6完。競プロer、DPが得意なやつしかいねえ。俺も得意だけど競プロerほどではないので負けた。
A - Find Takahashi
値ではなくインデックスを答えさせる問題。けっこう迷って、std::pairの最大値をとった。今思うと2回ループする方法はあったな。
え、解説の、最大値を持たずh[ans]で最大値を得る方法初見なんだけどｗ
B - ABC-DEF
modintを使えばいいが、問題は入力。6回も特別な処理を書けないのでループで受け取った。
C - Counting Squares
「軸に平行な」とか書かれてないのでかなりやばそう。実際サンプル1で45度ではない斜めの正方形が出ている。4点を全探索も一応間に合いそう。ただ、ひし形の判定は楽でも長方形の判定は内積とかになって若干面倒。もう少し考えると、回転方向を決めて順に見ていけばよさそう。サイズ0の正方形を作らないように注意。始点と次の頂点へのベクトルを決めて、同じ方向へ90度曲がりながら4点を生成する。その4点がこのボード上にあって'#'なら正方形。重複を除く方法は、最も上（上下位置が同じなら最も左）の頂点を始点にするとかも考えたけどかなり面倒なことになりそうなので、全部数えて4で割った。一つの正方形に対しちょうど4回カウントされる。
D - Yet Another Recursive Function
Nが大きいので、どうせ実験して規則性を見つけて数学的帰納法で示すんだろと思い実験すると、同じ数が不規則に連続していてかなりヤバい。ここで普通に問題文の通り再帰することを思いつく。計算量を考えるがダメそう、実験してもやはりダメ。そこで過去に出題されたものを思い出してメモ化再帰なら通るやつかと思いやってみるとNが大きくても関数呼び出し回数は少なかった。意味がわからないので提出してAC。
改めて考える。再帰の深さはO(log(N))。1/2側と1/3側で呼び出した回数が同じなら同じ場所に行くと仮定すればO(log(N)^2)だ。実際には切り捨ての具合とかでそうならないかもしれない。よく考えると値は小さくなっていくから一致しやすい気がする。いやまてよ、これ割る順番に依らないのでは。桁の位置によって2進か3進か変わる表記があったとして、2進になってる位置の個数さえ同じなら、10回割った結果は下位10桁を取り除いたものだ。
E - Sugoroku 4
なんか競プロ典型（行列累乗はできないなーとか）ばっか考えて、すごろく典型を忘れていた。あと1回でゴールできる位置に来たらそこからは簡単（毎回1/Mの確率でゴールしてそれ以外は状況が変わらない）。Mが小さいことには最初から注目していたのに、普通のDPがなかなか見えなかった。最初に「あと1回でゴールできる」になった時刻で場合分けして、そこに入ったものを答えの確率に足して消す。最初から「あと1回でゴールできる」ことはある。初回で引き返すことはない。この辺りがややこしくてかなりの時間を使った（得意な問題だと思っていたのに）。
そういえばすごろく典型すら使わず普通にDPできるな。マジ？いやー、引き返す動きがこれまでなぜかABCで出てなくてそこに注目してしまったが、無限ループがないからえらく簡単だったんだな（実装が簡単とは言ってない）。
F - Erase Subarrays
正面から行って、しゃくとりで列挙とか色々考えたけど、結局DPかーい。最初のi個を見て残ったやつの総和がjになるときの最小の操作回数でDP。操作回数がjになるときでDPとか一瞬考えて混乱。遷移は、a[i]を使う場合は単にj-a[i]から持ってくる。削除して終わる（a[i]を使わない）場合は、同じ和のこれまでの最小値まで戻ってそこまで全部削除すればよい。ここが愚直に書くと計算量ダメだけど、単純な構造なので何とかなると思って書き進めていた。和の各値について最小値を更新していくだけでよかった。これで解けているのだが、細かい部分（添え字の1違いとか）を詰めることが全然できていない。そのためには膨大な時間が要る。なので、手癖で書いてサンプルが合ったら提出した。ACだった。
G - Infinite Knapsack
Eまで通したらFGを開いてFを読み解けそうなら解いてそうでないならGを読むといういつものムーブ。しかし今回はGが魅力的（面白そう、思わず考えたくなる）でGを優先した。いやこれ時間足りねえよ。FGどっちもやりたくて振動してしまう。パッと見簡単そうだけど順位表見てたまげた。たしかに難しい。下位互換のやつを捨てて、どんな形に並ぶのかも言われてみるとよくわからない。二分探索できるのかな。
（追記）解説見て凸包はなるほど。2個選んでそれを結んだ線分の上は作れるので。単に下位互換をはじくだけじゃなくて、線分のあっち側のも要らなくて凸包になる。あとは線分上のどこを選ぶかだけど、頑張って数式をやる。凸包部分もかなり苦戦した。
