Codeforces Global Round 25 F. Inversion Composition が理解できたかもしれない

自分だけ解けない問題

この記事は、Codeforces Global Round 25 F. Inversion Composition の解き方を提案したものです。自分は解説を見て考えただけです。

「自分だけ解けない問題」と自分が言う問題たちは、解説を見たり、ヒントを得て解法を思いついたりしても必ずバグり、通すために時間がかかってしまうという傾向にあります。この問題も何も分からず、解説を見た上でさえ6時間以上ACできませんでした。

「自分だけ解けない問題」はそれにも拘らずやってきます。このACの苦戦を「次に向けて反省せよ」とのメッセージと解釈し、どういうふうに解けばよいのかを整理してみました。

PART 1

まずは軽く実験してみると、 $\text{inv}(p) \le k \le n(n-1) - \text{inv}(p)$ かつ $k \equiv \text{inv}(p) \pmod 2$ だったら問題文の条件を満たすような $q$ が必ず存在すると予想できます。これは正しい（ことが後々証明できる）ので、今後はこの条件を仮定します。

ただし、ここから構築方法を当てるのは難しいです。

PART 2

$r = q \cdot p$ 、すなわち $r_i = q_{p_i}$ とします。 $q$ と $r$ がどのような関係で動くのかは想像しにくいです。そこで、 $q$ と $r$ の転倒数の和がどのように動くのかに注目します。転倒数の定義に注目します。

$r$ の転倒数は $i \lt j$ かつ $r_i \gt r_j$ を満たす組の個数、すなわち $i \lt j$ かつ $q_{p_i} \gt q_{p_j}$ を満たす組の個数です。

$q$ の転倒数は $i \lt j$ かつ $q_i \gt q_j$ を満たす組の個数です。ここで、転倒数はどのような順番で計算してもよいです。なので、 $q$ の転倒数は「 $p_i \lt p_j$ （ $i \lt j$ とは限らない）かつ $q_{p_i} \gt q_{p_j}$ を満たす組の個数」に言い換えられます。

これらは似た形をしていますが、感覚的に、 $i \lt j$ かつ $p_i \gt p_j$ のときは $r$ による $q_{p_i} \gt q_{p_j}$ と $q$ による $q_{p_j} \lt q_{p_i}$ は打ち消し合い、 $i \lt j$ かつ $p_i \lt p_j$ のときは $r$ による $q_{p_i} \gt q_{p_j}$ と $q$ による $q_{p_i} \gt q_{p_j}$ はマッチして $2$ 倍に増幅するように思えます。定常波における「節」と「腹」を思い出します。

詳しく書いてみると：

かつなら
- $q_{p_i} \gt q_{p_j}$ なら $(p_i, p_j) \ (p_i \lt p_j)$ において $\text{inv}(q)$ にちょうど $1$ だけ寄与する
- $q_{p_i} \lt q_{p_j}$ なら $(p_i, p_j) \ (p_i \lt p_j)$ において $\text{inv}(q)$ に寄与しない
- $q_{p_i} \gt q_{p_j}$ なら $(i, j) \ (i \lt j)$ において $\text{inv}(r)$ にちょうど $1$ だけ寄与する
- $q_{p_i} \lt q_{p_j}$ なら $(i, j) \ (i \lt j)$ において $\text{inv}(r)$ に寄与しない
かつなら
- $q_{p_i} \gt q_{p_j}$ なら $(p_j, p_i) \ (p_j \lt p_i)$ において $\text{inv}(q)$ に寄与しない
- $q_{p_i} \lt q_{p_j}$ なら $(p_j, p_i) \ (p_j \lt p_i)$ において $\text{inv}(q)$ にちょうど $1$ だけ寄与する
- $q_{p_i} \gt q_{p_j}$ なら $(i, j) \ (i\lt j)$ において $\text{inv}(r)$ にちょうど $1$ だけ寄与する
- $q_{p_i} \lt q_{p_j}$ なら $(i, j) \ (i\lt j)$ において $\text{inv}(r)$ に寄与しない

となるので、

かつなら、
- $q_{p_i} \gt q_{p_j}$ すなわち $r_i \gt r_j$ なら $\text{inv}(q) + \text{inv}(r)$ にちょうど $2$ だけ寄与する
- $q_{p_i} \gt q_{p_j}$ すなわち $r_i \gt r_j$ なら $\text{inv}(q) + \text{inv}(r)$ に寄与しない
$i \lt j$ かつ $p_i \gt p_j$ なら、この組は $\text{inv}(q) + \text{inv}(r)$ に必ずちょうど $1$ だけ寄与する。

と分かります。

