A. Game with a Fraction
$1$ 問目から実験を書きました．規則が予想できて十分単純なので証明は帰納法で容易．
B. Another Problem about Beautiful Pairs
$xy\leq N-1$ となる $(x,y)$ ごとに数えます．
この際，$1\leq x\leq y$ として，$a_i=y$ となる $i$ に対して $(i-xy,i)$ および $(i,i+xy)$ をチェックするというようにします．
するとひとつの $i$ に対するチェックが $\min(y, N/y)$ 回以下とかでおさえられるので $1.5$ 乗オーダーになります．
なお，適当に「$x,y$ の出現頻度を調べて少ない方から調べる」をやってみるだけでも，上で述べたものより悪くなることはないので AC です．
C2. Interactive Graph (Hard Version)
DAG 制約注意．
$N+M$ 回ということで，おおよそ通常の dfs を再現すれば ok です．
- $v$ に到達するパスが $k$ 番目だと分かっている
- $k+1$ 番目のパスを調べて $v$ までのパスが変わってたら $v$ での探索を終了．
- 次の点 $w$ を見つけた場合，これが $w$ への初到ならば $w$ からの探索開始．
- $w$ への初到じゃない場合は $w$ からの探索をスキップして $v$ から行ける次の頂点を調べる．
だいたいこんな感じです．あとは探索スキップに対応する処理ができればよいですが，これは上の dfs をしながら同時に「$v$ から始まるパスの個数」を求めることを行えば解決です．DAG なので，$v$ に至るまでのパスによらずにそれを延長する方法の個数を求めればよいことに注意します．
スキップするときには，$v$ からのパスの個数に $w$ からのパスの個数（初到じゃなければ求まってるはず）を加算するというようにすればよいです．
D. Double Bracket Sequence
括弧列というのは，「$i<j$，$i$ が開きカッコ，$j$ が閉じカッコとして完全マッチングがある」という言い換えがあります．
よって，最小コスト完全マッチングを求めることとして定式化できます．あるペアのコストは要求変更回数に応じて $0,1,2$ のどれかです．
フローのことを考えると，ある流量までコスト $0$，ある流量までコスト $1$，そのあとコスト $2$ ということになります．
どこまでコスト $0$ であるかというのは，変更なしでカッコ列の開閉をマッチさせることで，種類ごとに独立に解けばよいです．
どこまでコスト $1$ かということですが．これは結局
- コスト $0,1$ の辺だけでマッチングを作る
- $0$ の個数は最大化している前提でよい
- コスト $1$ の辺をなるべく足す
ということです．（コスト $2$ 増えるところでは，コスト $0$ のマッチが解消されてコスト $1$ のマッチを $2$ ペア発生というパターンがありますが，コストが $1$ しか増えてない時点ではコスト $0$ のマッチが組み変わることはあっても個数が減ることはありません．）
というわけでまずコスト $0$ の辺を最大個数使うマッチングをとるのですが，これは少し考えると，普通にカッコ列の対応規則でマッチングを組んでしまうのが最適であることがわかります．最初に開閉ができるところで別の組み方にして残しが良くなるかを考えるという要領．
こうしてコスト $0$ のマッチングを最大限作ったあと，これらの辺は組み替えない前提でコスト $1$ のマッチングを作っていけばよいです．
帰着先としては，$01$ 列があって，$i<j$ に対して $i,j$ 番目が $(0,0),(0,1),(1,1)$ のどれかだとマッチ可能という感じです．
$0,1$ が偶数個ずつなら $(0,0),(1,1)$ だけで完全マッチング達成．奇数個ずつなら $(0,1)$ がひとつでも作れるかという問題になります．
コンテスト中は考えなかったのですが，結局コスト $2$ であるような辺は高々 $1$ つしか使わないということになっていて，その方向性でも解けたかもしれません．
E2. Fuzzy Concatenation (Hard version)
bitset $O(NM/w)$ が十分高速です．
次を行えばよいです：$p$ が与えられる．$q$ をインクリメントしながら，$t[p:q]$ が good かどうかを判定．
次の $2$ つの bitset を作ればよいです．
- $s[i:i+q-p]$ と $t[p:q]$ がコスト $0$ 以下で一致するような $i$ 全体．
- $s[i:i+q-p]$ と $t[p:q]$ がコスト $1$ 以下で一致するような $i$ 全体．
あとは難しいところは特にありません．
F. Indivisible
次数列だけが問題です．Erdos Gallai の定理と分割数列挙などで実験ができます．
$(N,M)$ で作れれば孤立点を足すだけで $(N+1,M)$ でできるので，各 $M$ に対して，最小の $N$ だけが問題です．
$\binom{N}{2}\geq M$ が必要で，多くの場合これを満たす最小の $N$ が条件を満たします．$N$ が奇数になるパターンが簡単です．この場合，総和 $2M$ を均等に割り振れば（$M$ が十分大きく $N$ が最小付近ならば）条件を満たします．$N$ が奇数であることにより，異なる大きさの集合を使わなければいけないことから証明できます．
$N$ が偶数ならば，まず $N-1$ で埋めたあと，少ない回数のデクリメントを行います．デクリメントのやり方ですが，これは「$N$ が奇数の場合の構成」を参考に，奇数箇所に対してバランスよくデクリメントするという方法をとってみます．
全体的に $N-1$ に近い大きさで埋められているから個数を半分ずつにしないと失敗，とはいえデクリメント量を半分ずつにすることはできない，ということからおおよそこれで解けていることが分かります．
デクリメントの量が $0,2,4,8,12,24$ だとこの方法で失敗しています．
$24$ のデクリメントの場合は，バランスよくデクリメントというのを少し崩して，$3,3,3,5,5,5$ のデクリメントを行うと条件を満たします．それ以外は分割数列挙的な探索により不可能（したがって $N$ をひとつ大きくして構築する）ということになります．
コンテスト当日の反省点として，各 $M$ に対する降順次数列として辞書順最大のものを出力して観察しようとしていたのですが，辞書順最小のものも試すべきでした．奇数頂点の場合の構築は実験だけで気づけるやつです．
