Ccmmutty logo
Commutty IT
14 min read

青色コーダーが ABC 全問解説する【ABC289】

https://cdn.magicode.io/media/notebox/955e4125-aa96-4c51-9495-b66ceccce3f5.jpeg

Sky株式会社プログラミングコンテスト2023(AtCoder Beginner Contest 289)

4 完…(´・ω・`) E 問題思いつかないし、F 問題も通しきれないし…(´・ω・`)

A - flip

11 文字目から順に見て、0 だったら 11 だったら 0 を出力すればいい。stringfor とかを使えれば OK。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;

    cin >> s;

    for (int i = 0; i < s.length(); ++i) cout << (s[i] == '0' ? 1 : 0);

    return 0;
}

B - レ

「レ」でつながっている数字を逆から出力するだけだけど、実装が若干大変?
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;

    cin >> n >> m;

    vector<int> a(m);
    for (int i = 0; i < m; ++i) cin >> a[i];

    a.push_back(0);  // 番兵
    for (int i = 1, k = 0; i <= n; ++i) {
        int from = i;  // from の左は「レ」でつながってない
        while (a[k] == i) ++i, ++k;  // 「レ」でつながっている間 i と k に 1 加算
        for (int j = i; j >= from; --j) cout << j << ' ';  // 逆順に出力
    }

    return 0;
}

C - Coverage

bit 全探索。わからない人は、AtCoder のここにも書いてあるので読むとよさそう。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;

    cin >> n >> m;

    vector<vector<int>> s(m);  // 集合 (0-indexed)
    for (int i = 0, c; i < m; ++i) {
        cin >> c;
        s[i].resize(c);
        for (int j = 0; j < c; ++j) {
            cin >> s[i][j];
			--s[i][j];
        }
    }

    int ans = 0;
    vector<bool> all(n, 1);  // 全部ある場合
    // bit 全探索
    for (int i = 0; i < (1 << m); ++i) {
        vector<bool> ss(n);
        for (int j = 0; j < m; ++j) {
            if (i & (1 << j)) {
                for (int a : s[j]) {
                    ss[a] = true;
                }
            }
        }
        if (ss == all) ++ans;  // 全部あるなら答えに 1 加算
    }

    cout << ans;

    return 0;
}

D - Step Up Robot

DP。
dp[i]dp[i]bool\text{bool} 値 (ちょうど ii 段目にのぼることが可能か) とおけば、
dp[0]=true,dp[k]=false(k<0)dp[0]=\text{true}, dp[k]=\text{false} (k<0) として、ii の昇順に、
dp[i]={false(if    (i{B1,,BM}) or (a{A1,,AN},dp[ia]=false))true(otherwise)dp[i]= \begin{cases} \text{false} & \left(\text{if}\;\; (i \in \{B_1, \cdots, B_M\}) \text{ or } (\forall a \in \{A_1, \cdots, A_N\}, dp[i-a] = \text{false})\right) \\ \text{true} & (\text{otherwise}) \end{cases}
で遷移できる。オーダーは、O(NX)O(NX)
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m, x;

    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    cin >> m;

    vector<int> b(m);
    for (int i = 0; i < m; ++i) cin >> b[i];

    cin >> x;

    vector<bool> mochi(x + 1);
    for (int i = 0; i < m; ++i) mochi[b[i]] = true;

    vector<bool> dp(x + 1);
    dp[0] = true;
    for (int i = 1; i <= x; ++i) {
        if (mochi[i]) continue;
        for (int j = 0; j < n; ++j) {
            if (i - a[j] < 0) break;
            if (dp[i - a[j]]) {
                dp[i] = true;
                break;
            }
        }
    }

    cout << (dp[x] ? "Yes" : "No");

    return 0;
}

E - Swap Places

