ABC466 参加記
私です。
ABC466 に参加しました。4完です。
C問題は頭の良さそうなアルゴリズムを考えたつもりでしたが、結局尺取りが一番丸かったです。
D問題は実装バグに気付くまで20分溶かしました。
A問題 Compromise
すべての選択肢で嬉しさが負かを判定するだけです。
a.iter().all(|ai| *ai < 0) で終わりです。
B問題 Representative Balls
色ごとの最大値を持てばよいです。最初にすべて で初期化しておき、各ボールを読んだら対応する色の値を max で更新しました。
C問題 Count Close Pairs
久しぶりにインタラクティブです。見た瞬間結構焦りました。が、落ち着いて実装しましょう。
点は番号順に左から右へ並んでいるので、ある left について、距離が 以下になる right は連続した区間になります。そこで left=1, right=2 から始めて、(left, right) を質問します。
Yesなら、leftとrightの間にある点との組もすべて条件を満たすので、right - leftを答えに加えてrightを進めるNoなら、これ以上このleftでは増えないのでleftを進める
各ポインタは高々 回しか進まないため、質問回数は 回以内に収まります。インタラクティブは毎回flushするのを忘れないようにしましょう。
D問題 Placing Rooks
クエリを逆順に見ること自体はすぐ気付きました。
最終状態で残る駒は、その行と列について最後に行われた操作の駒だけです。そこでクエリを逆順に見て、まだ使われていない行と列の組なら答えに加えます。その後、その行と列を使用済みにします。
ここで、row[r] = false と col[c] = false を row[r] && col[c] の条件の中に入れてしまい、それに気付くまで20分溶かしました。駒が残らない操作でも、行と列を消す効果は残るので、毎回更新しなければなりません。
E問題 Range Flip
なーんとなく「カバー何個目なのか」を状態に持つ耳DPを感じましたが、駄目でした。時間が足りませんでした。
おのれ、D問題…
最後に
インタラクティブをコンテスト中に解けたのはちょっと嬉しいです。 実装はもう少し丁寧にやらないとなぁ…
では、また。