珍しく全完した。理不尽に実装重い問題がないし、面白い問題も多かった。下手したら最近のABCより面白い。7ペナ（うち一つはサブミットデバッグ）で、全完したものの内容はいまいちだった。
A - ドリンクバー/Bubbler
min取るだけ。楽すぎて誤読を疑う。Aはこのくらいがいいと思う。
B - 積集合/intersection
std::set_intersectionを使う。しゃくとりしてもいいけど。
C - 出現回数 / Number of Apperance
r += a == x;
D - 約数/Divisor
愚直。
E - カラフルなTシャツ/Colorful T-Shirts
Fも頭に入れてからトイレへ。PASTバチャは連続する5時間を確保するため直前に食事をとることが多くこうなりやすい。
同じ色の中で一番安いやつだけ見ればいい。mapで解けそうだとは思ったが、これという実装が見えず、トイレで時間もあったのでしばらく考え、安い順にソートして既出の色は飛ばすようにした。unordered_setを使っている。オーバーフローで1WA。
F - 不完全順列 / Incomplete Permutation
これは簡単。'0'が0個ならそのまま、1個なら不可能、2個以上ならrotate。一致しない部分だけでrotateする実装にやや苦労する。temp変数を持っておきswapしていく。最後の仕上げに最初の'0'の場所へ書き戻す処理で'0'が0個のときも未初期化変数でアクセスして書き換えててWA。WAの内容が悪い。
G - K番目の要素/K-th element
数列のK番目の要素と誤読して実装。サンプルが合わず気づく。これは難しい。二分探索する。求める値は、数列に含まれるx以下の数の個数がK以上になる最小のxだ。これ（x以下の数の個数）はxが与えられたらO(N)で求まる。
H - 最短経路/Shortest Path
木なのでN回DFSする。
I - /2 and *3
操作できる回数はどう操作しても変わらない（操作する毎に素因数の2が数列全体から1個減る）。また、その上限まで行うのが最適（余っていたら自分に3倍すれば損しない）。2で割るのと3倍するのは可換なので最初に2で割れるだけ割って回数を記録しておく。あとは数列の中で最小の要素に対して3倍していく。priority_queueを使えばよい。
（解説を見て）64bitに収まるか気にしてなかったな。まあ2を使って1.5倍にしかならないから、初期値の2乗よりは小さそう（全部の積で考えて2乗まで行かなくて平均的に増えていくので）。
J - 数列の反転 / Reverse Array
反転された部分は左右対称になっている。数列の右半分をメインと考え、反転されているときや左半分を出力するときは裏を見るようにする（真ん中で折りたたんだイメージ）（左メインで右は反転させて平行移動のが楽だったかな）。区間加算1点取得ができれば反転回数の偶奇でどっちを見ればいいかわかる。BITを使う。けっこうややこしい。
（解説を見て）ああ、その考え方なら区間加算要らんな。まあやってることは実質同じだけど、自分の実装は重くなってしまった。
K - ニワトリのお見合い / Happy Wedding!
「もちろん」とか言わず普通に説明してよ。仲が悪いとつがいにできないが、仲の良い相手とつがいになっても幸福度は下がることがある。最大流か？片方の幸福度が下がっても相手が上がればつがいにする意味がある。トータルで上がらないならつがいにする意味がない（他のペアを作る邪魔になるだけ）。実装してサンプルが合わず、複数のつがいに含めている場合が普通にあると気づく。やっぱ最小費用流じゃないとダメか。しかし上手く行かなそうだったんだよな。ここで、有名問題っぽいのでググる。ハンガリアン法か。名前しか知らない。しばらく悩んで、最小費用流で考えることに。流量毎にわかればいいのでACLのmincostflowのslopeを使ってみる（初めて使う）。コストは、適当な大きい数から幸福度の増分を引いたもの。slopeの仕様や意味がわかっておらず、コーナーケースに自信がなかったが、提出してAC。
L - K番目の絶対値/K-th Abs
logが2つ付く実装も重い方法しか思いつかないので、新しい発想が出るのを待つために後回し。
Oまでやって戻ってきたが、何も思いつかないのでlog2つで実装していく。BITに乗るよう累積和を座標圧縮し、G問題と同じようにやる。部分列の右端毎に差の絶対値がx以下になる区間に含まれる左端候補の個数をBITで求め、それが初めてK以上になる値を二分探索で求める。なんとTLE。AtCoderでこれがTLEになるんだー。一旦Mへ。
最後の1問。お試しで二分探索が1回で終わるように書き換えて提出すると126ms。まあ二分探索以外にも時間かかってるけど、これを60回やるのは確かにきつそうではある。無限に時間がかかってるとかではなさそうなので定数倍高速化を考えるがあまりアイデアが出てこない。BITの使い回しと二分探索の範囲をA_iの絶対値の和にするの程度。ここで、累積和をソートしてしまってもいいのではないかと気づく。絶対値だから対称だし。Kは2倍にしておく。プラマイxの範囲を二分探索で求めて、自分自身を除くために1を引く（自身は必ず入っている）。これでBITが不要になった。1198msでAC（C++でこれはいわゆる「犯罪」）。残り10分を切っていた。
（解説を見て）あー自分のコードもしゃくとりできる形になってたわ。ソートしたからか。絶対値だからソートできて、ソートしたからしゃくとり法が使えるのかあ。解いてるときは「絶対値だけどただの区間だから簡単」って言い聞かせてたよな。
M - バランス/Balance
木だと勘違いしてたりMを受け取ってなかったり酷かった。さて、一つの頂点の数を決めれば全部決まる。木なら簡単なので閉路に注目する。偶閉路は最初の頂点の数を変化させると1つおきに増えたり減ったりする、1つおきに辺を足して等しい必要がある。奇閉路は解が一つしかなさそう、1周して2だけずれたら1増やせば戻ってくるのが1減って合う。DFSで奇閉路が見つかればそこに合わせてもう一回。必要条件を満たさなければその時点で-1を出力して終了。そうでなくて負の数があれば最小のものを0にしてもう一回。最後にそれでできたものが条件を満たすか確認して出力。WA。
そういえば、0, 10, 0, 10, みたいな辺が続いてたら際限なく大きくなるな。正解はintに収まるとしてもllを使う必要があったかもしれない。WAの個数は変わらず。ここで次の問題へ。
偶閉路と奇閉路の判定が逆だった。DFSで深さの差が偶数の場所へ戻ったら奇閉路。直して提出してWA。落ち着いて見直すと、DFSの開始地点を1か所ミスってた。直してAC。ACしたものの理解はあやふや。
N - ジグザグな数列/Zigzag Sequences
Aは座標圧縮してしまっていい（元の値が必要ないタイプの座圧はABC221Eで見たばかり）。BITを使いながらDP。最初に減るタイプのジグザグをまず求め、Aを上下反転して同じことをもう一回やればいい。BITを2本持ち、直前に増えたか減ったかで分ける。2本が交差する感じでややこしいけど、左からDPしていくだけ。無から列が生えるところは、直前に増えた扱いで毎回1加算する。長さ2以上という条件があるが、長さ0はこの方法だとカウントしておらず、BITに足したもの（さっきの1加算を除く）をそのまま足していけば長さ1もカウントされない（右端毎に足していく感じ）。考察はやや怪しいが短時間でACできた。
O - 色分けトーナメント/Red Blue Tournament
ここまで来ると全ての問題を読めたという安心感がある（この時点でLMが解けてない）。ボス問に相応しい難しさ。セグ木みたいな構造を考える。W_iとL_iがどこで当たるかはセグ木の要領で計算できる。そこで被ったら0通り。2^N-1個の試合枠のいくつかが埋まった状態になる。あとは上から考えていく？そこより下は全部W_iとL_iが勝ってる。特に制約がなければそこ以外は自由に色を決められる。1回勝つ毎に自由度が1減る？上からやるとややこしいので入力を受け取った時点で下からその試合で確定した勝者と敗者を書き込んでいく（矛盾したらそこで終わり）。Pの情報は要らないと思ってたけどW_iがどこかを知るために逆引きは作っておく必要がある。書き込んだ勝者の数だけ自由度が減るので2^Nからデクリメントしていって2のそれ乗が答え。書き込んだ敗者はその下の試合の勝者という情報しか持たないので数えなくていい。考察も実装もやや怪しかったがAC。
