- https://codeforces.com/contest/1482 (Технокубок 2021 – Финал)
- https://codeforces.com/contest/1483 (div1)
- https://codeforces.com/contest/1484 (div2)
問題番号は div1 のもの．
A. Basic Diplomacy
それぞれの人への容量を $\lceil m/2\rceil$ として最大流をとればよいです．
B. Playlist
素直にシミュレーション．今生き残っている要素，そのうちこのままなら削除できる予定の要素を検出できるようにしておきます．
C. Skyline Photo
素直な dp を考えて，$i=0,1,2,\ldots$ 順に，使う $h$ の最小値が $h_i$ であるような遷移をまとめて行います．するとこの遷移は遅延セグメント木でできることが分かります．
D. Useful Edges
$u$ が一定であるようなクエリを集めてそれらに対する useful edge を判定するようにすればよいです．
E. Vabank
まず，$46$ 回程度かけて，$2^n\leq M<2^{n+1}$ となる $n$ を見つけます．
そのあと単に二分探索していくと，ここから $2n$ 回くらいかかるので回数超過です．大きい方（成功した場合）の探索は所持金が充実して効率が良くなるみたいな要素があって，それを踏まえて二等分より良い分割をとる必要があります．
次のようにしました．まず $7$ 回ほどは，普通に二分探索します．これで，$M$ の上下限が非常に近くなります（$1/128$ 倍程度の差）．すると，この範囲の値をクエリする限り，所持金はほぼ成功回数のみに依存するようになります．適当に $1$ 回成功クエリした状態を所持金 $0$ と定義することにして，所持金は $\pm1$ で変化するとして解ければ十分ということになります（誤差 $1/128$ 倍あるので回数 $128$ 回くらいまでは問題が起きない）．
すると，現在の区間は要素数しか関係なくなるため，dp[残りクエリ回数][所持金] = 特定可能な最大要素数という dp で戦略が決められるようになります．
私は多分わりと $105$ 回ぎりぎりでした．
F. Exam
trie を構築しておき，suffix link も求めておきます．
各 $s_i$ に対する $s_j$ の個数を，$O(|s_i|\cdot \mathrm{polylog}(N)$ 程度の計算量で数えられればよいです．
$n=|s_i|$ として，まず候補は $O(n)$ 個です．$s_i$ の各 prefix に対して，$s_j$ として現れるような最大 suffix を求めればよいです．これを列挙します．suffix link に関する木の適当な dp でできます．
候補が見つかったら，候補の substring を禁止していって生き残るものを数えます．$s_i$ における右端 $r$ を固定して，適当な $s_i[l:r)$ の suffix を禁止ということになります．これも，suffix link に関する木を適当にたどれば，$s_i[l:r)$ の suffix であるような最大の trie のノードがとれるので，そこから trie の根までのパスを禁止という形で書けます．
