Ccmmutty logo
Commutty IT
・0 pv・16 min read

水色コーダーが ABC 全問解説する【ABC284】

AtCoder競技プログラミングAtCoderBeginnerContest
https://cdn.magicode.io/media/notebox/1adefaa8-4b3f-4db6-ad05-167153f2420b.jpeg

AtCoder Beginner Contest 284

6 完。D 問題でペナ 2 が痛い(´・ω・｀)
5 完で緑パフォって…。6 完も水パフォだし、今回 (思ったより) だいぶ簡単だったのか…。

A - Sequence of Strings

入力と逆順に出力するだけ。for 使えれば解ける。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;

    cin >> n;

    vector<string> s(n);
    for (int i = 0; i < n; ++i) cin >> s[i];
    for (int i = n - 1; i >= 0; --i) cout << s[i] << '\n';

    return 0;
}

B - Multi Test Cases

複数のテストケースについて解くタイプの問題に慣れるための問題かな？
複数のテストケースが含まれることを考えなければ、奇数の数を数えるだけなので、ほぼ A 問題くらいの難度。
(一応) x が奇数かどうかは x % 2 == 1 かどうかと等しい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

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

    cin >> t;

    for (int i = 0; i < t; ++i) {  // T 個のテストケースについて
        int ans = 0;
        cin >> n;
        for (int j = 0; j < n; ++j) {
            cin >> a;
            // 奇数なら答えに 1 加算 (if (a % 2) とか if (a & 1) とかでもできる)
            if (a % 2 == 1) ++ans;
        }
        cout << ans << '\n';
    }

    return 0;
}

C - Count Connected Components

BFS や DFS で連結である頂点をすべて探索できるので、それを各頂点ごとに行えばいい。ただし、別の頂点からの探索で探索済みの頂点は飛ばす。(飛ばさなかった頂点の個数) = (連結成分の個数)。
まあ、Union-Find とかを使ってもいい。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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);
        g[v].push_back(u);
    }

    int ans = 0;

    // 各頂点ごとに BFS
    vector<bool> visited(n);  // 探索済みなら true
    for (int i = 0; i < n; ++i) {
        if (visited[i]) continue;  // 探索済みなら continue
        ++ans;  // 探索済みでないなら答えに 1 加算して BFS
        queue<int> que;
        que.push(i);
        visited[i] = 0;
        while (!que.empty()) {
            int v = que.front();
            que.pop();

            for (int child : g[v]) {
                if (!visited[child]) {
                    visited[child] = true;
                    que.push(child);
                }
            }
        }
    }

    cout << ans;

    return 0;
}

D - Happy New Year 2023

N=p2q≤9×1018N = p^2 q \leq 9 \times 10^{18} で、9×10183\sqrt[3]{9 \times 10^{18}} が高々 3×1063 \times 10^6 なので、p≤3×106p \leq 3 \times 10^6 または q≤3×106q \leq 3 \times 10^6。p,qp,q は素数なので、NN の 22 以上の最小の約数を rr とおけば、p=rp=r または q=rq=r。
なので、NN が r2r^2 で割り切れなければ、q=r,p=Nrq=r,p=\sqrt{\frac{N}{r}}、割り切れれば、p=r,q=Nr2p=r,q=\frac{N}{r^2}。
2≤r≤3×1062 \leq r \leq 3 \times 10^6 なので、22 から順番に NN の約数かどうか調べれば間に合う。
sqrt 関数は double を扱うから long long を入れると誤差が出るので、long double を扱う sqrtl 関数を使うほうが無難。(今回は誤差が出ても、整数に直す際の四捨五入で帳尻が合うっぽい。)
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int t;
    ll p, q;
    ll n;

    cin >> t;

    for (int i = 0; i < t; ++i) {
        cin >> n;
        for (ll r = 2; r <= 3000000; ++r) {
            if (!(n % r)) {  // n の約数なら
                if (n % (r * r)) {  // r の 2 乗の約数なら
                    p = sqrtl(n / r);
                    q = r;
                } else {  // r の 2 乗の約数でないなら
                    p = r;
                    q = n / (r * r);
                }
                cout << p << ' ' << q << '\n';
                break;
            }
        }
    }

    return 0;
}

