- Yandex Cup 2024 参加記：https://maspypy.com/yandex-cup-2024-final-algorithm
A. Swap Columns and Find a Path
あるひとつの列からは両方，ほかの列からは好きなものひとつをとることができます．
B. Move Back at a Cost
一度以上 pop するものは操作順を調整すれば，$+1$ したあと好きな順で後ろにつけられます．$+1$ をしたものをソートして後ろにつけると思ってよいです．$+1$ を $2$ 回やる項もないとしてよいです．
あとは $+1$ せず残すものを適当な貪欲で選んでいきます．
C. Adventurers
$y_0$ と $n$ を決めると，全員 $n$ 個以上にできるかの判定は簡単です．$y$ が小さい側・大きい側それぞれで上位・下位 $n$ 要素全体を管理すればよいです．
あとは $y_0$ と $n$ を適切にスライドさせて判定します．
D. For the Emperor!
scc を求めて DAG の場合に帰着しておきます．最小費用流にします．
各頂点 $v$ に対して $3$ つの頂点 $v_0,v_1,v_2$ を作ります．
- $v_1\to v_2$ に最小流量 $1$ の辺：$v$ がひとつ以上受け取る必要があることを意味する．
- $v_0\to v_1$ にコスト $1$ の辺：$v$ でプランの原本を持つ人が発生することを意味する．
- $v_0\to v_2$ にコスト $\infty$ の辺：$v$ で他の人からコピーを受け取った人の動きを意味する．$v_1\to v_2$ の最小流量を満たす解においてコピーを受け取ることは可能．
などの辺を張ります．
E2. Cheops and a Contest (Hard Version)
各 $i$ について，グループ $p,p+1$ 間の要請をすべて満たすことが必要です．
すべてのトピックが異なることから，基本的には $a_i$ の高い人が高スコアを納めます．ある $2$ 人について，トピックを無視して計算した場合と比べて勝敗数差が大きく変わることはありません．
グループ $p$ の中での $a_i$ の最小値を $l_p$，最大値を $r_p$ とすると，$x\in [l_p+1,r_{p+1}]$ について難易度 $x$ の問題が存在してはいけません．これらの難易度の使用禁止を以下の前提とします．
この条件を満たす限り，誰とも無関係なトピックの問題を追加しても損することはありません．まずはこの条件を満たす範囲で（座圧したうえで）すべての難易度の問題を十分個数ずつ（$2$ 問で十分）追加しておきます．
この前提のもと，$2$ 人の関係としてはこの時点で $2$ 問以上差がついているか，同点かのどちらかです．この時点で $2$ 問差がついている人に関する条件はあとは無視してもよいです．この時点で同点であるような $2$ 人については，（使用禁止難易度の問題を使わない前提で）どちらかが専門であるようなトピックでしか差がつくことはありません．
このことを考慮すると，各トピックについて，
- このトピックによる加点（$a_i$ で計算するよりも真に得点が上がる）を得たい人が居るか
- 居る場合，このトピックとして可能な点数の上下限（グループ $p$ の人がグループ $p+1$ の人を抜き去るために下限が出てくる．そのような人の $b_i$ から上限が出てくる）
- そのトピックについてさらに禁止すべき難易度区間：グループ $p+1$ の人が正解するならば，グループ $p$ の人もすべて正解する必要があることから
などが決まります．これらの条件を満たすようにそれぞれのトピックの難易度を設定していきます．
F2. Yandex Cuneiform (Hard Version)
文字種を A, B, C とします．
まず F1 です．個数が等しくて連続同一文字が存在しないならば，目的を達成できます．$3$ 文字ずつ削除していることを示せばよいです．
ABC となる場所があったとしてこれに注目します．これが左端や右端なら削除可能です．ABCA でも削除可能です．どちらでもないとき BABCB の形になっています．これに加えて BAC, BCA のどちらかがあれば，(BA–B, B-C) や (B–CB, B-A) などと削除すれば条件を達成できます．
A, B, C の文字種を入れ替えて，上述のパターンの削除方法をすべて試すと，必ずうまくいく場所があることが示せます．BAC, BCA のどちらも存在しないと B-B-B-B のように B の個数が大量になってしまうことなどから示せます．
これで F1 が解けます．
F2 について，それぞれの “?” からなる区間を適切に埋められるかです．判定問題について，A, B, C それぞれを単独で見たときに配置できる個数上限を求めて，その必要条件が満たされていれば十分だというのを，実験で確かめました（成り立つならば証明は帰納法で比較的簡単に示せるとは思います）．
あとはこの条件を保つように $1$ 文字ずつ決めていけばよいです．
フローを使って各区間の個数を決めてから決めていきましたが，これは不要な実装でした．
