「うそお」って思った。これで100位以内かあ。EFが、やるだけでもあり、しかしかなり癖があり、自分の得意セットだったということか。競プロ長いので経験が生きるねABCは。
A - Slot
比較2回を書いたが、上手い方法あるかな。YesNoじゃないのやめてくれ。今回はWonとLostを手打ちしたが、サンプルに両方あるので書き間違いは検出される。
B - Alcoholic
Xを100倍しておいて、V * PをXから引いていく。
C - Mandarin Orange
実行時間制限が1.5秒でN=1万でO(N^2)っぽい。どういうことだ。そして面白い問題をCに置かないでくれ。時間計算量を減らせないか考えたくなってしまう。まあ2乗で書いた。ゆーてその実装もそこそこ難しく時間をかけてしまった。左端を全探索すると決めるまでも時間がかかった。左端を決めたら最小値を更新しながら右端も全探索（最小値 * 区間の幅）。
（追記）解説放送を見た。UnionFindを使うのマジか（自分はstd::setとかで区間を分割していくのを考えていた）。実装も軽いし計算時間もソートとUnionFindくらいなのでlogが付く中では軽い。そしてスタックを使うO(N)。これはABCのFに出そう。自分で思いつくのは無理だろうなあ。この2つを実装して通し、最後にstd::mapで区間を管理するのを書いた。コード量は多くないが、本番でやるとめちゃくちゃ時間食いそう。
D - Logical Expression
Dらしいいい問題。演算は左から順にかけていく。ということで、演算をi回かましたときのTrueとFalseそれぞれの通り数でDP。なんか3倍っぽいのが出てきて不安になってullを使ってしまった。よく考えたらTrueとFalse足してきっかり2^(N+1)だった（DPにアウトソーシングしてしまって、自分が何を数えているか忘れている）。なおllで扱えるのは2^63-1まで。
E - Rotate and Flip
簡単そうだけど具体的にどうやるか。行列で表現して累積積を持てばいいか。答えもllに収まる（対称な位置に移動しても高々2*pしか絶対値増えない）から行列も大丈夫だろう。回転に気を取られて平行移動を忘れていたが、ベクトルのサイズを2から3に増やして(x, y, 1)みたいにすればできる。行列を紙に4つ書き、それをプログラムに転写。振り返ればやるだけなんだけど、色々と理解が抜けてて細かく時間を削られ続ける。まあ自分にしてはそこそこ速かった。
（追記）形が変わらない（(0, 0)と(1, 0)と(0, 1)の移動先を見れば全体がどう移動したかわかる）ことに考えが至らなかった（行列で殴れるとはいえ）。
F - Sugoroku2
問題を読むと、かなり簡単そうなDP。ああ、「振り出しに戻る」が厄介なのね。マスNを越えてもゴールなので、双六にMマス追加する。幅Mの区間の期待値の和を持って更新しながらやればいい。いいやり方があるかもしれないけど、答えをXとして各マスの期待値を後ろからAX+Bの形で求めて最後マス0でAX+B=Xという方程式を解いて解がなければ-1を出力。誤差が気になったけどけっこうゆるい制約なので適当に提出したら通った（ちゃんと考えたい）。
（追記）誤差はかなり甘く考えていた（累積和を更新しながら使うという最も危ない実装をした）。そもそもコンテスト中は「振り出しに戻る」で答えがめちゃくちゃでかくなることを認識してなかった。AX+B=XのAが1にとても近くなりうることを認識してなかった。引き算が必要な累積和に代えてセグ木を使うという方法を知らなかった。ゴールできないことの判定は「振り出しに戻る」がMマス以上連続しているかでできるが、それを考えようとしなかった。