E - Count Simple Paths

DFS でバックトラックすればいい。
DFS では、進むごとに別のパスを通るので、進んだときに答えに 11 加算する。通ったところは記録しておき、そこには進めないものとする。戻るときに、その位置の記録を消す。答えが 10610^6 以上になった場合は、その時点で強制終了する。
オーダーは、O(min⁡(K,106))O(\min(K,10^6))。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int dfs(int v, vector<vector<int>>& g, vector<bool>& visited) {
    static int ans = 0;
    if (ans == 1000000) return 1000000;  // 1000000 になったら強制終了

    ++ans;
    visited[v] = true;  // 通ったことを記録する
    for (int a : g[v]) {
        if (!visited[a]) {  // 通ってないところを探索
            dfs(a, g, visited);
        }
    }
    visited[v] = false;  // 戻るときに記録を消す

    return ans;
}

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);
        g[v].push_back(u);
    }

    vector<bool> visited(n);
    cout << dfs(0, g, visited);

    return 0;
}

F - ABCBAC

連続部分文字列を各 O(1)O(1) で比較できればいいので知識ゲー。
ロリハ (rolling hash) で解きました。
00-indexed で考えると、TT の [0,i)[0,i) 文字目と、TT を反転した文字列 revTrevT の [N−i,N)[N-i,N) 文字目が一致して、かつ、TT の [N+i,2N)[N+i,2N) 文字目と、revTrevT の [N,2N−i)[N,2N-i) 文字目が一致していればいい。
ロリハで各 O(1)O(1) で比較できるので、O(N)O(N)。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

// rolling hash
template <typename T = char>
class RollingHash {
    const unsigned long long base;
    const unsigned long long mask31 = (1ull << 31) - 1;
    const unsigned long long mask30 = (1ull << 30) - 1;
    const unsigned long long mod = (1ull << 61) - 1;
    const unsigned long long mask61 = mod;
    const size_t n;

    vector<unsigned long long> hash;
    vector<unsigned long long> basePow;

    unsigned long long mul(unsigned long long a, unsigned long long b) {
        unsigned long long ah = a >> 31, al = a & mask31;
        unsigned long long bh = b >> 31, bl = b & mask31;
        unsigned long long m = ah * bl + al * bh;
        unsigned long long mh = m >> 30, ml = m & mask30;

        return ah * bh * 2 + mh + (ml << 31) + al * bl;
    }

    unsigned long long calcMod(unsigned long long a) {
        unsigned long long ah = a >> 61, al = a & mask61;
        unsigned long long ret = ah + al;
        if (ret >= mod) ret -= mod;

        return ret;
    }

   public:
    RollingHash(const vector<T>& s, unsigned long long _base = 1000000009)
        : base(_base), n(s.size()), hash(n + 1), basePow(n + 1) {
        basePow[0] = 1;
        for (size_t i = 0; i < n; ++i) {
            hash[i + 1] = calcMod(mul(hash[i], base) + s[i]);
            basePow[i + 1] = calcMod(mul(basePow[i], base));
        }
    }
    RollingHash(const string& s, unsigned long long _base = 263)
        : RollingHash(vector<char>(s.begin(), s.end()), _base) {}

    unsigned long long getHash(int x) { return hash[x]; }

    // [L, R) の hash 値を返す
    unsigned long long getHash(int L, int R) {
        return calcMod(hash[R] + mod * 4 - mul(hash[L], basePow[R - L]));
    }
};

int main() {
    int n;
    string t;

    cin >> n >> t;

    string rt(t.rbegin(), t.rend());  // T を反転した文字列
    RollingHash ht(t), hrt(rt);       // rolling hash

    for (int i = 0; i < n; ++i) {
        if (ht.getHash(0, i) == hrt.getHash(n - i, n) &&
            ht.getHash(n + i, n * 2) == hrt.getHash(n, n * 2 - i)) {
            cout << rt.substr(n - i, n) << '\n' << i;
            return 0;
        }
    }

    cout << -1;

    return 0;
}

G - Only Once

