ABCDFGの6完。あのARCの翌日にABCというのも変な感じ。先週のABCよりはだいぶ楽しめた。
A - Double Click
今思うと入力をvectorで受け取ってもっかいループしたほうが楽だったか。入力を受け取りながら初回以外前回と比較。Aはもっと簡単にしてくれ。これはBだよ。
B - chess960
「chess960の条件って本当にこれだけだろうか」とか考えてしまう。これは1回のループでできる。Rの個数をカウントしておきKが来たときRがちょうど1個かを見る。1個目のBの位置を記録しておき2個目のBが来たときに偶奇を比較する。この実装は好き。
C - PC on the Table
1次元の問題がW本並んでいるだけなので1行ずつ受け取って処理して出力していく。明らかに貪欲でいいんだけど、フローが必要な2次元バージョンで貪欲提出してWAになった過去があるのでどうしても見た目で怖くなる。いや明らかとか言ってないで証明しろ。
D - Count Subtractions
gcd貼るだけかと思ってコピペしてきたら思ったよりは違う処理だった。計算量はgcdみたいになる。大小関係が変わるまで割り算ですっ飛ばす。
E - Kth Takoyaki Set
しばらく考えてわからなかったので飛ばした（最近うまく飛ばせてなかった気がしていたので意識して早めに切り上げた）。
Gを通して順位表を見るとめちゃくちゃ通されていて意味がわからない。25分残っていたけど全く解ける気がしないまま終わった。
終了後、ダイクストラ法というのを見て考えると確かに～。合計金額を頂点として、各頂点からはN本の有向辺が出ている。あとはダイクストラするだけ。頂点0から始めて、優先度付きキューからは小さい順に出てくるので0を除いてK個数えればいい。優先度付きキューに入るのはK*N個くらいだから計算量は問題ない。同じ数が出てきたらスルーする必要があることに注意（サンプルで気づいた）（小さい順に出てくるので前回の金額を覚えておくだけでいい）。辺のコストはなんも考えてなかったけど、どの経路も最短距離になる感じに（その距離は金額の数）（最短でないものはpushされないし、最短距離を更新してないときもpushしてるから、同じ数だけスルーっていう処理になる）。
みんなこれ思いついてて俺は思いつかなかったのか。なんなん？bit全探索とか仕切り入れるのとかDFSとかナップサックとか二分探索とか、思いつく典型を掘り下げてダメだった。オーバーフィッティングして思考回路おかしくなってないか？
F - Minimum Bounding Box 2
1次元でさえけっこう難しい。1次元が解けないとこの問題も解けないので考える。端の2個を固定すれば横にずらすのは状況同じだから掛け算でよくて幅を全探索できそう。しかし2次元になると端が色々ある。ここで2次元累積和のイメージが浮かんで、包除がいけそうだと思った。が、よく考えると思ったより複雑。まず横だけ考える。右1列が全部空いてるケースを除きたい。左1列が全部空いてるケースも除きたい。その共通部分が2回除かれてしまうので、右1列と左1列が全部空いてるケースを足せばよさそう。累積和のイメージがあったので、縦横別々にやる方針になった。H*W個、そのサイズの長方形の中に入るのが何通りか求めて、後ろから包除で横方向は端まである場合の数にする。同じことを縦にやる。ややあやしいけどこれはサンプル通ればまあ大丈夫でしょ。AC。
fastestで嬉しい。ほっとけば抜かれるだろうけど、コンテスト中の提出でというのが良い。
G - Constrained Nim 2
実験すると、0がL個並んで次に1,2,3,...がL個ずつというのがR個続いてループという感じ。周期L+Rで単にLで割れば求まる。未証明AC。これ、実験コードをこそ提出したいよね。
