Ccmmutty logo
Commutty IT
・14 min read

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

競技プログラミングAtCoderAtCoderBeginnerContest
https://cdn.magicode.io/media/notebox/339b11fa-abb6-4ac1-a62b-2fc1541f49c9.jpeg

AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）

6 完。黄パフォに 7 完必須だった…(´・ω・｀)

A - camel Case

大文字を探すだけ。文字 A ~ Z には、ASCII コードで、数値 6565 ~ 9090 が割り当てられているので、不等式が使える。
文字 cc が大文字かどうかを調べるには、'A' <= c && c <= 'Z' かどうか調べればいい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;

    cin >> s;

    for (int i = 0; i < s.length(); ++i) {
        if ('A' <= s[i] && s[i] <= 'Z') {
            cout << i + 1;
            break;
        }
    }

    return 0;
}

B - Trimmed Mean

昇順で N+1N+1 番目の人から 4N4N 番目の人までの評点の平均をとるだけ。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;

    cin >> n;

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

    sort(x.begin(), x.end());  // 昇順にソート

    // N + 1 番目の人から 4N 番目の人までの評点の総和を計算
    double sum = 0;
    for (int i = n; i < 4 * n; ++i) sum += x[i];

    printf("%.10lf", sum / (3 * n));  // 平均を出力

    return 0;
}

C - LRUD Instructions 2

いたことがある座標を set などで管理すれば、移動ごとに O(log⁡N)O(\log N) で判定できる。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    string s;

    cin >> n >> s;

    int x = 0, y = 0;
    set<pair<int, int>> st;
    st.insert({x, y});
    for (int i = 0; i < n; ++i) {
        // 移動
        if (s[i] == 'R') ++x;
        else if (s[i] == 'L') --x;
        else if (s[i] == 'U') ++y;
        else if (s[i] == 'D') --y;

        // いたことがあるなら "Yes" を出力して終了
        if (st.find({x, y}) != st.end()) {
            cout << "Yes";
            return 0;
        }
        st.insert({x, y});  // set に今いる座標を追加
    }

    cout << "No";

    return 0;
}

D - Flip Cards

dp[i][c]=\text{dp}[i][c]= (カード 11 からカード ii までのみを考えたとき、条件を満たす選び方 (cc はカード ii を裏返すかどうかの bool\text{bool} 値)) とおくと、dp[0][0]=dp[0][1]=1\text{dp}[0][0]=\text{dp}[0][1]=1 で、
dp[i][0] += dp[i−1][0]  (if    Ai≠Ai−1)dp[i][0] += dp[i−1][1]  (if    Ai≠Bi−1)dp[i][1] += dp[i−1][0]  (if    Bi≠Ai−1)dp[i][1] += dp[i−1][1]  (if    Bi≠Bi−1)\text{dp}[i][0] \text{ += } \text{dp}[i-1][0] \; (\text{if}\;\; A_i \neq A_{i-1}) \\ \text{dp}[i][0] \text{ += } \text{dp}[i-1][1] \; (\text{if}\;\; A_i \neq B_{i-1}) \\ \text{dp}[i][1] \text{ += } \text{dp}[i-1][0] \; (\text{if}\;\; B_i \neq A_{i-1}) \\ \text{dp}[i][1] \text{ += } \text{dp}[i-1][1] \; (\text{if}\;\; B_i \neq B_{i-1}) \\
のように遷移できる。答えは、dp[N][0]+dp[N][1]dp[N][0]+dp[N][1]。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    const int mod = 998244353;

    cin >> n;

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

    vector<vector<int>> dp(n, vector<int>(2));
    dp[0][0] = 1, dp[0][1] = 1;
    for (int i = 1; i < n; ++i) {
        if (a[i] != a[i - 1]) dp[i][0] += dp[i - 1][0];
        if (a[i] != b[i - 1]) dp[i][0] += dp[i - 1][1];
        if (b[i] != a[i - 1]) dp[i][1] += dp[i - 1][0];
        if (b[i] != b[i - 1]) dp[i][1] += dp[i - 1][1];

        dp[i][0] %= mod;
        dp[i][1] %= mod;
    }

    cout << (dp[n - 1][0] + dp[n - 1][1]) % mod;

    return 0;
}

E - Find Permutation

XiX_i から YiY_i への辺を張ったグラフのトポロジカルソートの結果が一意に決まるかどうかを考えればいい。一意に決まるなら、トポロジカルソートの結果を (S1,⋯ ,SN)(S_1, \cdots, S_N) とおくと、ASi=iA_{S_i}=i。一意に決まらないなら。AA も一意でない。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