公式解説見ました。対称性があるから B1B_1 だけ考えればいいのか…。
解き方が同じなので、解説は基本的に公式解説に任せます。
一応、S1S_1 の総和が、
N−1Pl−1NN−l∑p=1l(p−1){}_{N-1} \mathrm{P}_{l-1} N^{N-l} \sum_{p=1}^l (p-1)
になる点が一瞬怪しかったので補足。
公式解説では、B1,1,B1,2,⋯ ,B1,l+1B_{1,1}, B_{1,2}, \cdots, B_{1,l+1} を固定してるけど、B1,1,B1,2,⋯ ,B1,lB_{1,1}, B_{1,2}, \cdots, B_{1,l} までにしてみる (つまり、l+1→ll+1 \rightarrow l)。
すると、AB1,1,AB1,2,⋯ ,AB1,l−1A_{B_{1,1}}, A_{B_{1,2}}, \cdots, A_{B_{1,l-1}} が確定する。Bi,1=iB_{i,1}=i なので、固定するとき、B1,2,⋯ ,B1,lB_{1,2}, \cdots, B_{1,l} の l−1l-1 個を選ぶため、選び方は N−1Pl−1{}_{N-1} \mathrm{P}_{l-1} 通り。
また、AB1,1,AB1,2,⋯ ,AB1,l−1,AB1,lA_{B_{1,1}}, A_{B_{1,2}}, \cdots, A_{B_{1,l-1}}, A_{B_{1,l}} 以外は自由に選べ、選び方は NN−lN^{N-l} 通り。
よって、AB1,lA_{B_{1,l}} を除いた A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N の選び方は N−1Pl−1NN−l{}_{N-1} \mathrm{P}_{l-1} N^{N-l} 通り。
ここで、AB1,lA_{B_{1,l}} は、B1,1,⋯ ,B1,lB_{1,1}, \cdots, B_{1,l} のいずれかであり、AB1,l=B1,pA_{B_{1,l}}=B_{1,p} のとき、S1=p−1S_1=p-1 となる。
AB1,lA_{B_{1,l}} を除いた A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N の選び方は N−1Pl−1NN−l{}_{N-1} \mathrm{P}_{l-1} N^{N-l} 通りなので、AB1,l=B1,pA_{B_{1,l}}=B_{1,p} のときの S1S_1 の総和は、
N−1Pl−1NN−l(p−1){}_{N-1} \mathrm{P}_{l-1} N^{N-l} (p-1)
よって、S1S_1 の総和は、
∑p=1lN−1Pl−1NN−l(p−1)(=N−1Pl−1NN−l∑p=1l(p−1))\sum_{p=1}^l {}_{N-1} \mathrm{P}_{l-1} N^{N-l} (p-1) \left(= {}_{N-1} \mathrm{P}_{l-1} N^{N-l} \sum_{p=1}^l (p-1) \right)
式が出たので補足終わり。
MM が素数とは限らないので、N−1Pl−1{}_{N-1} \mathrm{P}_{l-1} とかを求めるときに割り算を使わないように注意。
↓ こんな感じ。
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, m;
    ll ans = 0;

    cin >> n >> m;

    vector<ll> P(n);     // {n - 1}_P_i
    vector<ll> powN(n);  // n の i 乗
    P[0] = 1; powN[0] = 1;
    for (int i = 1; i < n; ++i) P[i] = P[i - 1] * (n - i) % m;
    for (int i = 1; i < n; ++i) powN[i] = powN[i - 1] * n % m;

    // S_1 だけ計算する
    for (int i = 1; i <= n; ++i) {
        ans += P[i - 1] * powN[n - i] % m * ((ll)i * (i - 1) / 2 % m) % m;
        ans %= m;
    }

    cout << ans * n % m;  // 最後に n 倍する

    return 0;
}

Ex - Count Unlabeled Graphs