後者は $q, r$ に関係なくちょうど $1$ だけ寄与するので、この組については何も気にしなくてよいことが分かります。しかも、「 $i \lt j$ かつ $p_i \gt p_j$ 」なので合計すると $\text{inv}(p)$ になります。また、 $i\lt j$ かつ $p_i\lt p_j$ かつ $r_i\gt r_j$ のときは $\text{inv}(q) + \text{inv}(r)$ に何も寄与しません。

よって、問題は「 $i \lt j$ かつ $p_i \lt p_j$ かつ $r_i \gt r_j$ となる個数が $(k - \text{inv}(p)) / 2$ になるような順列 $r$ を作る」ことに帰着されます。

PART 3

改めて、 $k' := (k - \text{inv}(p)) / 2$ とおきます。解くべき問題は、

$i \lt j$ かつ $p_i \lt p_j$ かつ $r_i \gt r_j$ となる個数（これをスコアということにします）が $k'$ になるような順列 $r$ を作る

です。明らかに $r=(1,2,\cdots, n)$ のときはスコア $0$ 、 $r=(n,n-1,\cdots, 1)$ のときはスコア最大です。

スコアを $k'$ にぐっと近づけてから調整することを考えます。ある $t$ があって、 $r=(t-1,t-2,\cdots,2,1,t,t+1,\cdots, n)$ のときスコアは $k'$ 以下、 $r=(t,t-1,\cdots,2,1,t+1,t+2,\cdots, n)$ のときスコアは $k'$ 以上となります。この $t$ を固定します。

$r=(t,t-1,\cdots,3,2,1,t+1,t+2,\cdots, n)$ としておいて、ここから調整します。これはスコア $k'$ 以上なので、スコア $k'$ にするには、 $1$ 個ずつ $i \lt j$ かつ $p_i \lt p_j$ かつ $r_i \gt r_j$ となる個数を減らせばよいです。つまり、いままで $r_i \gt r_j$ であったものを $r_i \lt r_j$ に変えればよいです。

ここで、

スコア $k'$ 以下であるところの $r=(t-1,t-2,\cdots,2,1,{\color{blue}t},t+1,\cdots, n)$ の左から $t$ 番目の位置にある $t$ に注目すると、 $1\le i\lt t$ について $r_i \lt r_t$ になっている
スコア $k'$ 以上であるところの $r=(t,t-1,\cdots,3,2,{\color{blue}1},t+1,\cdots, n)$ の左から $t$ 番目の位置にある $1$ に注目すると、 $1 \le i\lt t$ について $r_i \gt r_t$ になっている

ことが分かります。さらに、この $2$ つの順列について「 $i, j$ が $t$ に関係しない組 $(i, j)$ についての $r_i, r_j$ の大小関係は一緒」ということも分かります。

左から $t$ 番目の位置にある値を $1$ 個ずつ上げていく操作をする（ただし他の組の大小関係は変わらないようにする）と、 $k'$ 以上だったスコアがどんどん下がります。

操作 $1$ 回ごとに $(i, j)$ の組の大小関係が $1$ つだけ「 $\gt$ 」から「 $\lt$ 」に変わるのでスコアは $0$ または $1$ 減ります。 $1$ を $t$ まで上げるとスコアが $k'$ 以下になることは分かっているので、どこかで必ず $k'$ になります。ここでストップすればよいです。

つまり、完成品は、ある $1 \le s \le t$ が存在して、 $r=(t,t-1,\cdots,s+1,s-1,\cdots,2,1,s,t+1,t+2,\cdots, n)$ となります。 $s$ は左から $t$ 番目の位置にあります。

PART 4

PART 3 の実装をします。まず $t$ を決めたいと思います。 $r=(t,t-1,\cdots,2,1,t+1,t+2,\cdots, n)$ のスコアは、「 $1 \le i \lt j \le t$ かつ $p_i \lt p_j$ の個数」です。

よって、BIT かセグメント木などを使うと、転倒数と同じように $t=1,2,\cdots, n$ について $r=(t,t-1,\cdots,2,1,t+1,t+2,\cdots, n)$ のスコアを求めることができます。スコアが $k'$ 以上になる最小の $t$ を採用すればよいです。

次は調整ですが、 $i=t-1,t-2,\cdots, 1$ の順に、 $r_i \gt r_t$ だったものを $r_i \lt r_t$ に解消していきます。もし $p_i \lt p_t$ だったらスコアが $1$ 下がり、そうではなかったらスコアは下がりません。スコアが $k'$ になったらストップし、 $q_{p_i} = r_i$ を用いて $q$ を求めて出力すればよいです。