// 一意に決まるかどうかを調べる。
pair<bool, vector<int>> solve(const vector<vector<int>> &g) {
    int sz = g.size();
    vector<int> in(sz);
    vector<int> perm(sz);  // 一意に決まる場合の順列
    stack<int> roots;

    for (int u = 0; u < sz; ++u) {
        for (int v : g[u]) {
            ++in[v];
        }
    }

    for (int i = 0; i < sz; ++i) {
        if (!in[i]) roots.push(i);
    }

    int v;
    int cnt = 0;
    while (!roots.empty()) {
        // 次に調べる候補が 2 つ以上なら一意ではない
        if (roots.size() != 1) return {false, perm};

        v = roots.top();
        roots.pop();

        perm[v] = ++cnt;

        for (int a : g[v]) {
            --in[a];
            if (!in[a]) roots.push(a);
        }
    }

    return {true, perm};
}

int main() {
    int n, m;

    cin >> n >> m;

    vector<vector<int>> g(n);
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v);
    }

    auto [bl, perm] = solve(g);

    cout << (bl ? "Yes" : "No") << "\n";
    if (bl) for (int i = 0; i < n; ++i) cout << perm[i] << ' ';

    return 0;
}

F - Teleporter and Closed off

都市 kk を通らずに移動するためには、u<k<vu<k<v を満たし、テレポーターを 11 回利用して、都市 uu から 都市 vv へ移動でき、都市 11 から都市 uu、都市 vv から都市 NN へ移動できるような u,vu,v が存在するとき、かつそのときのみである。
1≤v−u≤M1 \leq v-u \leq M なので、組 (u,v)(u,v) の候補は O(M2)O(M^2) 個程度。よって、「都市 11 から各都市へのテレポーターの使用回数の最小値」と「各都市から都市 NN へのテレポーターの使用回数の最小値」を前計算しておけば、各 kk に対して O(M2)O(M^2) で答えを求められるので、全体で、O(NM2)O(NM^2)。
なお、「都市 11 から各都市へのテレポーターの使用回数の最小値」と「各都市から都市 NN へのテレポーターの使用回数の最小値」は BFS や DFS などで O(N)O(N) で求められる。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

vector<int> bfs(vector<vector<int>> &g, int r) {
    queue<int> que;
    vector<int> d(g.size(), -1);
    que.push(r);
    d[r] = 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);
            }
        }
    }

    return d;
}

int main() {
    int n, m;

    cin >> n >> m;

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


    vector<vector<int>> g(n), gr(n);  // gr は逆向き
    for (int i = 0, u, v; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (s[i][j] == '1') {
                u = i;
                v = i + j + 1;
                g[u].push_back(v);
                gr[v].push_back(u);
            }
        }
    }

    vector<int> d1 = bfs(g, 0), dn = bfs(gr, n - 1);

    const int INF = 1 << 30;
    for (int i = 1; i < n - 1; ++i) {
        int ans = INF;
        for (int u = max(0, i - m + 1); u < i; ++u) {
            for (int v = i + 1; v <= min(n - 1, u + m); ++v) {
                if (s[u][v - u - 1] == '1' && d1[u] != -1 && dn[v] != -1) {
                    ans = min(ans, d1[u] + 1 + dn[v]);
                }
            }
        }
        cout << (ans == INF ? -1 : ans) << ' ';
    }

    return 0;
}

G - OR Sum