polya の数え上げ定理というものを使うらしい (公式解説)。
NN 頂点グラフの頂点への置換は、N!N! 個あり、置換ごとに、置換しても同じになるグラフの個数を数えて、平均を取ればいいっぽい。
置換しても同じになるグラフの例はこんな感じ。
置換をサイクル分解したときのサイクルの大きさの列が (c1,c2,⋯cm)(c_1, c_2, \cdots c_m) であるときの置換しても同じになるグラフの個数は、
  • 置換しても同じ色でなくてはいけないので、サイクルごとに同じ色である必要があるため、KmK^m 通り。
  • 置換しても同じになるサイクル内の辺の張り方は、pow(2,⌊ci2⌋)\text{pow}\left(2, \left\lfloor \dfrac{c_i}{2} \right\rfloor \right) 通り。
  • 置換しても同じになるサイクル間の辺の張り方は、pow(∑j=1i−1gcd(ci,cj))\text{pow}\left(\displaystyle\sum_{j=1}^{i-1} \text{gcd}(c_i, c_j) \right) 通り。
これらを合わせて、
Km×pow(2,∑i=1m(⌊ci2⌋+∑j=1i−1gcd(ci,cj)))K^m \times \text{pow} \left(2,{\sum_{i=1}^m \left( \left\lfloor \frac{c_i}{2} \right\rfloor + \sum_{j=1}^{i-1} \text{gcd}(c_i, c_j) \right)}\right)
個となる。自然数 NN の分割をすべて列挙して、各分割に対して (分割がそのようになる置換の通り数) × (グラフの個数) を足し合わせて、N!N! で割ったものが KK 色以下に塗る場合の答え。KK 色 "以下" なので、包除原理で、解である、ちょうど KK 色の場合を求める。
また、分割がそのようになる置換の通り数は、サイクルの大きさが ii であるものの個数を sis_i とおくと、
N!(∏ci)(∏(si!))\frac{N!}{(\prod c_i) (\prod (s_i!))}
である。
↓ こんな感じ。(基本的に公式解説と同じ。)
#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using mint = modint;

class Factorial {
    int n;
    vector<mint> fac;
    vector<mint> inv;

   public:
    Factorial(int _n) : n(max(0, _n)), fac(n + 1), inv(n + 1) {
        fac[0] = 1; inv[0] = 1;
        for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i;
        inv[n] = fac[n].inv();
        for (int i = n; i > 1; --i) inv[i - 1] = inv[i] * i;
    }

    mint getFac(int n) { return fac[n]; }

    mint C(int n, int r) {
        if (n < 0 || r < 0 || n < r) return 0;
        return fac[n] * inv[r] * inv[n - r];
    }
};

// k 色以下の polya の数え上げ
mint cal(int n, int k) {
    vector<pair<int, int>> v;
    mint ans = 0;
    Factorial F(n);

    // 分割用
    auto dfs = [&](auto self, int n, int last) -> void {
        if (n == 0) {
            mint cur = 1;  // 最後に N! で割る代わりに、置換の通り数の N! を掛けない
            for (int i = 0, sz = v.size(); i < sz; ++i) {
                auto [ci, si] = v[i];
                // ci の si 個分と si! で割る
                cur /= F.getFac(si) * ((mint)ci).pow(si);
                // k の si 乗を掛ける ((k の m 乗) = (k の sum(si) 乗))
                cur *= ((mint)k).pow(si);
                // 2 の floor(ci / 2) 乗を si 個掛ける
                cur *= ((mint)2).pow(ci / 2 * si);
                // 2 の gcd(ci, ci) 乗を si * (si - 1) / 2 個掛ける
                cur *= ((mint)2).pow(ci * si * (si - 1) / 2);
                // 2 の gcd(ci, cj) 乗を si * sj 個掛ける
                for (int j = 0; j < i; ++j) {
                    auto [cj, sj] = v[j];
                    cur *= ((mint)2).pow(gcd(ci, cj) * si * sj);
                }
            }
            ans += cur;
            return;
        }
        for (int i = last + 1; i <= n; ++i) {
            for (int j = 1; i * j <= n; ++j) {
                v.emplace_back(i, j);
                self(self, n - i * j, i);
                v.pop_back();
            }
        }
    };

    dfs(dfs, n, 0);

    return ans;
}

int main() {
    int n, k, p;
    mint ans = 0;

    cin >> n >> k >> p;

    mint::set_mod(p);
    Factorial F(n);
    // 包除原理
    for (int i = 1; i <= k; ++i) {
        ans += ((k ^ i) & 1 ? -1 : 1) * F.C(k, i) * cal(n, i);
    }

    cout << ans.val();

    return 0;
}

Discussion

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