LoginSignup
0

More than 3 years have passed since last update.

競プロ参戦記 #56 Sequence Decomposing | ABC 134

Posted at

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つ頭にありましたが、反例が構成できたのでお蔵入りになりました。無証明貪欲 :thinking:

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0