15か月前公開・15か月前更新・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 完も水パフォだし、今回 (思ったより) だいぶ簡単だったのか…。

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？

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 = p^2 q \leq 9 \times 10^{18}

で、

\sqrt[3]{9 \times 10^{18}}

が高々

3 \times 10^6

なので、

p \leq 3 \times 10^6

または

q \leq 3 \times 10^6

。

p,q

は素数なので、

N

の

2

以上の最小の約数を

r

とおけば、

p=r

または

q=r

。
なので、

N

が

r^2

で割り切れなければ、

q=r,p=\sqrt{\frac{N}{r}}

、割り切れれば、

p=r,q=\frac{N}{r^2}

。

2 \leq r \leq 3 \times 10^6

なので、

2

から順番に

N

の約数かどうか調べれば間に合う。
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 では、進むごとに別のパスを通るので、進んだときに答えに

1

加算する。通ったところは記録しておき、そこには進めないものとする。戻るときに、その位置の記録を消す。答えが

10^6

以上になった場合は、その時点で強制終了する。
オーダーは、

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)

で比較できればいいので知識ゲー。

ロリハ (rolling hash) で解きました。

0

-indexed で考えると、

T

の

[0,i)

文字目と、

T

を反転した文字列

revT

の

[N-i,N)

文字目が一致して、かつ、

T

の

[N+i,2N)

文字目と、

revT

の

[N,2N-i)

文字目が一致していればいい。
ロリハで各

O(1)

で比較できるので、

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

公式解説見ました。対称性があるから

B_1

だけ考えればいいのか…。

解き方が同じなので、解説は基本的に公式解説に任せます。
一応、

S_1

の総和が、

{}_{N-1} \mathrm{P}_{l-1} N^{N-l} \sum_{p=1}^l (p-1)

になる点が一瞬怪しかったので補足。

公式解説では、

B_{1,1}, B_{1,2}, \cdots, B_{1,l+1}

を固定してるけど、

B_{1,1}, B_{1,2}, \cdots, B_{1,l}

までにしてみる (つまり、

l+1 \rightarrow l

)。

すると、

A_{B_{1,1}}, A_{B_{1,2}}, \cdots, A_{B_{1,l-1}}

が確定する。

B_{i,1}=i

なので、固定するとき、

B_{1,2}, \cdots, B_{1,l}

の

l-1

個を選ぶため、選び方は

{}_{N-1} \mathrm{P}_{l-1}

通り。
また、

A_{B_{1,1}}, A_{B_{1,2}}, \cdots, A_{B_{1,l-1}}, A_{B_{1,l}}

以外は自由に選べ、選び方は

N^{N-l}

通り。
よって、

A_{B_{1,l}}

を除いた

A_1, A_2, \cdots, A_N

の選び方は

{}_{N-1} \mathrm{P}_{l-1} N^{N-l}

通り。

ここで、

A_{B_{1,l}}

は、

B_{1,1}, \cdots, B_{1,l}

のいずれかであり、

A_{B_{1,l}}=B_{1,p}

のとき、

S_1=p-1

となる。

A_{B_{1,l}}

を除いた

A_1, A_2, \cdots, A_N

の選び方は

{}_{N-1} \mathrm{P}_{l-1} N^{N-l}

通りなので、

A_{B_{1,l}}=B_{1,p}

のときの

S_1

の総和は、

{}_{N-1} \mathrm{P}_{l-1} N^{N-l} (p-1)

よって、

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

式が出たので補足終わり。

M

が素数とは限らないので、

{}_{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 の数え上げ定理というものを使うらしい (公式解説)。

N

頂点グラフの頂点への置換は、

N!

個あり、置換ごとに、置換しても同じになるグラフの個数を数えて、平均を取ればいいっぽい。

置換しても同じになるグラフの例はこんな感じ。

置換をサイクル分解したときのサイクルの大きさの列が

(c_1, c_2, \cdots c_m)

であるときの置換しても同じになるグラフの個数は、

置換しても同じ色でなくてはいけないので、サイクルごとに同じ色である必要があるため、 $K^m$ 通り。
置換しても同じになるサイクル内の辺の張り方は、 $\text{pow}\left(2, \left\lfloor \dfrac{c_i}{2} \right\rfloor \right)$ 通り。
置換しても同じになるサイクル間の辺の張り方は、 $\text{pow}\left(\displaystyle\sum_{j=1}^{i-1} \text{gcd}(c_i, c_j) \right)$ 通り。

これらを合わせて、

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)

個となる。自然数

N

の分割をすべて列挙して、各分割に対して (分割がそのようになる置換の通り数) × (グラフの個数) を足し合わせて、

N!

で割ったものが

K

色以下に塗る場合の答え。

K

色 "以下" なので、包除原理で、解である、ちょうど

K

色の場合を求める。

また、分割がそのようになる置換の通り数は、サイクルの大きさが

i

であるものの個数を

s_i

とおくと、

\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

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

Ads

Commutty IT ADS

記事を書いた人に広告収入が入る、そんなエンジニア向けブログサービスに広告を掲載しませんか？