Codeforces Round 740

https://codeforces.com/contest/1558

A. Charmed by the Game
B. Up the Strip
C. Bottom-Tier Reversals
D. Top-Notch Insertions
E. Down Below
F. Strange Sort

A. Charmed by the Game

先攻を決めて 2 回解きます．

https://codeforces.com/contest/1558/submission/126848797

B. Up the Strip

$n$ からゴールまでの経路数 $d p [n]$ を昇順に計算します． $z$ は愚直にループして調和級数計算量．区間加算をしながら点取得を昇順にとりたいことになります．imos 法と同じことを動的にやればよいです．計算量 $O (n \log n)$ ．

https://codeforces.com/contest/1558/submission/126861277

C. Bottom-Tier Reversals

すべての数の移動距離が偶数であることが必要です．

$5$ 回で末尾ふたつをそろえます．

$N - 1$ を先頭に持ってくる
$N - 1, N - 2$ がこの順に並ぶようにする．
$2, 3$ 番目がこの順に $N - 2, N - 1$ であるようにする．
$1, 2$ 番目がこの順に $N - 1, N - 2$ であるようにする．
末尾 $2$ つが $N - 2, N - 1$ であるようにする．

という感じの手順でできます．

https://codeforces.com/contest/1558/submission/126871972

D. Top-Notch Insertions

操作を逆順に考えれば，初期状態はソートされていて， $A_{i} < A_{i + 1}$ を満たす $A_{i}$ を適当な後ろの方に捨てるという操作になります．

初期状態の隣接 $2$ 項について， $<$ であるか $≦$ であるかが順次求まっていき，最終的には $N$ 個のものの各隣接 $2$ 項に $≦$ , $<$ が与えられるので列を数えるというタイプの問題になります．これは適当な二項係数です．

各時点での $y$ 番目が初期状態のどれに相当するかなどは，fenwick tree などで得られます．

https://codeforces.com/contest/1558/submission/126887059

E. Down Below

すごい．

二分探索します．そのあとは「貪欲に」倒していきます．以下で経路はすべて power の条件を満たすもののみを考えます．

新規に何人かを撃破したあと，はじめて撃破しない移動をする瞬間があるはずで，その一連の動作を考えると， $a, b$ は撃破済の頂点として

「 $a \to v_{1} \to \dots \to v_{k} \to b$ 」，「 $a \to v_{1} \to \dots \to v_{k} \to v_{i}$ (i<k)」といったパターンがあります．どちらの方法でも，そのように撃破済の頂点を拡張した後には，これまでの撃破済の頂点すべてに移動可能であるという性質が維持されます．なので，「後戻りできない」という制限は忘れてこれら $2$ 種の動作を可能なものがある限り行うという貪欲アルゴリズムで判定できます．

すると今度は，これら $2$ 種のパターンが存在するか否かを高速に判定することが課題となります．特に探索時に各頂点へ行く方法は一意ではなく，そのうち最適なものを判断する基準もよくわからないのが難しそうに見えます．

しかし撃破済の頂点から同じ頂点 $c$ への相異なるパス $a \to v_{1} \to \dots \to v_{i} = c$ , $b \to w_{1} \to \dots \to w_{i} = c$ があったとしましょう．さらに最後に使った辺が異なるとします．このとき，これらの経路上の点 $v_{1}, \dots, v_{i}, w_{1}, \dots, w_{i}$ はすべて撃破可能です（reverse して結合する，少し計算すると証明可能）．

したがって，各頂点へ行く方法のどれを持つべきかという心配は杞憂で，そのような方法がはじめて $2$ 通り見つかった瞬間にすでに撃破可能頂点集合がひとつ手に入っていることになります．よって単に dfs します． dfs 木を持っておき，各頂点へ行く方法は木上のものだけを保持している状態です．木にならない辺が見つかったらその時点で撃破頂点集合が見つかるので，この一連の探索の計算量は $O (n + m)$ となります．

あとは可能な限りこのステップを進めることと二分探索で計算量は $O (n (n + m) \log a)$ です．

https://codeforces.com/contest/1558/submission/309658867

F. Strange Sort

01 principle． $1, \dots, m$ が書かれている場所を $0$ に置き換え， $m + 1, \dots, n$ が書かれている場所を $1$ に置き換えた $01$ 列に対するソート回数の max をとればよいです．これらがすべてソートされるならば， $1, 2, \dots, n$ が正しい位置に来ることが帰納的に言えるからです．

結局， $01$ 列の点変更（ $1 \to 0$ ）を行いながら， $01$ 列に対する odd, even sort の回数を求められればよいです．

$0$ は左に移動する一方です．

仮想的に列の左側に無限個の $1$ を置いておきます．このように拡張しても，各 $0$ の移動はゴールするまでは変わらないことが確認できます． $0$ が $m$ 個あるとしてこれらを $a_{1}, \dots, a_{m}$ と呼び，これらがインデックス $0$ から $- 1$ に移動する時刻を $t_{i}$ とすると， $t_{i + 1} = max (t_{i}, x)$ ただし $x$ は左側がすべて $1$ だと想定して計算した時刻となることが分かります．すべてがゴールする時刻は $t_{m} - m$ です．あとはこの計算，差分更新をセグメント木などで実現します．

https://codeforces.com/contest/1558/submission/270438025