畳み込みかぁ…。
B′=(B0′,⋯ ,BN−1′)=(BN−1,⋯ ,B0)B'=(B'_0, \cdots, B'_{N-1})=(B_{N-1}, \cdots, B_0) とおくと、
∑i=0N−1(Ai∣Bi)=∑i=0N−1(Ai∣BN−1−i′)\sum_{i=0}^{N-1} (A_i|B_i)=\sum_{i=0}^{N-1} (A_i|B'_{N-1-i})
また、AN+i=AiA_{N+i}=A_i とおくと、AA を k(<N)k(<N) 回シフトしたとき、A=(Ak,⋯ ,AN−1+k)A=(A_k, \cdots, A_{N-1+k})。
よって、A′=(A0,⋯ ,A2N−1)A'=(A_0, \cdots, A_{2N-1}) とおくと、AA を k(<N)k(<N) 回シフトしたときの与式の解は、
∑i=0N−1(Ai+k′∣BN−1−i′)=∑i+j=N−1+k(Ai′∣Bj′)\sum_{i=0}^{N-1} (A'_{i+k}|B'_{N-1-i})=\sum_{i+j=N-1+k} (A'_{i}|B'_{j})
となる。つまり、
min⁡0≤k<N∑i+j=N−1+k(Ai′∣Bj′)\min_{0 \leq k < N} \sum_{i+j=N-1+k} (A'_{i}|B'_{j})
が解。
Ai′A'_i の xx ビット目の値を ai,x′a'_{i,x}、Bi′B'_i の xx ビット目の値を bi,x′b'_{i,x} とおくと、
∑i+j=N−1+k(Ai′∣Bj′)=∑i+j=N−1+k∑x2x(ai,x′∣bi,x′)=∑x2x∑i+j=N−1+k(ai,x′∣bi,x′)\begin{align*} \sum_{i+j=N-1+k} (A'_{i}|B'_{j})&= \sum_{i+j=N-1+k} \sum_{x} 2^x (a'_{i,x} | b'_{i,x}) \\ &=\sum_{x} 2^x \sum_{i+j=N-1+k} (a'_{i,x} | b'_{i,x}) \end{align*}
ai,x′∣bi,x′=1−(ai,x′‾&bi,x′‾)=1−(ai,x′‾⋅bi,x′‾)a'_{i,x} | b'_{i,x} = 1-(\overline{a'_{i,x}} \& \overline{b'_{i,x}})=1-(\overline{a'_{i,x}} \cdot \overline{b'_{i,x}}) (&(\& はビット毎の論理積)) なので、
∑i+j=N−1+k(Ai′∣Bj′)=∑x2x∑i+j=N−1+k1−(ai,x′‾⋅bi,x′‾)=∑x2x{N−∑i+j=N−1+k(ai,x′‾⋅bi,x′‾)}\begin{align*} \sum_{i+j=N-1+k} (A'_{i}|B'_{j})&=\sum_{x} 2^x \sum_{i+j=N-1+k} 1-(\overline{a'_{i,x}} \cdot \overline{b'_{i,x}}) \\ &=\sum_{x} 2^x \{N -\sum_{i+j=N-1+k} (\overline{a'_{i,x}} \cdot \overline{b'_{i,x}})\} \end{align*}
よって、
min⁡0≤k<N∑x2x{N−∑i+j=N−1+k(ai,x′‾⋅bi,x′‾)}\min_{0 \leq k < N} \sum_{x} 2^x \{N -\sum_{i+j=N-1+k} (\overline{a'_{i,x}} \cdot \overline{b'_{i,x}})\}
が解。
0≤k<N0 \leq k < N の ∑i+j=N−1+k(ai,x′‾⋅bi,x′‾)\displaystyle\sum_{i+j=N-1+k} (\overline{a'_{i,x}} \cdot \overline{b'_{i,x}}) は畳み込みで O(Nlog⁡N)O(N \log N) で求められるため、オーダーは、O(Nlog⁡Nlog⁡max⁡(Ai,Bi))O(N \log N \log \max(A_i,B_i))。
↓ こんな感じ。
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

using ll = long long;

int main() {
    int n;

    cin >> n;

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

    reverse(b.begin(), b.end());  // B' にする

    vector<ll> bitA(n * 2), bitB(n);  // ビット毎
    vector<vector<ll>> con(5);        // ビット毎畳み込み
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < n; ++j) {
            bitA[j] = bitA[n + j] = ((a[j] >> i) & 1) ^ 1;  // A' にする
            bitB[j] = ((b[j] >> i) & 1) ^ 1;
        }
        con[i] = convolution_ll(bitA, bitB);
    }

    int ans = 0;
    for (int i = n - 1; i < n * 2 - 1; ++i) {
        int temp = 0;
        for (int j = 0; j < 5; ++j) temp += (n - con[j][i]) << j;
        ans = max(ans, temp);
    }

    cout << ans;

    return 0;
}

Ex - Balanced Tree

公式解説がわかりやすいので、解説は省略。
要は、重心分解を再帰的に行えばいい。重心を、重心分解でできた部分森の各重心の親としていけば、条件を満たす木ができる。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

// 重心を探す
void findCentroid(int v, int p, const int n, const vector<vector<int>> &tree, int &centroid,
				  const vector<bool> &removed, vector<int> &subtreeSize) {
    subtreeSize[v] = 1;
    bool flag = true;
    for (int a : tree[v]) {
        if (a != p && !removed[a]) {
            findCentroid(a, v, n, tree, centroid, removed, subtreeSize);
            subtreeSize[v] += subtreeSize[a];
            if (subtreeSize[a] > n / 2) flag = false;
        }
    }

    if (n - subtreeSize[v] > n / 2) flag = false;
    if (flag) centroid = v;
}

// 再帰的に重心分解し、根付き木を生成
vector<int> centroidDecomposition(vector<vector<int>> &tree) {
    int n = tree.size();
    vector<int> parent(n, -1);

    int centroid;
    vector<bool> removed(n);
    vector<int> subtreeSize(n);
    stack<int> s;

    subtreeSize[0] = n;
    s.push(0);
    while (!s.empty()) {
        int v = s.top();
        s.pop();

        findCentroid(v, -1, subtreeSize[v], tree, centroid, removed, subtreeSize);

        removed[centroid] = true;
        parent[centroid] = parent[v];  // 重心の親を書き換える

		// 子の部分木をスタックに入れる
        for (int a : tree[centroid]) {
            if (!removed[a]) {
                parent[a] = centroid;  // 重心の親を書き換えるために一時的に保持
                if (subtreeSize[a] > subtreeSize[centroid]) {
                    subtreeSize[a] = subtreeSize[v] - subtreeSize[centroid];
                }
                s.push(a);
            }
        }
    }

    return parent;
}

int main() {
    int n;

    cin >> n;

    vector<vector<int>> g(n);
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        --u; --v;
        g[u].push_back(v); g[v].push_back(u);
    }

    for (int i : centroidDecomposition(g)) cout << (i == -1 ? -1 : i + 1) << ' ';

    return 0;
}

Discussion

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