22か月前公開・22か月前更新・0 pv・14 min read

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

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

Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 289）

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

A - flip

1

文字目から順に見て、0 だったら 1、1 だったら 0 を出力すればいい。string と for とかを使えれば 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]

を

\text{bool}

値 (ちょうど

i

段目にのぼることが可能か) とおけば、

dp[0]=\text{true}, dp[k]=\text{false} (k<0)

として、

i

の昇順に、

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)

。

↓ こんな感じ。

#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)

は、

(1,N)

以外、

C_i \neq C_j

を満たす必要がある。ここで、

(N,1)

が候補となるためには、

C_N \neq C_1

でなくてはいけないので、

(1,N)

も

C_i \neq C_j

を満たす必要がある。

よって、

C_i \neq C_j

を満たす組

(i,j)

を新たな頂点とすれば、頂点

(1,N)

から頂点

(N,1)

への距離を求めるだけでよくなる。距離は BFS で求められるので、オーダーは、

O(\sum N^2 + \sum M^2)

。

なお、頂点

(u_i,u_j)

と頂点

(v_i,v_j)

を結ぶ辺を張るのは、頂点

u_i

と頂点

v_i

を結ぶ辺があり、頂点

u_j

と頂点

v_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

今いる位置を

(p_x,p_y)

とおくと、

(x,y)

を中心とした対称な位置は、

(2x-p_x,2y-p_y)

である。なので、

p_x

も

p_y

も、移動によって偶奇は変わらない。
よって、

(s_x,s_y)

から

(t_x,t_y)

に移動するためには、

s_x \equiv t_x \pmod 2

かつ

s_y \equiv t_y \pmod 2

でなくてはいけない。

また、

(p_x,p_y)

から

(x,y)

を中心に瞬間移動したあと、

(x+1,y)

を中心に瞬間移動すると、

(2(x+1)-(2x-p_x),2y-(2y-p_y))=(p_x+2,p_y)

に着く。同様に、

(x,y)

を中心に瞬間移動したあと、

(x,y+1)

を中心に瞬間移動すると、

(p_x,p_y+2)

に着く。
よって、

a \neq b

かつ

c \neq d

であれば、偶奇が一致している任意の位置に、

|s_x-t_x| + |s_y-t_y|

回の瞬間移動で移動できる。

そのため、以下の

4

パターンを考えればいい。

$a=b$ かつ $c=d$ のとき
$(t_x,t_y) = (s_x,s_y)$ なら、移動なし。
$(t_x,t_y) = (2a-s_x,2a-s_y)$ なら、 $(a,c)$ を中心に $1$ 回瞬間移動するだけ。
それ以外なら、到達不可能。
$a=b$ かつ $c \neq d$ のとき、
$t_x = s_x$ なら、 $|s_y-t_y| (\leq 10^6)$ 回の移動で到達可能。
$t_x=2a-s_x$ なら、 $(a,c)$ を中心に $1$ 回瞬間移動したあと、 $|(2c-s_y)-t_y| (\leq 10^6)$ 回の移動で到達可能。
それ以外なら、到達不可能。
$a \neq b$ かつ $c = d$ のとき、
$t_y = s_y$ なら、 $|s_x-t_x| (\leq 10^6)$ 回の移動で到達可能。
$t_y=2a-s_y$ なら、 $(a,c)$ を中心に $1$ 回瞬間移動したあと、 $|(2a-s_x)-t_x| (\leq 10^6)$ 回の移動で到達可能。
それ以外なら、到達不可能。
$a \neq b$ かつ $c \neq d$ のとき、
$|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

n_i

を

B_j \geq B_i

となる

j

の数 (

j=i

を含む) とおくと、答えは、

\displaystyle\max_i (B_i+C_j)n_i

。

k=1, \cdots, N

について、

(B_k+C)n_i=\displaystyle\max_i (B_i+C)n_i

となる

C

の範囲を求めれば、答えは、二分探索で求められる。

C

の範囲は、ソートを含めて

O(N \log N)

で求められる。自力で実装したけど、Convex Hull Trick とかいう名前がついてるらしい。

全体のオーダーは、

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

編集中…。

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

Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 289）

A - flip

B - レ

C - Coverage

D - Step Up Robot

E - Swap Places

F - Teleporter Takahashi

G - Shopping in AtCoder store

Ex - Trio

Discussion

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