A. Warrior and Archer
ソートして $d=\min\{x_{N/2+i}-x_i\}$ とします.
後手は $d$ 以上を達成できます.$i,i+N/2$ でマッチングを作り,相手の手にマッチするところを選んでいけばよいです.
先手は $d$ 以下を達成できます.こっちの方が難しいと思います.$x_{N/2+i}-x_i\leq d$ となる $i$ が存在する状態を保つようにプレイします.先手は,$[i,N/2+i]$ の外から削除すると,後手が何を削除してもそのような $i$ の存在が維持されることが確認できます.
B. Max and Bike
単純な二分探索でできます.
C. Edo and Magnets
座圧したときに,最小値や最大値からいくつの $x$ 座標,$y$ 座標を消せるかを考えると,その候補の個数は少なくて全探索可能です.
D. REQ
$\varphi(n)=n\cdot \prod_{p|n}(1-p^{-1})$ で,後者の項を求められればよいです.
各 $a_i$ を素数の列に取り換えれば,列が与えられて,subarray に含まれる要素を unique したときの総積を求めるという問題になります.unique したときの総積というのは,最後の occurrence のみに注目したときの総積といってもよいです.$r$ をインクリメントしながら最後の occurrence を管理すればできます.
E. Cutting the Line
かなり苦労した….解説を読みましたが細部の証明をかなり補いながら読む必要があるように感じられ,まだちょっと証明の細部にも不安があるので,なるべく丁寧に議論します.
Lyndon 分解の定義,存在と一意性を仮定します.Lyndon 分解を線形時間で求めるアルゴリズムについては扱いません.
この解説において,文字列 $S,T$ に対して,$S<T$ かつ $S\notin \mathrm{Prefix}(T)$ であることを $S\ll T$ と書くことにします.$S\ll T$ であることと,任意の $X,Y$ に対して $S+X<T+Y$ であることは同値です.この概念の名称や記号について標準的に使われているものは,少し探した範囲では見つけられなかったので,この記事独自のものだと考えてください.
Lyndon 文字列 $L$ とその proper suffix $L’$ について,$L< L’$ が成り立ちますが,当然 $L$ は $L’$ の prefix ではないので $L\ll L’$ が成り立ちます.このことをよく用います.
本問における操作を次のように再解釈しておきます:$S$ を substring に分割し,そのすべてを reverse してつなげたものを $S’$ とする.substring $1$ つにつきコスト $1$ がかかるが,例外として長さ $1$ の substring を連続して使う場合にはコストがかからない.
さらに次のように言い換えておきます:
$\mathrm{rev}(S)$ を $\mathrm{rev}(S) = X_1\cdots X_M$ と分解し,$S’=X_M\cdots X_1$ とする.通常は substring ひとつに対してコストが $1$ 必要だが,「$X_i, X_{i+1}$ がともに長さ $1$」および「$X_i=X_{i+1}$」の場合には $X_{i+1}$ にはコストがかからない.
後の議論が簡潔になるように $X_i=X_{i+1}$ の場合もコストが出ないことにしました.同じものをまとめて reverse するか,reverse してからまとめるかの違い.
$k=\infty$ の場合
直接は必要ないのですが,議論に慣れるために $k=\infty$ の場合からはじめます.ko_osaga さんの Random notes on Lyndon decomposition で主張はされているが証明はされていないやつです.
$\mathrm{reverse}(S)=L_1L_2\cdots L_K$ を Lyndon 分解とします.最適解が $S’=L_K\cdots L_1$ であることを示します.
(1) まず $X_M=L_i\cdots L_K$ の形であるとしてよいことを示します.
そうでないとすると,$X_M$ はある Lyndon 因子 $L_i$ の proper suffix から始まります.つまり $X_M=L_i’\cdots L_K$ かつ $L_i’$ は $L_i$ の proper suffix とできます.$L_i$ が Lyndon 文字列であることから $L_i\ll L_i’$ となるため,$X_M\cdots = L_i’\cdots > L_i\cdots$ となって,$L_i$ からとった方が文字列が小さくなります.これで示せました.
(1) より帰納的に,最適解を各 $X_j$ が $L_l\cdots L_r$ の形のときに限定できます.よって $S’$ は $L_1, \ldots, L_K$ の permutation です.そのうちで $S’=L_K\cdots L_1$ が最適であることを示すには,次の (2) を示せばよいです.
(2) $S,T$ が Lyndon 文字列で $S<T$ のとき,$ST<TS$.
$S\ll T$ なら自明です.$S$ が $T$ の prefix であるとしてよいです.$T=SX$ とします.
$X$ は $T$ の proper suffix で $T$ が Lyndon 文字列なので $T\ll X$ です.よって $T<XS$ なので $ST=SXS=TS$ です.
これで,$k=\infty$ の場合が解けました.
$k$ が大きいときの貪欲法
雑な気持ちとしては,$S’$ はなるべく $L_K\cdots L_1$ に近づけたくて,特になるべく長い prefix を $L_K\cdots L_1$ に完全一致させたくて,そのためコストに余裕があるうちは $L_K, L_{K-1},\ldots$ の順に貪欲にとっていくのが良さそうです.これをちゃんと証明します.
$k\geq 3$ であるとき,$X_M=L_K$ とするのが最適解のひとつであることを示します.
まず,$X_M=L_i\cdots L_K$ の形以外の取り方は,上の (1) と同様に除外できます.
また,$K'<K$ かつ $L_{K’}=\cdots=L_K$ であるとき,$X_M=L_{K’}\cdots L_K$ という取り方も考慮する必要がありません.同じ文字列の連続はコスト $0$ でとれるという定式化を採用したからです.
したがって,$i<K$ かつ $L_i>L_K$ として,$X_M=L_i\cdots L_K$ という取り方が最適でないことを言えばよいです.
今考えている文字列では $L_i\cdots L_K\cdots$ となっていますが,その代わりにコスト $3$ 以下で実現できる $L_K\cdot (L_i\cdots L_{K-1})\cdot (L_1\cdots L_{i-1})$ という解を考えて,辞書順で小さくなっていることを確かめればよいです($k\geq 3$ を使いました).
文字列長の等しい部分 $L_K\cdot (L_i\cdots L_{K-1}) < (L_i\cdots L_{K-1})\cdot L_K$ を示せばよいです.これは $L_K$ の挿入位置をずらしていきながら繰り返し (2) を適用することで証明できます.
以上で $k\geq 3$ のときは,最初に末尾の Lyndon 因子をとるとしてよいことが分かりました.初手以外ではコストがかからない操作が存在するので,少しだけ議論を修正しなければいけませんが,次が証明できます:
末尾の Lyndon 因子をとったときに残りコストが $2$ 以上残るならば,末尾の Lyndon 因子をとってしまってよい.
証明はほとんど同じです.
$k=2$ の場合
($k=1$ の場合は別処理するとして)結局本問は,$k=2$ かつ,末尾の Lyndon 因子がコスト $0$ でがとれない場合に帰着できたことになります.
末尾の文字 $1$ 文字をコスト $0$ でとれる余地は残っていますが,これが Lyndon 因子でないならばその文字は最小の文字ではないため,これをとるのは最適解になりえません.よって,最初にとるものはコスト $0$ ではないとしてよいです.
そこで,ここからは元の問題の設定に立ち返って考えます.
$S$ が与えられる.$S=XY$ と分割したとき,$XY$, $X\cdot \mathrm{rev}(Y)$,$\mathrm{rev}(X)\cdot Y$,$\mathrm{rev}(X)\cdot \mathrm{rev}(Y)$ の形で書ける文字列のうち辞書順最小のものを求めよ.
$4$ 問あります.単純な解法として,suffix array と LCP 配列を計算して,LCP 配列の RMQ を用意すれば,上の形の文字列は何もかも辞書比較できるようになって解けるのですが,本問は制約が非常に大きいため私は TLE でした.比較的軽い $O(|S|)$ 時間で動作する解法を説明します.
$4$ 問あります.
$XY$ の最小化
これはどこで分割しても $S$ そのものなので明らかです.
$X\cdot \mathrm{rev}(Y)$ の最小化
$\mathrm{rev}(S)+S$ に対する Z-algorithm の結果から,比較に必要な lcp が全て得られるので,$O(|S|)$ 時間で解けます.
$\mathrm{rev}(X)+\mathrm{rev}(Y)$ の最小化
次を示しておきます.
(3) Lyndon 分解 $L_1\cdots L_K$ について $L_i\cdots L_K > L_{i+1}\cdots L_K$.
(2) を繰り返し使うと $L_i\cdots L_K\geq L_{i+1}\cdots L_K\cdot L_i$ がいえるのでよい.
さて,$\mathrm{rev}(X)+\mathrm{rev}(Y)$ は $\mathrm{rev}(S)$ の cyclic shift です.よって,文字列 $S$ に対してその minimum cyclic shift が求められればよいです.これは $S+S$ の長さ $|S|$ の substring です.
よって,文字列 $S$ と整数 $n$ に対して,$S$ の長さ $n$ の substring で最小のものが求められればよいです.substring は suffix の prefix なので,$S$ の長さ $n$ 以上の suffix のうちで最小のものが求められればよいです.$S$ の Lyndon 分解 $L_1\cdots L_K$ をとります.(1) の証明のようにして,ある $L_i$ から始まる suffix のみを考慮すればよいです.(3) より,そのようなもののうち長さ $n$ 以上であるもののうち最も大きな $i$ から始まるものをとればよいです.
$\mathrm{rev}(X)+Y$
(4) $S=L_1\cdots L_K$ を Lyndon 分解とし,$L_{i-1}\cdots L_K$ が $L_i\cdots L_K$ の prefix とならないような最大の $i$ を $K’$ とする.このとき,$S$ の suffix $X$ について次は同値である.
(i) ある $i\geq K’$ が存在して $X=L_i\cdots L_K$.
(ii) $S$ の suffix $Y$ であって,$Y\ll X$ となるものは存在しない.
(1) と同様に Lyndon 因子から始まる suffix 以外は (ii) を満たしません.これと (3) から分かります.
このことを用いて $\mathrm{rev}(X)+Y$ の最小化を考えます.この前半の $\mathrm{rev}(X)$ としては,$\mathrm{rev}(S)$ について (4) を満たす suffix のみを考えればよいです.
これらの suffix はどの 2 つも border の関係にあるため,$\mathrm{rev}(X)$ 部分の候補として,文字列 $X_1, \ldots, X_n$ であって $X_i$ は $X_{i+1}$ の prefix であるというものをとることができます.
すると,$\mathrm{rev}(X)+Y$ の最小化問題は,$i$ について昇順に $X_i$ から $X_{i+1}$ に延長するか,打ち切ってそれ以降を $Y$ とするかの $2$ 択を貪欲に行えばよいです.これで $O(|S|)$ 時間でこの最小化問題を解くことができます.
なお最後のケースについて,より詳しく考えれば試すべき $X$ を $2$ 個以下にできることが解説に書かれています.がこれは私は理解していません.