ABCDFの5完。体調悪かったけどスムーズに早解きできていた。Eが全くわからなかったね。
A - Generalized ABC
簡単でいいね。
B - Let's Get a Perfect Score
Mが30以下なのでビットで管理すると楽。
C - String Delimiter
またぐたびに内側か外側かが入れ替わる。
D - Make Bipartite 2
見た目のわりに重くてびっくりする。まず、二部グラフであってほしいときに、辺の追加は損しかない。連結と限らないので各頂点を訪れたかのフラグを持って各頂点からDFSする。二部グラフでない連結成分があれば答えは0。全体が二部グラフだったら、同じ連結成分同士と違う連結成分同士に分けて追加する辺を考える。同じ連結成分同士は、2色に塗り分けて頂点数がx個とy個だったらx*y本の辺を持てる（元からあった辺の数を引くのを忘れてサンプル通らず）。違う連結成分同士（どこに辺を追加しても二部グラフのまま）が厄介そうだが、現在の連結成分より前に見つけた連結成分と結ぶ辺の数を足していくだけでいい（これまでに見つけた連結成分内の頂点数の和だけ持っておく）。
E - Choose Two and Eat One
DPしようにもそれまでに何を使ったかで状況が変わるからbitDPしかできない。得点はたぶん乱数でも解けるってことなんだろうし、そこは工夫できそうにない。制約も意図がわからない。食べる順番を適切に決められればいいが、それができない。順番を入れ替えて得なら入れ替えればソートできんのかな（やけくそ）（いや自分よりあとの要素に依存するから無理でしょ）。不可能な問題の解法はDPなので、逆にボールを追加していくとかN*Nの表を描いて消していくとか考えるがどうやったってまとめて考えることができない。価値の高いものから貪欲というのはまあ一度は考えるが、じゃあどっちを食べるのが貪欲なの、そもそも価値の高いものを最初に使っていいのとなって、貪欲する気分に（頑張ってなろうとしてるのに）なれない。それぞれのボールから見て得点が高い順に他のボールを並べ替えたりも思ったけど何その操作。
（追記）最小全域木というキーワードだけ見て自分で考えたが、まあ解法は想像通りで簡単なんだけど、正当性がけっこう難しい。まず、最大全域木から操作手順を得るのは簡単。葉を一つとって、葉と、それとつながっている唯一の頂点に対応するボール2つを選んで葉のほうを食べるというのをN-1回やればいい。あとは逆に操作手順で選んだ2個から辺を作っていってそれが全域木になっていればいい。操作を逆から考えると、最初1個のボールが置いてあって、置いてないボールと既に置いてあるボールから一つずつ選んで置いてなかったボールほうのを置く（得点を得る）という操作をN-1回繰り返すことになり、ボールを置くときに辺を張れば木になる。いやむっず。順方向の操作は葉から（運が悪いとバラバラの場所から）構築というか縮退させていく感じになるので相当イメージしづらい。貪欲も、クラスカル法の貪欲と操作手順が一致しない。
F - Union of Two Sets
4000と50000の関係を調べると、logっぽいなと思い4096が2^12というのをふまえて50000/4000の計算結果を見ると12よりちょっと大きい。長さ1の区間は全部必要なのでN個持つとして、そういうのをlog_2(N)段使っていい。Sparse Table（名前はコンテスト中思い出せず終了後にツイートを見た）みたいにすればいけそうだ。幅を、1以上N未満の2冪に設定する（のちにN=1のケースもあると気づき「N以下」に変更）。その幅の区間を全部生成する。1つのvectorに突っ込むことにしたので、幅が2^iのときの開始位置をb[i]に保存する。クエリに対しては、クエリの幅がK*2以下であるような最小のK（2冪）を求めて、始点がLである区間と終点がRである区間を出力すればよい（隙間はできない）。N=4000のときM=43917で50000以下になることを確認。手で動作確認して、bのイテレータを進め忘れていたことに気づく。提出してAC。
（追記）Disjoint Sparse Tableは実装したことがなかったのでやってみた。2冪みが強いけど思ったより書きやすい。Nより大きい数を出力しててTLE。
G - Similar Permutation
（追記）解説を見ると、EDPCのTが示されているのでまずそれを解く。全然わからないのでkyopro_friendsさんの解説を読む。どうやってまとめるんだと思っていたけど、言われてみれば順列で同じ数はないんだし大小関係だけが重要だから、最後の要素より小さいものが何個残っているかで分類してまとめることができる。左の要素より大きくなるとき、自分より小さいものが残らないようにできるのは左の要素より小さいものが残ってない場合のみ。1個残るようにするには、左の要素より小さいものが0個か1個である必要がある。同様に累積和でできる。その場で累積和をとればin-placeで更新できる。左の要素より小さくなるときは、逆から累積和をとるけど、位置が1個ずれるのでDPテーブルをポインタで管理して累積和をとる前にずらせばやはりin-placeで余計な処理もなくできる。
元の問題に戻ると、順列が2個に増えて類似度もあるのでかなり複雑だ。それまでの類似度と、最後の要素より小さいのがABそれぞれ何個残っているかでDP。さっきのDPは区間和だったので累積和で更新できたが、今回はそれぞれ何個残っているかで正方形に広がるマス目を考えその正方形を4分割して2つずつの和をそれぞれ類似度が変わらないものと1増えるものに配ることができる。つまり2次元累積和をとる。類似度は大きい順に、残り個数は小さい順にやればin-placeでできる。
Ex - Min + Sum
（追記）解説を見る。かなり難しそうだが、分割統治で境界をまたぐものを高速に計算できるらしい。2個目の解法が簡単そうなのでそちらで（実装が楽かは知らんけど）。まずその区間のAの最小値を求めるが、何か上手い方法がありそうでわからず、普通にセグ木を使った（AC後他の提出を見るとなんか上手い方法はあるらしい）（1個目の解法と異なりちょうど半分に分けるわけではないので最小値を全探索はできない）。最小値が境界のすぐ左か右に来るように分ける。そして大きくないほうの区間内の各要素と反対側の区間の要素で作れるペアの個数を求める。境界をまたぐなら最小値は固定なのでBの累積和で二分探索できる。左からと右から両方書かないといけないのがつらい。左からはupper_bound。右から左の相手を探すのはlower_boundだけど逆向きなのでかなり混乱する。丁寧に書けばこれで解けている。最小値の位置がどっち寄りかの判定で、（始点と終点の和と比較するのに）最小値のインデックスを2倍するのを忘れてTLE。
