ABC-only 回です。参加できなかったので練習記になります。Eで苦戦したのでたぶんD完だったと思います。
AtCoder Beginner Contest 136
- この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細は問題一覧を参照してください。
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