ABC209

5完。レーティング更新対象でないということで緊張感がなく事前にトイレにギリギリ行かない状態だったが、やはり緊張はしていて直前になってしたくなった(無理にでも出しとくべきだった)。ABを通し、CDを頭に入れてトイレに行った。といっても、Dは読み終わったときには解けていたので考える対象はCのみ。やや難しいとはいえ小考で解けてしまい少しだけ時間を無駄にした。

A - Counting

ABCのAなのに A <= B という条件がない!?と思ったけどサンプルに A > B のケースあった。0とのmaxをとる。

B - Can you buy them all?

シミュレーションする。値引き額は i % 2 でいい。

C - Not Equal

最初は難しく感じる。ていうか前もやったことある問題だと思うんだけど、思い出せないのだ。左から決めていくと、C_iより大きい数を選んだかどうかの場合分けが発生するのでヤバい。

思いつけば簡単。ソートしても答えは同じ(ソートしていない状態で、小さいものから決めていくのと同じ)なので、ソートして小さいほうから決めていく。0とのmaxとる必要あるかなあと10秒くらい考えて自信が持てなかったのでmaxとった。単調非減少の整数列だから、使用済みの個数を引いても前の数と比べて高々1しか減らず、0を飛ばしてマイナスに行くことはないよね。

D - Collision

LCAやるだけなので貼った。あとで順位表を見ているときに気づいたが、距離の偶奇はDFSして深さを持つだけでいい。特に、LCAから根までを往復する距離は常に偶数なので、LCAを求めている意味が全くないという点が悔しい。

E - Shiritori

少し前にどうぶつしょうぎの後退解析を考えてて、(計算時間の節約を考えると)難しいなあと思っていたのだけど、こんな計算量でできるんだね(コンピュータ将棋開発してて知らなかったのかよという話もある)。これが可能であるということが問題からわかるので、解けなくても嬉しさがあるし、通せた(証明したわけではないので解けたという表現でない)のでなお嬉しい。

後退解析をする。負けのノードへ辺が出ているノードは勝ち、勝ちのノードへしか辺が出ていないノードは負け。グラフの有向辺の向きを逆にして持つ。逆にしたグラフで入次数が0のものは負けで確定。それらをキューに入れて処理していく。キューから取り出したノードが負けなら辺を辿って隣のノードは勝ち。取り出したノードが勝ちなら隣のノードのカウントを++して入次数と同じになったら負け確定。勝ち負けが確定したらキューに入れる。キューが空になって確定していないノードは引き分け。各ノードがキューに入るのは高々1回なので、グラフの辺も高々1回辿るだけでよくて高速。

前置++に書き換えたとき元のを消し忘れて1WA。グラフに落とすまでもけっこう混乱した。(26*2)^3個の頂点とN個の有向辺があるというだけの話なんだけど、それがなかなかわからない。グラフに落とせたらどうぶつしょうぎと同じ状況になるので後退解析となる。引き分け(千日手)の扱い、どうぶつしょうぎのほうでもしっかり考えてなかったなと気づかされた。

F - Deforestation

全然わからなかった。考えたことは、最初 1 2 2 2 1 みたいな重みを持ってて、選ぶとそれ掛けるH_iのスコアがもらえて隣から1引くというゲームのスコア最大化。あと、いい感じのポテンシャルがないかと思ったけど何も思いつかず、仮に貪欲に取るみたいな感じだとしたらDAGの入力辺がないものだけ取れるとして何通りの取り方があるかとかこれも解ける気がしなかった。最近は少なくなったけど、たまに「座ってるだけ」になるね。