Codeforces Round 1079

A. Game with a Fraction

$1$ 問目から実験を書きました．規則が予想できて十分単純なので証明は帰納法で容易．

$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 です．

DAG 制約注意．

$N+M$ 回ということで，おおよそ通常の dfs を再現すれば ok です．

だいたいこんな感じです．あとは探索スキップに対応する処理ができればよいですが，これは上の dfs をしながら同時に「$v$ から始まるパスの個数」を求めることを行えば解決です．DAG なので，$v$ に至るまでのパスによらずにそれを延長する方法の個数を求めればよいことに注意します．

スキップするときには，$v$ からのパスの個数に $w$ からのパスの個数（初到じゃなければ求まってるはず）を加算するというようにすればよいです．

括弧列というのは，「$i<j$，$i$ が開きカッコ，$j$ が閉じカッコとして完全マッチングがある」という言い換えがあります．

よって，最小コスト完全マッチングを求めることとして定式化できます．あるペアのコストは要求変更回数に応じて $0,1,2$ のどれかです．

フローのことを考えると，ある流量までコスト $0$，ある流量までコスト $1$，そのあとコスト $2$ ということになります．

どこまでコスト $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$ つしか使わないということになっていて，その方向性でも解けたかもしれません．

bitset $O(NM/w)$ が十分高速です．

次を行えばよいです：$p$ が与えられる．$q$ をインクリメントしながら，$t[p:q]$ が good かどうかを判定．

次の $2$ つの bitset を作ればよいです．

あとは難しいところは特にありません．

まだ