((高橋君がいる頂点,, 青木君がいる頂点)) を考える。
すると、候補となる組 (i,j)(i,j) は、(1,N)(1,N) 以外、CiCjC_i \neq C_j を満たす必要がある。ここで、(N,1)(N,1) が候補となるためには、CNC1C_N \neq C_1 でなくてはいけないので、(1,N)(1,N)CiCjC_i \neq C_j を満たす必要がある。
よって、CiCjC_i \neq C_j を満たす組 (i,j)(i,j) を新たな頂点とすれば、頂点 (1,N)(1,N) から頂点 (N,1)(N,1) への距離を求めるだけでよくなる。距離は BFS で求められるので、オーダーは、O(N2+M2)O(\sum N^2 + \sum M^2)
なお、頂点 (ui,uj)(u_i,u_j) と 頂点 (vi,vj)(v_i,v_j) を結ぶ辺を張るのは、頂点 uiu_i と頂点 viv_i を結ぶ辺があり、頂点 uju_j と頂点 vjv_j を結ぶ辺もあるとき、かつそのときのみである。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int t, n, m;

    cin >> t;

    for (int cases = 0; cases < t; ++cases) {
        cin >> n >> m;
        vector<int> c(n);
        for (int i = 0; i < n; ++i) cin >> c[i];

        vector<bool> isDifColor(n * n);  // C_i != C_j かどうか
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                isDifColor[i * n + j] = (c[i] != c[j]);
            }
        }

        vector<pair<int, int>> edge(m);
        for (int i = 0, u, v; i < m; ++i) {
            cin >> u >> v;
            --u; --v;
            edge[i] = {u, v};
        }

        vector<vector<int>> g(n * n);
        for (int i = 0; i < m; ++i) {
            auto [ui, vi] = edge[i];
            for (int j = 0; j < m; ++j) {
                auto [uj, vj] = edge[j];
                int unum = ui * n + uj, vnum = vi * n + vj;
                int uvnum = ui * n + vj, vunum = vi * n + uj;

                // C_i != C_j なら辺を張る
                if (isDifColor[unum] && isDifColor[vnum]) {
                    g[unum].push_back(vnum);
                    g[vnum].push_back(unum);
                }
                if (isDifColor[uvnum] && isDifColor[vunum]) {
                    g[uvnum].push_back(vunum);
                    g[vunum].push_back(uvnum);
                }
            }
        }

        // bfs
        queue<int> que;
        vector<int> d(n * n, -1);
        que.push(n - 1);
        d[n - 1] = 0;
        while (!que.empty()) {
            int v = que.front();
            que.pop();

            for (int child : g[v]) {
                if (d[child] == -1) {
                    d[child] = d[v] + 1;
                    que.push(child);
                }
            }
        }
        cout << d[(n - 1) * n] << '\n';
    }

    return 0;
}

F - Teleporter Takahashi

今いる位置を (px,py)(p_x,p_y) とおくと、(x,y)(x,y) を中心とした対称な位置は、(2xpx,2ypy)(2x-p_x,2y-p_y) である。なので、pxp_xpyp_y も、移動によって偶奇は変わらない。
よって、(sx,sy)(s_x,s_y) から (tx,ty)(t_x,t_y) に移動するためには、sxtx(mod2)s_x \equiv t_x \pmod 2 かつ syty(mod2)s_y \equiv t_y \pmod 2 でなくてはいけない。
また、(px,py)(p_x,p_y) から (x,y)(x,y) を中心に瞬間移動したあと、(x+1,y)(x+1,y) を中心に瞬間移動すると、(2(x+1)(2xpx),2y(2ypy))=(px+2,py)(2(x+1)-(2x-p_x),2y-(2y-p_y))=(p_x+2,p_y) に着く。同様に、(x,y)(x,y) を中心に瞬間移動したあと、(x,y+1)(x,y+1) を中心に瞬間移動すると、(px,py+2)(p_x,p_y+2) に着く。
よって、aba \neq b かつ cdc \neq d であれば、偶奇が一致している任意の位置に、sxtx+syty|s_x-t_x| + |s_y-t_y| 回の瞬間移動で移動できる。
そのため、以下の 44 パターンを考えればいい。
  • a=ba=b かつ c=dc=d のとき
    (tx,ty)=(sx,sy)(t_x,t_y) = (s_x,s_y) なら、移動なし。
    (tx,ty)=(2asx,2asy)(t_x,t_y) = (2a-s_x,2a-s_y) なら、(a,c)(a,c) を中心に 11 回瞬間移動するだけ。
    それ以外なら、到達不可能。
  • a=ba=b かつ cdc \neq d のとき、
    tx=sxt_x = s_x なら、syty(106)|s_y-t_y| (\leq 10^6) 回の移動で到達可能。
    tx=2asxt_x=2a-s_x なら、(a,c)(a,c) を中心に 11 回瞬間移動したあと、(2csy)ty(106)|(2c-s_y)-t_y| (\leq 10^6) 回の移動で到達可能。
    それ以外なら、到達不可能。
  • aba \neq b かつ c=dc = d のとき、
    ty=syt_y = s_y なら、sxtx(106)|s_x-t_x| (\leq 10^6) 回の移動で到達可能。
    ty=2asyt_y=2a-s_y なら、(a,c)(a,c) を中心に 11 回瞬間移動したあと、(2asx)tx(106)|(2a-s_x)-t_x| (\leq 10^6) 回の移動で到達可能。
    それ以外なら、到達不可能。
  • aba \neq b かつ cdc \neq d のとき、
    sxtx+syty(106)|s_x-t_x| + |s_y-t_y| (\leq 10^6) 回の移動で到達可能。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int sx, sy, tx, ty, a, b, c, d;

    cin >> sx >> sy >> tx >> ty >> a >> b >> c >> d;

    if (((sx ^ tx) & 1) || ((sy ^ ty) & 1)) {  // 偶奇が一致していないなら
        cout << "No";
        return 0;
    }

    bool swaped = false;  // (a, c) を中心に 1 回瞬間移動するかどうか
    if (a == b) {
        if (c == d) {  // a = b かつ c = d
            if (sx == tx && sy == ty) {
                cout << "Yes";
            } else if (tx == a * 2 - sx && ty == c * 2 - sy) {
                cout << "Yes\n";
                cout << a << ' ' << c << '\n';
            } else {
                cout << "No";
            }
            return 0;
        } else {  // a = b かつ c != d
            if (sx != tx) {
                if (tx != a * 2 - sx) {
                    cout << "No";
                    return 0;
                } else {
                    swaped = true;
                    sx = tx;
                    sy = c * 2 - sy;
                }
            }
        }
    } else if (c == d) {  // a != b かつ c = d
        if (sy != ty) {
            if (ty != c * 2 - sy) {
                cout << "No";
                return 0;
            } else {
                swaped = true;
                sx = a * 2 - sx;
                sy = ty;
            }
        }
    }

    cout << "Yes\n";
    if (swaped) cout << a << ' ' << c << '\n';
    int xnum = abs(sx - tx) / 2;
    bool sx_less_tx = (sx < tx);
    // sx < tx なら (a, c), (a + 1, c) を中心にそれぞれ xnum 回瞬間移動
    // sx >= tx なら (a + 1, c), (a, c) を中心にそれぞれ xnum 回瞬間移動
    for (int i = 0; i < xnum; ++i) {
        cout << a + (1 - sx_less_tx) << ' ' << c << '\n';
        cout << a + sx_less_tx << ' ' << c << '\n';
    }

    int ynum = abs(sy - ty) / 2;
    bool sy_less_ty = (sy < ty);
    // sy < ty なら (a, c), (a, c + 1) を中心にそれぞれ ynum 回瞬間移動
    // sy >= ty なら (a, c + 1), (a, c) を中心にそれぞれ ynum 回瞬間移動
    for (int i = 0; i < ynum; ++i) {
        cout << a << ' ' << c + (1 - sy_less_ty) << '\n';
        cout << a << ' ' << c + sy_less_ty << '\n';
    }

    return 0;
}

