ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Codeforces Round #590 (Div. 3) E. Special Permutations

Codeforces プログラミング競技プログラミング

お題箱より。

Problem - E - Codeforces

Editorialのソースコードがよく分からないというリクエストだったんですが、見たところ確かによく分からなかったので、私の解法を書きます。

問題概要

長さ $n$ の順列 $p_{i}$ を $\lbrace i, 1, 2, ..., i-1, i+1, ..., n\rbrace$ と定義する。

長さ $m$ の整数列 $x = \lbrace x_{1}, ..., x_{m}\rbrace$ （ $1 \le x_{i} \le n$ ）が与えられる。長さ $n$ の順列 $p$ に対して、 $f(p)$ の値を「 $x$ において隣り合う2要素の組全てについて、その2整数の $p$ での距離を求めたものの合計」と定義する。

それぞれの $p_{i}$ に対する $f(p_{i})$ の値を求めよ。

制約

$2 \le n, m \le 2\times 10^{5}$
$1 \le x_{i} \le n$

解法

$x$ における隣り合う2要素の組それぞれについて、それが $f(p_{i})$ の値にどう影響するか考えていきます。

隣り合う2要素が同じ整数である場合は、距離はゼロなのでその組は $f(p_{i})$ の値に影響しません。異なる値である場合、これらを小さい方から順に $a, b$ と表記することにします。

整数 $a, b$ の距離は、 $p_{1}, ..., p_{n}$ それぞれにおいていくつになるでしょうか。これは以下のように少ないパターン数に分けられることが分かります。

$i \lt a$ のとき、 $p_{i}$ において $a, ..., b$ の並びはそのまま保持されるので、距離は $b-a$ 。
$a \lt i \lt b$ のとき、 $p_{i}$ において $a$ と $b$ の間にある整数 $i$ が先頭に移動するので、距離は $b-a-1$ 。
$i = a$ のとき、 $p_{i}$ において $a$ が先頭で $b$ が $b$ 番目にあるので、距離は $b-1$ 。
$i = b$ のとき、 $p_{i}$ において $b$ が先頭で $a$ が $a+1$ 番目にあるので、距離は $a$ 。
$b \lt i$ のとき、 $p_{i}$ において $a, ..., b$ の並びはそのまま保持されるので、距離は $b-a$ 。

ざっと書きましたが、パターンはこれだけです。これらの値がそれぞれの $f(p_{i})$ に加算されます。同じ値を取る連続した区間（または1点）を1回の範囲加算で扱えると見なすと、これは高々5回の範囲加算で処理することができます。

$x$ における隣り合う2要素の組は $m-1$ 個あるので、結局は高々 $5(m-1)$ 回の範囲加算を行った結果が答えになります。そしてたくさんの範囲加算を行った結果を得るための方法と言えば「いもす法」です。これで解くことができます。

ACコード

Submission #62410726 - Codeforces