A. Suspension
人が無限に居るときの最適解が $R+\lfloor Y/2\rfloor$ です．これと $N$ の $\min$ が答です．
B. Split
結構難しい．
出現するものの頻度を数えて，奇数だったら $1$ 点，偶数だったら $2$ 点というのがその種類から得られるスコアの上界です．これは多くの場合達成可能です．まずこの理論値が達成できるかを考えると
- 偶数回のもの：まず $p,q$ に $1$ 個ずつ入れる．残りを $2$ 個組に分けておく．
- 奇数回のものは，好きに $p,q$ に入れられる，これに上で分けておいた $2$ 個組ずつで $p,q$ どちらかに入れられる．
こういう状況です．$p$ だけをサイズ $n$ にすれば $q$ は自動的にサイズ $n$ になることを考えると，次のどちらかの状況で理論値達成可能です．
- 奇数回の要素が存在する．
- 最初にいれた $1$ 個ずつと，$2$ 個組いくつかでちょうど $n$ 要素にできる（偶奇が適切）．
これに失敗する状況を考えます．このとき，ひとつの偶数のスコアを $0$ 点とすれば目的を達成できることが分かります．
ひとつの偶数を，好きに $p,q$ に入れられるとして扱えば，上の場合とだいたい同じです．
C. Annoying Game
これも信じると簡単ですが，証明には詰まりました．$k$ ターンのときの解を $f(k)$ とします．
- $f(1)\geq f(3)\geq f(5)\geq \cdots$：$k$ ターンのゲームでは，B は A の動きを戻すようにすると，$f(k-2)$ 以下の値に抑えられる．
- $f(1)\leq f(3),f(5),f(7), \cdots$：A は初手以外では B の動きを巻き戻すようにすると，$f(1)$ 以上の値が獲得可能．
- $f(0)\geq f(2),f(4),f(6),\cdots$：B は A の動きを戻すようにする．
- $f(2)\leq f(4)\leq f(6)\leq \cdots$：A は $2$ 回目以降の手番では B の動きを戻すようにする．
- $f(0)\leq f(2)$：初期状態で max subarray sum となる区間 $[l,r]$ をとり，$l\leq i\leq r$ のうちで最大の $b_i$ を選びこれを加算する．最大の $[l,r]$ を選んだため，B の動きの後必ず $[l,r]$ の subarray sum は $f(0)$ 以上である．
これで，$f(0)=f(2)=f(4)=\cdots$, $f(1)=f(3)=f(5)=\cdots$ となるので，問題を解くには $f(0),f(1)$ を求めればよいです．
$r$ をインクリメントしながら，$r$ で終わる subarray の和の最大値を持つ dp をすればよいです．$f(1)$ のためには，状態として $b_i$ の加算を選んだか否かという $2$ 状態の dp にします．
D. Palindrome Flipping
操作は可逆なので，$s\to 000000\to t$ とします．これで $s\to 000000$ と $t\to 000000$ だけ実装すればよくなり，文字列ひとつに専念できます．
$1$ の occurrence のうち最も右のものに注目して，その位置を小さくしていくということをします．
$…100001$ というところをフリップするということをやっていけばよいです．$1$ がひとつだけになったときが問題ですが，$001\to 111\to 000$ や $0100\to 0111\to 0000$ などを適切に使います．
E. Sink
まず変更クエリがないとすると，
- 同じ値の隣接 $2$ 頂点に辺を張って連結成分分解．
- 各連結成分の近傍で小さい値があるかをチェック．これが $0$ 個なら答に $1$ を加算．
ということになります．あとはいわゆる offline dynamic connectivity のテクニックです．
よくあるのは「辺の追加・削除」ですが，この問題では「$a_v=x$ であるというデータ」の追加・削除をすればよいだけで，大した違いはありません．
全部の $a_v$ が未定の状態からはじめて
- $a_v$ の値を確定させる操作が来る．確定している頂点に対するマージや，近傍の小さい値のカウント，ANS の更新などを行う．
- この操作を roll back する．
ということをすればよいです．
F1. Distinct GCDs (Easy Version)
$\gcd(x_i,x_j)$ （$1\leq i\leq j\leq n$）が全部異なるような $x$ がとれたとして，ここからなるべく長い列 $a$ を作ることを考えます．
$n$ 頂点の完全グラフにループを追加した上で，同じ辺を $1$ 回までしか使わないような最長 walk の頂点列から，このような $a$ が得られます．最長 walk を求めるためには，次数が奇数の頂点が $2$ 個以下になるまで辺を減らしてから eulerian walk をとればよくて，完全グラフだと簡単です．
結局，列 $x$ をとるところが問題です．F1 では，$x_i=2^i3^{k-i}$ の形の数を使えば目的を達成できます．
F2. Distinct GCDs (Hard Version)
$x_i=2^i3^{k-i}$ のアイデアを $2$ 次元化して表現力を増やします．
$x_{i,j} = a^ib^{9-i}c^jd^{9-j}$ としてできる $100$ 個の数を考えてみます（$a,b,c,d$ は異なる素数）．
$x_{i_1,j_1}, x_{i_2,j_2}$ の GCD が与えられると，F1 と同じ理屈で，$(i_1,i_2)$ および $(j_1,j_2)$ が multiset としては決まります．ただし $(i_1,j_1),(i_2,j_2)$ と $(i_1,j_2),(i_2,j_1)$ が区別できません．
これを修正して $x_{i,j}=a^ib^{9-i}c^jd^{9-j}e^{i+j}$ の形にすると，これらの区別が可能となります．$a=3,b=11,c=5,d=7,e=2$ などとすれば AC が得られます．