G - Shopping in AtCoder store

nin_iBjBiB_j \geq B_i となる jj の数 (j=ij=i を含む) とおくと、答えは、maxi(Bi+Cj)ni\displaystyle\max_i (B_i+C_j)n_i
k=1,,Nk=1, \cdots, N について、(Bk+C)ni=maxi(Bi+C)ni(B_k+C)n_i=\displaystyle\max_i (B_i+C)n_i となる CC の範囲を求めれば、答えは、二分探索で求められる。
CC の範囲は、ソートを含めて O(NlogN)O(N \log N) で求められる。自力で実装したけど、Convex Hull Trick とかいう名前がついてるらしい。
全体のオーダーは、O((N+M)logN)O((N+M) \log N)
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, m;

    cin >> n >> m;

    vector<ll> b(n);
    for (int i = 0; i < n; ++i) cin >> b[i];

    sort(b.rbegin(), b.rend());

    vector<tuple<ll, ll, int>> cs;  // (C の下限, 購買意欲, 人数)
    cs.emplace_back(0, b[0], 1);

    // C の範囲を求める
    auto ceil = [](ll a, ll b) { return (a + b - 1) / b; };
    for (int i = 1; i < n; ++i) {
        ll ic;
        while (!cs.empty()) {
            auto [minc, bnum, num] = cs.back();
            ic = ceil((bnum - b[i]) * num, (i + 1 - num)) - b[i];
            if (ic <= minc) cs.pop_back();
            else break;
        }
        cs.emplace_back(max(0ll, ic), b[i], i + 1);
    }

    // 二分探索
    int csSize = cs.size();
    for (int i = 0, c; i < m; ++i) {
        cin >> c;
        int ok = -1, ng = csSize;
        for (int mid = (ok + ng) / 2; abs(ok - ng) > 1; mid = (ok + ng) / 2) {
            ll midc = get<0>(cs[mid]);
            if (midc <= c) ok = mid;
            else ng = mid;
        }
        auto [dummy, bnum, num] = cs[ok];
        cout << (bnum + c) * num << ' ';
    }

    return 0;
}

Ex - Trio

編集中…。

Discussion

コメントにはログインが必要です。