5完。ギリ黄パフォだったけどFを通せないようでは楽しくない。
A - Similar String
問題文の通りにやるのはさすがに面倒なので考察を入れる。'l'を'1'に置き換えてしまっていいと予想。同一視していいかということだと気づくが、よくわからないまま反例思いつかないのでそのまま提出した。結局if文を4行書いてるし、これ楽でミスらない実装を一瞬で思いつくの不可能でしょ。2分以上かかってるし、こんなのコンテスト中にやらせないでくれよ。
B - Discord
不仲である可能性を潰していく。残った可能性をカウント。潰すほうで2箇所やって、カウントは三角形だけ。これは好き。
C - Dash
std::setを使ってシミュレーションするだけなんだけど、体力が負になったら移動先にアイテムがあってもダメ・アイテムは消費される・スタート地点にアイテムがあることもありスタート時点では使われない、といったことを正確に読み取る必要があり、読み取れはしたけれども怖かった。
D - Shift vs. CapsLock
現実のこととして考えると、Shiftと同時に押したほうが速いという場合があるのが罠。脳のアクセラレータを使うとそういう罠にかかるので、何も考えずDPをする。入力する文字は決まっているので、'a'と'A'で場合分けしてさっさと書く。その文字を入力する前にCapsLockをどちらの状態にするかを状態とするDP。入力の合間に2回以上CapsLockを押すのは無駄なので、これでいい。以前snukeさんがやっているのを見た、変数dpと同じ型のpをループの内側に置いて更新したらswapというので書いた。慣れてきた。
E - A Gift From the Stars
簡単そうで、はまるとやばそうな。星をつなげたときの2頂点の次数はどちらも2になる。レベル3以上の中心は次数で検出できる。3以上の次数を列挙して2以下の次数をカウントすればいけそう。いけそうが本当なのか、本当だとして具体的にどうやるか、というのが難しい。で、レベル数+1を全部足したらNになると気づいて解けた。レベル3以上由来の頂点を全部削除するとレベル2由来だけが残る。レベル2は3頂点だから3で割れば個数がわかる。ほんとか？って感じだけど解けてるんだからしょうがない。
F - Damage over Time
二分探索ですねと言って書き始めるがよく考えると判定問題もけっこう大変だ。残りターン数を固定すると、最適な呪文はわかる。さらに考えると、後ろから考えればよさそう。呪文の寄与をグラフにすると、原点から斜めに上がってどこかで平らになる。d_iで降順ソートすればいい。1回の呪文による総ダメージの最大値を更新するたびに書き加えていくとジグザグに上がって最後平らになるグラフとなる。これの積分がいつH以上になるかという問題だ。二分探索ではなく、順番にやって直接求めることができる。まともに計算するには逆から考える必要があって、逆から考えることで問題の性質が変わり二分探索ではなくなる。平らなところはまあ簡単で、斜めのところは二分探索（また別のね）する。境界がかなりややこしいけど頑張る。最後の平らなところも面倒だがちゃんと書く。
これで提出して7WAだった。まあ想定内ではあるけど。ちょっとずつバグり方が変わるように直して提出しても改善しない。終了後、int128というツイートを見て、確かにオーバーフローする場所があった。キャストしたらACした。自分の図だとただの三角形だけど、これめちゃくちゃ縦に長いことがあるんだよね。油断しすぎだ。
G - Bags Game
Fを考えてるときに読んだけど難しそうなので戻った。すぬけ君という3人目が現れるとややこしいので、お金ではなくX-Yというスコアの変動と見れば二人ゼロ和ゲームになる。
（追記）区間DPというキーワードは見ちゃったのでさっさと通しましょう。SWAGも見ちゃったのでゴミすぎるね。確かにそんな感じ。対称なので、手番側から見たスコアでDPする。A円とC円の2つの選択肢があるので配列にする。まず3乗を書こうかと思ったけど、かなり面倒そうに見えるのでいきなりSWAGで。A円払って残ったやつらのスコアはいいとして、自分が取ったやつも計算しないといけないことに気づいた。これは、SWAG側で残ったXの分のスコアを引いておいて、その最大値に今の区間のXの和を足せばいい。前計算から更新していく区間和が2つ現れてきっちり合わせるのが本当に大変。BがN以上になったときも面倒なんだけど、なんかいけた。区間DPをSWAGで高速化というところだけやりたいのに、めちゃくちゃに面倒で、もうACしたからいいやという感じ。
Ex - Constrained Tree Degree
順位表を見てから読むだけ読んだけど考えてない。
