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

ABC-only 回です。遅めのE完でした。

## AtCoder Beginner Contest 134

- この連載記事では、着手した問題の考察を自分なりに書いていきます。
    - 前回: [競プロ参戦記 #55 Rain Flows into Dams | ABC 133](https://qiita.com/vain0x/items/463c56a6d9af5c0249ab)
- 問題の詳細は問題一覧を参照してください。
    - 問題一覧: https://atcoder.jp/contests/abc134/tasks

## 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_face: