ABC-only 回です。参加できなかったので練習記になります。Eで苦戦したのでたぶんD完だったと思います。

AtCoder Beginner Contest 136

この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 前回: 競プロ参戦記 #57 Digits Parade | ABC 135
問題の詳細は問題一覧を参照してください。
- 問題一覧: https://atcoder.jp/contests/abc136/tasks

A - Transfer

問題概要: 水を入れる容器が2つある。容器1には水が最大 A ミリリットル入り、いまは B ミリリットル入っている。容器2には C ミリリットル入っている。容器2から容器1に可能なかぎり水を移した後、容器2に入っている水の量を求めよ。

A: 考察

移せる量を x とします。元々の水量から条件 x≤C が必要です。加えて、容器1の容量から条件 A+x≤B すなわち x≤B-A も必要です。したがって x = min(C, B-A) が最大値になります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc136/submissions/6772223

B - Uneven Numbers

問題概要: 整数 N が与えられます。N 以下の正の整数のうち、10進展開の桁数が奇数であるものを数えよ。

B: 考察

例えば N=31415 なら5桁の数 (10000から31415) と3桁の数 (100から999) と1桁の数 (1から9) を数えればよいです。

計算できそうですが、N が小さいので、実際に N 以下の各正整数の桁数を数えて奇数か判定する方が安定です。

桁数は、10 で繰り返し割ったとき 0 になるまでの回数で求まります。(文字列に変換して長さを調べる方が楽だったかも。)

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc136/submissions/6772260

B: 高速解法

せっかくなので、より高速な解法を考えます。

いま桁数が重要なので、整数を桁ごとに分類しましょう。

    1桁   1..  10
    2桁  10.. 100
    3桁 100..1000
    ..

これにより桁数が奇数か否か容易に判定できるようになりました。

桁数が奇数である各類に含まれる N 以下の整数をカウントすればよいです。類の範囲を x..y とすると、カウントすべき範囲は x..y と 1..N+1 の共通部分なので、x..min(y, N+1) です。

1桁ずつ大きな類を試して、N 以下の整数が含まれない類 (最小値が N を超える類) が出現したらそこで終了できます。O(log N) 時間です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc136/submissions/6890814

C - Build Stairs

問題概要: N 個のマスが一列に並んでいる。i 番目のマスは高さ H(i) である。各マスにつき、そのマスの高さを 1 減らしてもよい (減らさなくてもよい)。操作の後、マスの高さを単調非減少にできるか判定せよ。

C: 考察

H が単調非減少 (単調増加) とは、すべての i について H(i) ≤ H(i+1) が成り立つことです。

H(i) の値がなるべく小さい方が条件を満たしやすいので、H(i) の高さを減らしても単調増加のままになるなら、減らした方がよいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc136/submissions/6882986

D - Gathering Children

問題概要: N 個のマスが一列に並んでいる。i 番目のマスには L または R の文字が書かれていて、1人の子供がいる。ただし 1 番目のマスには R が、最後のマスには L が書かれている。以下の操作を 10^100 回行なった後、各マスにいる子供の人数を求めよ。

操作: 各子供は、自分のいるマスに L が書かれているなら左隣のマスに移動し、R が書かれているなら右隣のマスに移動する。

D: 考察

入力例2をやってみると以下のようになります。各マスにつき左のマスが R なら増加、右のマスが L なら増加、と考えればよいです。

    t | R R L L L L R L R R L L
    0 | 1 1 1 1 1 1 1 1 1 1 1 1
    1 | 0 2 2 1 1 0 1 1 0 2 2 0
    2 | 0 2 3 1 0 0 1 1 0 2 2 0
    3 | 0 3 3 0 0 0 1 1 0 2 2 0
    4 | 0 3 3 0 0 0 1 1 0 2 2 0
    .. (以下同じ)

十分な操作回数の後、R L の部分にすべての子供が集まることが分かります。そのため、他の部分の子供について以下を考えればよいです。

どの R L に合流するのか
R L の左側に入るのか、右側に入るのか

各 R L 部分からの視点で考えると分かりやすいです。合流するのは R L 部分から見て左側に連続している R R .. R の子供と、右側に連続している L .. L L の子供です。

R L 部分の R, L の位置に初めにいた子供をそれぞれ X, Y とします。X, Y は操作ごとに入れ替わるので、X, Y のどちらと合流するかは X との距離の偶奇で決まります。例えば R R R R L では左の3人の子供はそれぞれ Y, X, Y と合流します。形式的にいえば、X との距離が偶数なら X に、奇数なら Y 側に合流します。

実装もこの通りにやればよいです。R L の部分を探して、その左側にある R を列挙し、右側にある L を列挙します。2重ループですが、各マスを2回ずつ処理するだけなので全体としては O(N) 時間になります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc136/submissions/6772675

E - Max GCD

問題概要: 長さ N の整数列 A が与えられる。以下の操作を最大K回まで行なった後、A のすべての要素を割り切る最大の正整数を求めよ。

操作: i, j (i≠j) を選び、A(i) を1増やし、A(j) を1減らす

制約: N≤500, A(i)≤10^6, K≤10^9

E: 考察

答えとなる最大の正整数を G とします。操作が終わった後、A の要素はすべて G の倍数なので、A の総和も G の倍数です。操作の前後で A の総和は変化しないので、G の候補としては A の総和の約数だけ考えればよいです。

A の総和の約数 d を大きい順に試し、「最大K回の操作によって A のすべての要素が d の倍数にできるか」を判定するという問題になります。

A の要素を d の倍数にするとき、1つの要素に対して +1 する操作と -1 する操作を行うのは無駄です。以下のように1つの操作にまとめられるからです。

    a b c          a b c
    - +      →       + -
    +   -

したがって、A の要素を「+1 操作を繰り返して d の倍数にするもの」と「-1 操作を繰り返して d の倍数にするもの」に分類すればよいです。分類したときの操作回数の最小値が計算できるので、それが K 以下になるかどうか判断します。

メモ化再帰で解けそうなので DFS を考えました。

設計:
    dfs(i, p, m) = k :
        +1 操作を p 回、-1 操作を m 回行なうことにより、
        A の前から i 個を d の倍数にしたとするとき、
        残りの操作回数の最小値が k に等しい

基底ケース:
    dfs(N, p, m) = 0 (p = m)
    dfs(N, p, m) = ∞ (p ≠ m)

帰納ケース:
    dfs(i, p, m) = min(
        // 加算して d の倍数にするケース
        dfs(i + 1, p + (d - A(i) % d), m) + (d - A(i) % d),

        // 減算して d の倍数にするケース
        dfs(i + 1, p, m + A(i) % d) + A(i) % d
    )

p, m は最終的に p = m になるかだけが問題なので、x = p - m で変換することで計算量を落とせます。

x の範囲を考えると、1ステップごとに ±d だけ増減するので、|x|≤O(N d)です。d の最大値は M = N・ΣA(i) ≒ 5×10^8 ですが、全体としては調和級数が出てきて O(M log M) で抑えられそうな 気がする。

とりあえず投げてみたら AC になりました。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc136/submissions/6870958

模範解答

解説 PDF によると、実はメモ化再帰でおおざっぱに計算しなくてもよくて、「小さい値は -1 、大きい値は +1 で d の倍数にする」という方針を取ると、累積和で解けるようです。

解説AC: https://atcoder.jp/contests/abc136/submissions/6873382