5完。コンテストのない土日、バーチャルコンテストをやる機会。面白かった。最初やる気なかったけど、結果的にいい時間をすごせてよかった。
A - Where's Snuke?
入力を受け取りながら、snukeだったら位置を出力して終了。
B - Exactly N points
まず配点の低いものから足していく。N点以上になったところで止める。その最後に足したやつ（K点とする）未満のだけではN点に届かないので、配点の最大値の最小はK以上とわかる。また、N点以上とはいえKを引けばN未満になるのでNをK未満しかオーバーしていない。なので、オーバーした点数の問題だけスキップすればよい。こういう方針で解けそうなのはすぐ見えたけどけっこう混乱した。
C - Interpretation
人と言語を頂点とし、人から話せる言語に無向辺を張ったグラフを考える。条件がかなりややこしいが、UnionFindでいい問題でありそうだ。あとは、人が全部同じ連結成分にあるか見るだけ。
D - Pair Cards
Mで割ったあまりで分ける。Mが偶数かもしれないことに注意（かなりあとになってから気づいた）。同じグループ内か、あまりを足してMになるグループの人としかペアになれない。ということで、あまり毎にカウントしていく。2倍してMで割り切れるときは場合分け。これは同じグループ内でしかペアになれず、また同じグループ内ならペアになれるので簡単。そうでないとき、足してMになる2つのグループそれぞれについて、奇数個含まれる数をカウントする。イメージとしては、同じ数のペアを作れるだけ作ったときの仲間外れだけを取り出す。こいつらは別のグループとしかペアになれないとしてよい。仲間外れ同士をペアにしたら、仲間外れは片方のグループにしか残らない。そいつらは、もう片方のグループの同じ数のペアを崩してペアにする。なんか、ゆるく証明しながらやってたつもりがうまく書けないな。証明できてなかったか。
E - Cookies
RiJで見てからの数日間、Cookie Clickerをやっている。走者がDPを使っているという話題も見た。ということで、（一応知ってたけど忘れており）当たって嬉しい問題。
部分点であればDPできそう。でもかなり単純な構造なので満点もなんとかなるんじゃないかと思う。クッキーを2秒焼いて食べてを40回繰り返せば10^12枚のクッキーは得られるので、食べる回数がかなり少ないとわかる。0秒や1秒焼いてすぐ食べる意味はないので2秒は使うとしていい。DPするにあたり、何回食べたか・使った時間（食べる時間を除く？）・直前に食べた枚数、といった要素を挙げパターンを減らせる要素がないか考える。ここで、K[1]秒焼いて食べてK[2]秒焼いて食べて...K[L]秒焼いてN枚以上という流れを考えると、使う時間と食べる回数を固定したときの最終的な枚数の最大値を求めたくなる。二分探索の匂いもしてくる。実は最終的なクッキーの枚数は単にKの積になっていた。ということで時間を均等に分配して二分探索。答えの自明な上界としてNがあるのでそれを使う。単純に掛け算していくとオーバーフローが心配なのでdoubleで概算してはじいていく。
F - Road of the King
全ての町を通ることが必要条件。最後1に帰ってくるならOK。そうでないとき、最後の場所から1に行けるならOK。列cの最初に1を追加しておくことにして、1212という流れならOK。OKパターンはそれだけではなく、121323もOK。3で終わるとき、最後の1の前に3がなくても、最後の1の前にある2が最初の3の後にあればいいのだ。このチェーンを伸ばして考えるのをかなり長時間やっていたが難しすぎる。方針転換。自由に行き来できるようになった部分に注目する。あと1回だけ移動を残した状態で全ての町を訪れている必要があり、そのとき、町1を含む自由に行き来できる塊とそこから生えた1本の髭に分けることができる。これでDPできそうだが、どうしても4乗になってしまう。解けなかったけど、時間を使い切ることができてよかった。
（追記）4乗のDPを書き切るのめちゃくちゃ大変だった。定数倍がかなりいいことは気づいていたが、実際にサンプルを実行してみて1秒くらいだったので頑張って2倍くらい高速化してから提出して620ms。解説を見ると、単に塊+髭をM回成長させる3乗のDPができるらしい。なるほどなあ。これは逆からやればin-placeでできる。
