Order Capital Round 2 (Codeforces Round 1104)

A. Destroying Towers

誤読して間違えまくった挙句，単にサンプルを眺めて合うものを提出しましたｗ

並べ替えて $a_i\leq b_i$ にする問題だと思うことにします．並べ替えに対する転倒数の最小値ということになります．

$b$ の単調性に注目します．$b_1$ の手前に入れるものは，$a_i\leq b_1$ を満たすもののうちでインデックス最小のものとしてよいです．

なぜならば $b_1$ 以下であるものはすべて同じ値だと思ってしまってもよく，同じ値同士のスワップはしないと仮定してもよいので，インデックス最小のものを使うとしてよいです．

これを繰り返して，$b_2$ 以下，$b_3$ 以下のものでどれを使うかを貪欲に決めていきます．

手前から順に操作しました．実はあまり証明していませんが，たぶん $[0,n)$ が単調になる中で末尾が最小化できているということを $n$ について帰納的に示すとできるかな？

見たことあるはずなのに，初見っぽい気分で悩んでしまった．

実験して数えると $2^n/3$ 通りくらいありそうだったので mod 3 の不変量を疑う．

mod 3 から来る必要条件と，”00″ or “11” の存在という必要条件があって，十分にもなる．

条件が分かれば証明は帰納法で簡単．

$a$ を写像と見て，条件は

$$a\colon i\to j\implies b[i]\to b[j]$$

と見ます．特に $a$ について，$i\to j\to k\to \cdots$ というサイクルがあると，$b[i]\to b[j]\to b[k]\to \cdots$ というサイクルもなくてはいけません．$i, b[i]$ の $a$ に関するサイクル長が等しいという必要条件があります．

$1$ 点での値が決まっているとそれの属するサイクル全体が決まります．そういう処理を常に可能な限りやっておきその時点で矛盾がなければ，未知の値が来たときには単に同じサイクル長のところを割り当てればよいことがわかります．

結局，例の塗りつぶしできる条件を整理していくと，かなり簡単な条件になってしまいます．

言い換えられたら，$a[i]-i$ をインデックスとするセグメント木で適当に dp するだけになります．

いったん $n$ を $9$ の倍数だとします．

長さ $9n$ の配列はだいたい $180n$ bit の情報量で，これを長さ $10n$ 程度の列 $b$ にエンコードすればよいです．$2 ^ {18}$ 通り程度の値を $10$ 個送るという方針にします．末尾 $150$ 個を使って，これらを復元します．

小さい素数 $150$ 個をとって，smooth number を数えると，$2^{18}$ よりたくさんあるので，末尾に小さい素数 $150$ 個の pow を並べておき，それらとの gcd を使って smooth number を復元します．

自分は $10\cdot \lceil n/9\rceil$ のような何かを使ったため，小さい $n$ を例外処理する必要が発生しました．

$n\leq 150$ なら，単に入力列を $2$ 回並べて自身との gcd をとって処理しました．丁寧にやれば解法場合分けなしでもいけるはずです．

まだ．

まだ．