6完。Fまで簡単だなーと思ってたらなんかいい順位だった。Gが難しかったので、完全に運だけど橙パフォで黄色復帰。
A - Pawn on a Grid
'#'を数える。Aはもっと簡単でいいよ。このくらいなら俺の負担にはならないけど。
B - Inverse Prefix Sum
累積和を取ったあとの列が与えられるので元のを復元せよという問題。累積和を作る手順を想像し、それを逆からやっていく。後ろから引き算していく。考察難度はけっこう高いけど、自分にとっての考察/実装の負担は小さく、ありがたい。
C - Extra Character
サンプルを眺めると、左から見て最初の違う場所がどこかわかればいい気がする。さすがに怖いのでちゃんと考える。Sの文字数をNとする。まず、挿入したのが末尾だったときはN文字全部一致する。次に、末尾に挿入した可能性がないときを考える。N文字の中にどこか一致しない場所が必ずある。さて、S[i]はT[i]かT[i+1]のどちらかと一致する。S[i]とT[i]が異なるならS[i]とT[i+1]は一致する。この「一致する」は、文字として等しいだけでなくT[i+1]がSのどこ由来かというのまで含めて一致している。よって、そこから右全部1ずれて一致しているはず。ということで提出。これも実装は軽かった。
解説放送や解説（狭義の）を見ると色々明快な考え方があるんだな。
D - Factorial and Multiple
直前にトイレは行ったけどまたしたくなって、CDを開いてDを読んでからトイレに行った。難しい問題をトイレで考えることができて運が良かった。
Kが大きい素数である場合はNも大きくなる（素数Kが含まれる正整数はK未満にはない）。一方でK=2^30みたいな場合はNをどこまで大きくすればいいかまた別の考え方をする必要がある。難しい。さて、Kを素因数分解すれば、素因数毎に考えて最大値をとればいい。じゃあ素数PがC個含まれているときは1からいくつまで掛ければいいか。よく考えると、素数Pが含まれるのはPの倍数のみだ。Cも小さいので、単にPの倍数を小さい順に見ていってPが含まれていた個数をCから引いていって何個目で0以下になったかを求めればいい。break忘れで無限ループになってしまいデバッグにてこずった。
E - Critical Hit
めちゃくちゃ簡単に見える。実際、残り体力で単純なDPをするだけ。残り体力0のときと1のときは自明で、2以上のときは貰うDPでNまでやる。
ひやー、解説の方針1のコード（の解法）すげえな。その体力値を経由する確率を順に求めていくことができる。現在の位置をスキップするのは1個前の位置から2ダメージ与えた場合のみなので1個前の確率だけで求まる。まあこれは思いついたとしてもけっこう難しいので、コンテスト中はかんたんDPをしたほうがいい。
F - Pay or Receive
こんな制約でできるのかって一瞬思うけど、これはポテンシャルだ。大まかにはすぐ解けたけど、細かいところを時間かけて詰めていく（わりと実装に頼って詰めていく）。多重辺や自己辺が怖いけど、到達できるかはUnionFindで簡単。次にグラフでDFSしてポテンシャルを求めていく。訪問済みの頂点に当たったら、ポテンシャルに矛盾があれば記録する。UnionFindのリーダーのインデックスでその情報を管理する。矛盾があればそこをグルグル適切な方向へ回ればいくらでも稼げるからinfだし、そうでなければどんな経路でも結果は同じなのでポテンシャルの差を出力する。矛盾してたらリーダーの自分との差を0じゃなくしておいて判定に使う。
言われてみれば確かにポテンシャルはUnionFind内で管理できた。
（追記）実装してみたら思ったより難しかった（何が「管理できた」だよできてから言え）。mergeするときに全体を書き換えるわけにいかない（マージテクを思えばいかないは言い過ぎか）ので、ポテンシャル自体を持つのではなく親との差分を持つ。リーダーにつなぎ直すとき、同じくつなぎ直した親のポテンシャル（リーダーの直接の子になったので差分がそのままポテンシャルになっている）を見て計算できる。mergeは、リーダーを求めるときにポテンシャルもわかるのでその差を考慮してつなげる。
G - Do Use Hexagon Grid 2
一目めちゃくちゃ簡単そう。しかしびっくりするほど解かれていない。「どの2マスの距離も」だから難しいのか。ある大きさと形の六角形の領域内なら条件を満たすって言えそう（あやしいけど）。選ぶ点のうち最も左にある点をN通り固定したらいいのでは？ただ、その点が六角形のどこにあるかはそれほど絞れない。ただ、Nが小さいのでO(N)通りくらいうまくスライドさせてできてもおかしくはないなあと思う。ただまあ具体的な実装に向けて手が動くということはなく、夢物語だけ。
