AtCoder Beginner Contest 172 感想 - スコルの知恵袋

感想

ABCの三完で惨敗......。ABCで三完なんて久しぶりだなぁ。

解けなかったDは緑diffらしい。めちゃくちゃくやしい。

A - Calc

$1 \le a \le 10$ なので、何も気にすることは無い。

提出コード

void solve() {
    ll a;
    cin >> a;
    cout << a + a * a + a * a * a << "\n";
}

B - Minor Change

$S_i \neq T_i$ となる $i$ の個数を数える。

提出コード

void solve() {
    string S,T;
    cin >> S >> T;
    ll cnt = 0;
    for (ll i = 0; i < (ll)S.size(); i++) {
        if (S[i] != T[i]) {
            ++cnt;
        }
    }
    cout << cnt << "\n";
}

C - Tsundoku

机Aの本を読む冊数を固定すると、机Bの本をどこまで読めるかは $B_i$ の累積和の上で尺取りか二分探索をすればすぐに求められる。

コンテスト中はまず尺取りで実装しようとしたが、バグらせまくって結局二分探索で解きなおす羽目になった。

「これにぶたんで実装すれば一瞬やなぁ......」とか思いながら尺取りをバグらせ続けたのマジで草（真顔）

提出コード

void solve() {
    ll N, M, K;
    cin >> N >> M >> K;
    Vl A(N), B(M);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (ll i = 0; i < M; i++) {
        cin >> B[i];
    }
    Vl cumA(N + 1), cumB(M + 1);
    for (ll i = 0; i < N; i++) {
        cumA[i + 1] = cumA[i] + A[i];
    }
    for (ll i = 0; i < M; i++) {
        cumB[i + 1] = cumB[i] + B[i];
    }
 
    ll ans = 0;
    for (ll i = 0; i <= N; i++) {
        if (cumA[i] > K) {
            break;
        }
        ll idx = upper_bound(cumB.begin(), cumB.end(), K - cumA[i]) - cumB.begin();
        ans = max(ans, i + idx - 1);
    }
 
    cout << ans << "\n";
}

一応尺取りでも解いておいた。

ちなみに実行時間は二分探索→54ms 尺取り→52ms。logは定数！！！

コンテスト後提出コード(尺取り)

void solve() {
    ll N, M, K;
    cin >> N >> M >> K;
    Vl A(N), B(M);
    for (ll i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (ll i = 0; i < M; i++) {
        cin >> B[i];
    }
    Vl cumA(N + 1), cumB(M + 1);
    for (ll i = 0; i < N; i++) {
        cumA[i + 1] = cumA[i] + A[i];
    }
    for (ll i = 0; i < M; i++) {
        cumB[i + 1] = cumB[i] + B[i];
    }

    ll ans = 0;
    ll idx = M;
    for (ll i = 0; i <= N; i++) {
        if (cumA[i] > K) break;
        while (idx >= 0 && cumA[i] + cumB[idx] > K) {
            --idx;
        }
        ans = max(ans, i + idx);
    }
    cout << ans << "\n";
}

D - Sum of Divisors

解けませんでした......。

何も思い浮かばず、試しに愚直に素因数分解をして解くコードを書いて手元で試してみるも、当然間に合いそうになく提出を断念......。

結局、エラトステネスの篩っぽく約数を数えれば $O(N \log N)$ で済む。C++なら N = 10⁷ でも $O(N \log N)$ 解が余裕で間に合う(112 ms)。はやい！！！

また、解説PDFにあるように、等差数列の和を考えることで $O(N)$ にできるらしい。

「まとめ方を変えて総和を求める」という典型を思いつくことができず、かなしい。

コンテスト後提出コード

void solve() {
    ll N;
    cin >> N;
    ll ans = 0;
    for (ll i = 1; i <= N; i++) {
        for (ll j = i; j <= N; j += i) {
            ans += j;
        }
    }
    cout << ans << "\n";
}

E - NEQ

Dをあきらめて挑むものの、残り15分程度しか残っておらず解けなかった。以下、解説PDFを見た後の考察。

「 $1 \le i \le N$ なる任意の $i$ について $A_i \neq B_i$ 」を条件1、「 $1 \le i \lt j \le N$ なる任意の $(i, j)$ について $A_i \neq A_j$ かつ $B_i \neq B_j$ 」を条件2とする。条件2は要するに数列の中に同じ要素は2つ以上含まれないということ。

以下、条件2を満たす $(A, B)$ だけを考えて、その集合を普遍集合とする。

$C_i$ を「 $A_i = B_i$ である $(A, B)$ の集合」とする。求める答えは次式のように表される：

$\displaystyle{ ans = \left| \overline{C_1 \cup C_2 \cup \cdots \cup C_N} \right| = \left( {}_M \mathrm{P}_{N} \right)^2 - \left| C_1 \cup C_2 \cup \cdots \cup C_N \right| }$

$D = \left| C_1 \cup C_2 \cup \cdots \cup C_N \right|$ とおくと、包除原理より

$\displaystyle{ D = \sum_{i_1} \left| C_{i_1} \right| - \sum_{i_1 \lt i_2} \left| C_{i_1} \cap C_{i_2} \right| + \sum_{i_1 \lt i_2 \lt i_3} \left| C_{i_1} \cap C_{i_2} \cap C_{i_3} \right| - \cdots }$

ここで、解説PDFで述べられている議論より

$\displaystyle{ \left| C_{i_1} \cap \cdots \cap C_{i_k} \right| = {}_M \mathrm{P}_{k} \times \left( {}_{M-k} \mathrm{P}_{N-k} \right)^2 }$

であり、これを使って $D$ を整理すると

$\displaystyle{ D = \sum_{k=1}^{N} (-1)^{k+1} {}_N \mathrm{C}_{k} {}_M \mathrm{P}_{k} \left( {}_{M-k} \mathrm{P}_{N-k} \right)^2 }$

を得る。上式を使うと $D$ はコンビネーションとパーミュテーションの前計算と合わせて $O(N + M) = O(M)$ で求められ、解を得ることができる。

コンテスト後提出コード

// ModInt, ModComb 略

constexpr ll MOD = 1000000007;
using Mint = ModInt<MOD>;
 
void solve() {
    ll N, M;
    cin >> N >> M;
 
    ModComb<MOD> mc(M);
 
    Mint ans = mc.perm(M, N).pow(2);
    for (ll i = 1; i <= N; i++) {
        Mint t = mc.comb(N, i) * mc.perm(M, i) * mc.perm(M - i, N - i).pow(2);
        if (i & 1) {
            ans -= t;
        }
        else {
            ans += t;
        }
    }
 
    cout << ans << "\n";
}

F - Unfair Nim

問題を見てすらいないので割愛。