Ccmmutty logo
Commutty IT
0 pv14 min read

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

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(logN)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[i1][0]  (if    AiAi1)dp[i][0] += dp[i1][1]  (if    AiBi1)dp[i][1] += dp[i1][0]  (if    BiAi1)dp[i][1] += dp[i1][1]  (if    BiBi1)\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 が存在するとき、かつそのときのみである。
1vuM1 \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,,BN1)=(BN1,,B0)B'=(B'_0, \cdots, B'_{N-1})=(B_{N-1}, \cdots, B_0) とおくと、
i=0N1(AiBi)=i=0N1(AiBN1i)\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 とおくと、AAk(<N)k(<N) 回シフトしたとき、A=(Ak,,AN1+k)A=(A_k, \cdots, A_{N-1+k})
よって、A=(A0,,A2N1)A'=(A_0, \cdots, A_{2N-1}) とおくと、AAk(<N)k(<N) 回シフトしたときの与式の解は、
i=0N1(Ai+kBN1i)=i+j=N1+k(AiBj)\sum_{i=0}^{N-1} (A'_{i+k}|B'_{N-1-i})=\sum_{i+j=N-1+k} (A'_{i}|B'_{j})
となる。つまり、
min0k<Ni+j=N1+k(AiBj)\min_{0 \leq k < N} \sum_{i+j=N-1+k} (A'_{i}|B'_{j})
が解。
AiA'_ixx ビット目の値を ai,xa'_{i,x}BiB'_ixx ビット目の値を bi,xb'_{i,x} とおくと、
i+j=N1+k(AiBj)=i+j=N1+kx2x(ai,xbi,x)=x2xi+j=N1+k(ai,xbi,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,xbi,x=1(ai,x&bi,x)=1(ai,xbi,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=N1+k(AiBj)=x2xi+j=N1+k1(ai,xbi,x)=x2x{Ni+j=N1+k(ai,xbi,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*}
よって、
min0k<Nx2x{Ni+j=N1+k(ai,xbi,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}})\}
が解。
0k<N0 \leq k < Ni+j=N1+k(ai,xbi,x)\displaystyle\sum_{i+j=N-1+k} (\overline{a'_{i,x}} \cdot \overline{b'_{i,x}}) は畳み込みで O(NlogN)O(N \log N) で求められるため、オーダーは、O(NlogNlogmax(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

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