A, B, C, D1 の 4 完。+30 くらいで Candidate Master に到達しました。

内容

A. Bingo Candies

すべての飴が同じ数字であるような行・列が存在しないようにできるかを判定する問題です。

同じ種類の飴の個数を数えて最大値が $n^2 - n$ より小さければよいです。

B. Cyclists

手前 $k$ 枚のカードから 1 枚選んで、その数字を足してそのカードを末尾に回すみたいなのを繰り返したとき、総和が $m$ を超えないように最初 $p$ 枚目にあるカードを何回選べるかみたいな問題です。

結構面倒ですが、目的のカードを何回目に取るかを考えていけば貪欲に取るだけで解けます。1 回目に取るときは、手前 $p$ 枚に入っているかどうかを確かめて、2 回目以降は $n - k$ 枚取るのが確定なので、あとはコストを最小にするように動けばよいです。2 回目以降は消費するコストが一緒なのでただ割り算をするだけで ok です。

C. Stamina and Tasks

$n$ このタスクがあって、

• なにもしない (ポイント増加なし、スタミナ消費なし)
• タスクをやる (ポイント $+c_i$、スタミナが $S \cdot \left(1 - \frac{p_i}{100} \right)$) になる

のどちらかを選ぶとき、最終的に得られるポイントを最大化する問題です。

直感的には適当に dp をすればいけそうです。

$\mathrm{dp}(i)$ を $i$ 番目以降のタスクを処理したときに得られるポイントの最大値と定義してあげます。$\mathrm{dp}(n + 1) = 0$ と初期化しておきます。

$i$ 番目のタスクについて

• なにもしないとポイント増加がないので、今後得られるポイントは $\mathrm{dp}(i + 1)$
• タスクをやるとき、ポイントが増加するがスタミナが減るので、今後得られるポイントは $c_i + \mathrm{dp}(i + 1) \cdot \left(1 - \frac{p_i}{100} \right)$

この 2 つを比較してあげればよいです。スタミナは元々 $1$ なのでこれで問題ありません。コンテスト中は何もしない場合、する場合で $\mathrm{dp}(i, j)\ (j \in \{0, 1\})$ でやってましたが、解いた後に考えたらどう見ても 1 次元でいいですね。

D1. Tree Orientation (Easy Version)

無向木があって、各辺について適当に向きをつけていたという状況で、任意の 2 頂点に対する順序対 $(u, v)$ について、$u \to v$ と移動できるパスが存在するか否かが与えられるので、そのような状況を満たすような辺の向きの付け方の存在判定・構築の問題です。

そもそもは無向木なので、最終的に確認すべきことは「向きを考えないとき全体が連結かどうか」です。また、ちゃんと与えられた状況を満たすことも確認しなきゃいけません。

有向辺 $e = (u, v)$ が存在する条件を考えます。まず自明に $a_{i, j} = 1$ を満たしている必要があります。また、任意の $k \neq i, j$ に対し $a_{i, k} = 0$ かつ $a_{k, j} = 0$ のとき、$i \to j$ の通り道は直接行くしかなくなるので、必ず $a_{i, j}$ が存在するといえます。

$n \leq 500$ なので、これをすべての順序対に対して確認できます。その結果、上の 2 条件をともに満たす順序対が $n - 1$ 個あれば、それらをリストアップすればよいです。確認すべきことをしっかり確認する必要があることに注意です。

感想

まずは紫に到達というところで一つの基準を超えられて安心しました。

今回は序盤かなりうまくいったなという印象です。D1 で詰まっちゃったのがかなりもったいないなと思うのと、D2 もっと時間があれば解けた感があるので、中終盤の時間の使い方はもっと考えるべきという感触です。もっと早く手を動かすというところを徹底してやっていきたいですね。

おわり

おわりです。