ABC-only 回です。遅めのE完でした。
AtCoder Beginner Contest 134
- この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細は問題一覧を参照してください。
A - Dodecagon
問題概要: 3 r^2
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc134/submissions/6451648
B - Golden Apple
問題概要: N 本の林檎の木がある。いくつかの木に監視員を派遣する。i 番目の木に監視員をつけると、i-D 番目から i+D 番目の木を監視できる。すべての木を監視するのに必要な監視員の人数の最小値を求めよ。
B: 考察
監視範囲が重ならないように配置するのが最善です。
監視員1人で最大 (2D+1) 本の木を監視できます。監視員の人数 x について x * (2D+1) ≥ N であればよいので、x ≥ N/(2D+1) となる x の最小値、つまり N/(2D+1) の切り上げが答えです。
整数の除算 x/y の端数を切り上げる場合、(x + y - 1)/y と書くとシンプルです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc134/submissions/6451078
C - Exception Handling
問題概要: 長さ N の整数列 A(i) が与えられる。1 以上 N 以下の各整数に対して、A(i) 以外の要素の最大値を求めよ。
C: 考察
例えば A=(3, 1, 4, 1, 5, 9) なら (9, 9, 9, 9, 9, 5) が答えになります。
見て分かる通り、A(i) が最大値でなければ数列全体の最大値が答えで、A(i) が最大値のときは2番目に大きい要素が答えです。
したがって、数列を昇順にソートした数列 B を用意しておき、最大値 B(N) か次点の B(N-1) を出力すればいいです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc134/submissions/6449497
D - Preparing Boxes
問題概要: N 個の箱があり、i 番目の箱には整数 i が書かれている。各箱にボールを1個入れるか入れないかを選ぶ。以下の条件を満たす選び方が存在するか判定し、存在するなら一例を示せ。
条件: 1 以上 N 以下の任意の整数 i について、i の倍数が書かれた箱に入っているボールの総数を2で割った余りが a(i) に等しい
D: 考察
例えば N=9, a=(1, 1, .., 1) なら、以下のようにボールを入れればOK。
1 2 3 4 5 6 7 8 9
0 1 1 0 1 1 1 1 1
1 以上 N 以下の範囲に N の倍数は N 自身しかないので、a(N) = 1 なら N 番目の箱にボールを入れる、a(N) = 0 なら N 番目の箱にボールを入れない、以外の選択肢はありません。
同様に、i > N/2 の範囲の箱に入れるボールの個数は a(i) になります。
箱に入れるボールの数を後方の箱 (整数の値が大きい箱) から順番に決めていけそうです。i 番目の箱にボールを入れるかどうかは、実際に 2i, 3i, 4i, .. 番目の箱に入っているボールの個数と a(i) を比較すると決定できます。
具体的には、i 番目の箱に入れるボールの個数を dp(i) とすると dp(i) = a(i) ^ dp(2i) ^ dp(3i) ^ .. です。
これは一見 O(N^2) になりそうですが、O(N log N) 時間で終わります。
dp(i) を求めるには最大 N/i 回のループを回せばいいので、全体のループ回数は最大で、
N/1 + N/2 + .. + N/N
= N * (1 + 1/2 + 1/3 + .. + 1/N)
になります。カッコ内の和は調和級数と呼ばれていて、O(log N) であることが知られています。(1/5 + 1/6 + 1/7 + 1/8 ≤ 4*(1/8) ≤ 1/2 のように 1/2 以下になるグループを作ると、グループのサイズが倍々に増えるため。)
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc134/submissions/6460524
E - Sequence Decomposing
問題概要: N 個の整数からなる数列 A(i) が与えられる。N 個の要素をそれぞれ1色ずつ色を塗る。以下の条件を満たす塗り方のうち、色数の最小値を求めよ。
条件: A(i) と A(j) (i < j) が同じ色で塗られているならば A(i) < A(j) が成立する
E: 考察
例えば A=(3, 1, 4, 1, 5, 9, 2) なら3色が最小値です。
3 1 4 1 5 9 2
R G R B R R B
適当に2つの要素を取ります。
i j
3 1 4 1 5 9 2
R G R B R R B
上の i, j は同じ色なので A(i) < A(j) が成立していなければいけません。いま 4 < 9 は成立するのでOKです。他の要素についても同様になります。
条件を論理式で書くと、
∀i, j ((i < j and 同色(i, j)) → A(i) < A(j))
となります。これを変形すると、 ((P&Q)→R は P→(Q→R) と同値なので)、
∀i, j (同色(i, j) → (i < j → A(i) < A(j)))
とできて、要するに「同じ色からなる部分列が単調増加」であることを表しています。
やや天下りですが、小さい順に塗っていく貪欲法がよさそうです。以下の操作を繰り返すことで、色の塗り方が1つ構成できます。
- まだ色を塗ってない要素の中で、最小値である最後の要素を A(i) として、これに新しい色を塗る。
- i+1..N の範囲でまだ色を塗っていない要素の中で、最小値である最後の要素を A(j) として、これに A(i) と同じ色を塗る。i = j + 1 として可能な限り繰り返す。
実装はいわゆる range minimum query (RMQ) を繰り返すだけなので、セグメントツリーを貼ると楽です。(久しぶりに使いました。)
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc134/submissions/6471773
ちなみに証明のアイディアが1つ頭にありましたが、反例が構成できたのでお蔵入りになりました。無証明貪欲 