A, B, C, D, E1 の 5 完。レートが +116 で爆盛でした。

内容

A. 1-1

左右に隣接するマスが両方 1 であるマスの数字を 0, 1 のどちらかに自由に設定できるという条件下で、文字列中の 1 の個数を最大化・最小化する問題です。

特に何も証明していないのですが、直感的にはとりあえず 1 をできるだけ増やしてから、その状態からなるべく 0 を増やすようにすれば最大値と最小値が分かるよなという気持ちで実装して通りました。

B. One Night At Freddy's

敵が $m$ 体いて、$l$ 秒間の中で 1 秒ごとに敵側は一人選んでその人のレベルを $1$ 上げることができます。一方、こちら側は $n$ 回行動を起こせて、$i$ 回目は $a_i$ 秒立ったときに敵側を一人選んでその人のレベルを $0$ にできます。$l$ 秒経った後の敵のレベルの最大値を最小化したいという問題です。

今回解いた問題で一番難しかった気がします。とりあえず直感的にわかること :

• こちら側がレベルを $0$ にする敵は、その時点で最大値を持っている敵を選べばよい
• こちら側が行動を起こせる回数 + 1 体分に対して操作を考えればよいので、$m$ がその数より大きい場合は、その時点でレベル最小値を持つ敵はこれ以降考えなくてよい。

なんか全体的にレベルを上げていくのが良いのかなと思って、こちら側の行動の間の時間に増やすレベルの割り当ては候補のうち小さい方から順にやっていったらなんか通ったんですが、なぜこれでいいのかは証明していません。

C. Where's My Water?

プールみたいなのがあって、排水口を Max で 2 個置けます。排水口から出る水は、排水口まで上方向への移動 (左上・真上・右上) を伴うことなく動けるマスの水であるとき、出せる水の量を最大化したいという問題です。

排水口を置く位置は土の上であるとしてよいです。そのため、$n$ 列のうちどこの列に排水口を置くかが問題になりますが、これは良い感じに木を作って dfs すれば解けます。木は Cartesian Tree みたいに構築すればよくて、簡単に構築できます。

昼に ICPC の順位表見ていて、日本チーム以外では特に NYCU_CartesianTreeII を応援していたのでおかげさまですぐ頭に出てきました。NYCU_CartesianTreeII ありがとう...

D. Boxed Like a Fish

木上を根から移動し、葉まで行きたい人がいます。一方で、一つの辺を選び、$k$ ターンだけ封鎖することを繰り返せる人がいます。この状況で、確実に葉にたどりつけるかを判定したいという問題です。

bottom up を考えます。葉まで確実にたどり着ける頂点を valid な頂点と呼ぶことにします。求めたいのは、根が valid か否かです。葉は自明に valid です。

最初は、妨害役の人がつねに 1 つの辺を妨害している状態でなければいけないと思っていたので、深さが $k$ の頂点だけ気を付けて適当に dfs すればよいと思っていたのですが、そこで誤読をしていたようです。+1 penalty です。

要するに、妨害している辺が無い時間があっても良いということなので、これだとサンプルの最後のケースで $v = 4$ だったときに落ちてしまいます。

結論から言うと、2 つの valid な頂点であって、その頂点間の距離が $k + 1$ 以下であるようなものが存在すればよいです。2 頂点間の path だけを考えると、一番端の辺を封鎖したところで、残りの部分の path を $k$ ターン中に移動しきることができます。

それを加味して dfs すると、通りました。実装では今見ている頂点から子までの距離を加算していないので min1 + min2 <= k - 1 が判定条件になっています。

E1. N-MEX (Constructive Version)

配列 $b = \{b_i\}_{1 \leq i \leq n}$ であって、任意の $1 \leq i \leq n$ に対し、$\left[b_1, ..., b_i\right]$ の $(n-i+1)$-mex が $a_i$ であるようなものを構築する問題です。

まず、そのような $b$ が存在しない条件を考えると、次のようになります :

• $a$ が単調非増加でない。
• $a_1 = n - 1$ または $a_1 = n$ のどちらでもない。
• $a_i < n - i$

逆に、これらをすべて満たさない $a$ に対しては、そのような $b$ を必ず構築できます。$a$ に登場しない数を列挙して、$a_i = a_{i - 1}$ であれば $b_i$ は登場しない数のうち最大のもの、そうでなければ $b_i = 1e9$ みたいにダミーを置くなどすれば構築できます。

感想

解く順番考えないといけないなと思いました。たぶん B を後回しにしていたら、もっとレート伸びて Candidate Master 入れたのかもわかりません。難易度感をちゃんと把握しておくのは ICPC では特に大事なのでちゃんと鍛えないといけないなと思いました。

おわり

おわりです。