昨日よりだいぶ調子よかったけど結果は逆。Fは時間内に解けなかったけど最後までワンチャンつかみに行けていた。
A - Five Variables
15から引いていけば答え。Aでこういうの書けると嬉しい。
B - Crane and Turtle
全探索。鶴がi匹なら亀はX-i匹（iは0以上X以下）。
C - Forbidden List
面白そう。そしてけっこう怖い見た目だが、制約がわりと親切で答えは0以上101以下なので、答え候補を長さ102の配列にしてp_iで潰していき、最後に全探索。pair<int, int>に{ abs(X-i), i }を入れてminをとっていくと楽。もっとスマートな書き方はあるかもしれないけど。
D - Not Divisible
A_iが10^6以下ということで、そこが使えないか考える。割り切るというのは約数ということ。自分も含めて全体で約数が1個だけ（自分自身は約数）と言い換えできる。mapとか必要なく、長さ10^6+1のvectorで個数をカウントできる。あとはそれを使いO(sqrt(A_i))かけて約数が何個あるか数えればよい。計算量に√が付くの珍しいなと思ったけどやはりもっと速い解法があるのね。
E - Smart Infants
やばそうな問題。std::setを使えば解けそうではある。解けるので頑張って書く。multi_setも考えたが、まあset<pair<int, int>>でできるのでそっちにした。setの最大要素を見る定石知らないのでゴテゴテ書いて関数にした（O(1)だと思うけどlogが付いてもいいし）。setを2*10^5個持つのは初めてで本当に大丈夫か不安だった。レーティングは不変だが、どの幼稚園に属するかは変化するので別のvectorで更新する（最初更新を忘れてた）。天才感がなく時間ばかりかかる。PASTかよ。
F - Pond Skater
H*Wが10^12になりえると誤読していた。'@'は別途10^6個くらい位置で与えられるという設定で。ただ、サンプルの入力は最初に見たんだよね。そのうえで誤読にしばらく気づかないの意味わからん。
//広い @は縦横斜めに連結する 塊として捉えられそうにも思ったがKがでかいとき疎な配置で地味に邪魔できるな Kが小さくてもか
//広くはなかったｗ
さて、それなら普通にBFSとかもできそうだ。Kがでかいのでそのままだとダメ。ただ全体で10^6マスしかないので、1マスあたりO(1)で処理できれば問題ない。1回探索した場所に行き当たったらそこでやめればいいか。全然解けてないけど、考えを寝かせる時間で実装するの効率がいいので、実装に入る。実装の途中で、探索済みのマスの向こう側に未到達のマスがある場合があることに気づく。そこで、マス毎に4方向のリンクを持つやつを使う。その方向で次に探索すべき場所を更新していく。探索した場所を飛ばす感じでつなぎ直せばいいだろ。とりあえず書きあがったくらいでタイムアップ。サンプルが動かないので惜しくない。これかなりややこしいから準備が必要だった。そもそもこれで解けるかわからんけど。
