4完。結果は酷いが内容はよかった。
A - Shampoo
ぷよぷよ最強リーグを観てトイレに行って戻ってきてツイートしたら21時を1秒過ぎていた。たぶん15秒くらいのロス。
3人の使用量を配列で受け取り普通にループしてシミュレーション。「B問題と間違えたか？」って思った。しかし解説を見るとループが必要ない解法もある。別に思いつかなくてもいいんだけど、3分以上かけてこれかいというのはある。
B - Hit and Blow
Wordleが出てきた。同じ文字が複数含まれているときの処理（マスターマインドでもWordleでも同じでやや非自明）を思い浮かべて不安になるが、「すべて異なる」と書いてあった。位置が異なるやつは、集合として共通部分のサイズを見てそこから位置が同じやつを引く（この手のでよくある処理）。
C - Collision 2
Yで分けてそれぞれやる。衝突する条件を知るのがかなり難しい。衝突するのはLとRなのでそこから考えると、あるLとあるRが存在してLのが右にあるというのが衝突する必要十分条件。つまりたぶん一番右のLと一番左のRを求めて比較すればいい。XをYで振り分けてしまうと、Sとの対応がわからなくなるので、実装もけっこう難しい。まず普通に入力だけ受け取って、あとはunordered_mapにLの最大値とRの最小値を記録していく。最大値と最小値の初期値に注意。あとはY毎に比較して1個でも衝突するものがあればYes、そうでなければNo。
D - Moves on Binary Tree
一転して簡単そう（楽そう）。Nが小さいのでシミュレーションするだけだが、その過程で番号が64bit整数に収まらなくなるという問題。これは先頭が最上位桁となるようにstackで番号の2進表記を持てばいい（シミュレーションできる）。Xを2進法に変換して、2進法をまたXに戻すのが面倒。
（解説を見て）解法1のやり方は思いついていたが、よく覚えてないけどUが最初に大量にあるやつが消えないとかぼんやり思って捨てた気がする。Uは大量にあってもいいんだよね。あと、このスタック的な消え方がけっこうイメージ難しくて、解説にあるような性質はしばらく考えないとわからない。
E - Edge Deletion
EFGどれも5分くらい使って解けず、この3問を並列に考えていた。
貪欲に削除していくのをまず思いつく。実装したくない。しばらく経って貪欲の正当性を考えるが、思いがけず正しそうだが証明は全然見えない。ワーシャルフロイド法も思い付く。書いてみるが、結局既存の辺に対して更新（あるいは、別の頂点を経由しても同じ）があったか見ることになり、削除する順番に関する知見が得られない。あまりにも何もわからないので、実装して点を得ようとするよりは他の問題を考えたほうが価値が高いと考え、捨てた。
F - Lottery
解けそうに見えて全然わからない。種類数の期待値なら線形性とかでわかるのかな。包除っぽく指定したM個にだけ行く確率とかをやるにしても、ちょっと期待値が求まりそうな形をしていない。
G - Sqrt
DPっぽいけどクソでかいのでまず小さいXに対し愚直（というか2乗のDP）で実験してみる。するときれいな数列になっている。平方数を境にちょっと増えるのは言われてみればなるほど（そこでようやく2項目の数の選択肢が1個増える）。それでも10^9よりでかいので厳しいと思っていたが、2項目はsqrt(X)以下なのでそこまでに現れる通り数はsqrt(sqrt(X))種類くらいしかないことに気づく。これは普通に前計算して累積和とかも持っておけば普通に解けそう。時間も書き切るだけはありそうだったけど、二分探索で平方根求める実装に1億年くらいかかったのと、書き上がっても全然合わないので、全然ダメだった。
（追記）X=1のとき平方根の切り捨てが0になってたのは二分探索の範囲のせい。あと、2乗したら普通にオーバーフローしてたし、半端を数えるのは平方根とったやつに対してだし、半端の個数は1足す必要があった。
