2019-10-29

Codeforces Round #595 (Div. 3) D2. Too Many Segments (hard version)

お題箱より。

問題概要

整数を端点とする $n$ 個の閉区間 $\lbrack l_{i}, r_{i}\rbrack$ が与えられる。これらから0個以上の区間を捨てて、全ての整数点について「その整数点を含んでいる区間は $k$ 個以下である」という状態にしたい。

捨てる区間の最小個数と、その選び方の1例を求めよ。

制約

$1 \le k \le n \le 2\times 10^{5}$
$1 \le l_{i} \le r_{i} \le 2\times 10^{5}$

解法

小さい方を左として、左から順番に整数点を見ていきます。このとき各整数点について「今見ている整数点を含んでいる区間が $k$ 個以下となる」ように区間を捨てていきます。

具体的には「残す区間であって、今見ている整数点を含むもの」の集合を管理するようにします。そして整数点 $i$ を見る時には以下の処理をします。

$i$ を左端とする区間を、いったん全て集合に入れる。
集合に含まれる区間数が個を超えている場合、個以下になるまで↓を繰り返す。
- 集合の中で右端が最も右にある区間を捨て、集合から取り除く。
集合の中に $i$ を右端とする区間がある場合、この区間から出るので集合から取り除く。

この方法で捨てる区間の個数が最小となり、その選び方の1例を求められます。

その理由を考えてみましょう。この処理を左側の整数点から順に行っていくと、整数点 $i$ を見るときにはそれより左の整数点は既に条件を満たしています。つまり集合に入っている区間が $i$ より左側のどこまで伸びているかは、もはや考えなくて良いです。2.において捨てる区間を選ぶときには、 $i$ より右側で最も邪魔になりやすい区間、つまり右端が最も右にある区間を捨てるのが常に最適になります。

つまり区間を管理する集合においても、左端は必要なくて右端の値（と出力のためのインデックス）が保持されていれば良いです。この集合に必要な機能は

含まれている区間の個数が分かる。
右端の値が最も大きい区間の番号を求め、取り除くことができる。
右端の値がある値と等しい区間を取り除くことができる。

ことです。これはC++であれば set 等で実現できます。

言語機能にない場合は、BIT等に入れておいて二分探索する等の方法があります。もしくはPython等にもある優先度付きキューで1.と2.の機能は実現できるので、3.を工夫して代用しても良いです。集合に入っている値の頻度表を別途作っておき、「区間から出る」ことで除かれるはずの要素数を別途計算しておけば、その分だけキューの中の要素数から差し引くことで同じことができます。

ACコード

（C++ set利用）Submission #63665793 - Codeforces
（Python heapq利用）Submission #63666907 - Codeforces

リクエストくれた人の使用言語が分からなかったのですが、順序付き集合が使えるかどうかで若干実装が異なるのでC++とPythonの実装例を紹介しておきます。

私はこのコンテストの本番では区間加算ができるセグメント木を使いました。解法、実装手段は色々あると思います。

2019-10-21

Kyoto University Programming Contest 2019 E - 根付き森二人用ゲーム

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

お題箱より。

E - 根付き森二人用ゲーム

解法

それぞれの木を小規模なゲームとして解く

スタート地点からある木に移動し、その木の葉に到達してスタート地点に戻るまでの一連の動作を考えます。このときゲームに本質的に影響するのは「次にスタート地点で手番を持つプレイヤーが交代するかどうか」だけです。これは到達した葉の深さの偶奇に依存します。

この観点で、それぞれの木に対して小規模なゲームを考えます。以下の2つのゲームを考え、それぞれの勝敗を調べます。ここで「先手」はスタート地点からその木に移動するプレイヤー（木を選ぶ人）、「後手」はその後に根から最初の移動をするプレイヤーを指します。

ゲーム1：先手は手番を交代したい、後手は手番を交代したくないと思って行動する。結果として手番が交代すれば先手の勝ちである。両者が最適に行動するとどちらが勝つか？
ゲーム2：先手は手番を交代したくない、後手は手番を交代したいと思って行動する。結果として手番が交代すれば後手の勝ちである。両者が最適に行動するとどちらが勝つか？

これは後退解析によって求めることができます。まず葉については深さの偶奇から手番交代する/しないが分かるので、その葉がどちらの勝ち状態であるかが分かります。あとは根まで順に辿っていき、各頂点がどちらの勝ち状態かを判定します。その判定方法は「その頂点からの遷移先に自分の勝ち状態であるものが1つでもあれば勝ち、そうでなければ負け」です。

この2つのゲームの結果から、それぞれの木は以下のように分類できます。

タイプA：どちらも先手プレイヤーが勝つ。つまり先手プレイヤーが手番交代の有無を選べる。
タイプB：どちらも後手プレイヤーが勝つ。つまり後手プレイヤーが手番交代の有無を選べる。
タイプC：どちらの場合でも、結果として手番が交代する。
タイプD：どちらの場合でも、結果として手番が交代しない。

全体の勝敗判定をする

このように分類したもののうちタイプDは勝敗に影響しません。残りの3タイプの木の個数を用いて、ゲームの状態を3つの整数の組 $(a, b, c)$ で表現します。入力として与えられる木を分類して求めたそれぞれの個数を $(A, B, C)$ とすると、これがゲーム開始時の状態です。

単純に考えると、ここでも後退解析を使いたくなります。つまり $(0, 0, 0)$ の状態で手番を持ったプレイヤーは負けであり、DPのように値が小さい方から順番に $0 \le a \le A, 0 \le b \le B, 0 \le c \le C$ なる全ての $(a, b, c)$ について後退解析で勝敗を求めていけば、一応判定することはできます。ただ計算時間が間に合いません。

もっと楽に判定できないか考えましょう。例えば $(a, b, c)$ という状態からタイプAの木を1つ消費した状態 $(a-1, b, c)$ の勝ち負けは、どちらかは計算できていませんがどちらかに定まっているはずです。ならば先手はこれが負け状態であれば手番を交代して相手に押し付け、勝ち状態であれば再び自分の手番にすることで必ず勝つことができます。

同様にタイプBの木を選んでしまうと、相手に勝てる方を選ばれてしまい必ず負けます。つまり、タイプAやタイプBの木によって選択権利を持ったプレイヤーはその時点で勝ちが確定します。

つまりこのゲームの勝敗は、以下のように判定することができます。

タイプAの木が存在する（ $A \gt 0$ である）場合、真っ先にその木を選べば良いので必ず先攻のAliceが勝つ。
そうでない場合、手番プレイヤーはタイプBの木を選びたくないので、タイプCの木が尽きるまで選ばれ続ける。タイプCの木が尽きた時点で手番を持ったプレイヤーが、タイプBの木を選ぶ（または全ての木が尽きる）ので負ける。つまり $C$ の偶奇により勝敗が決まる。

ACコード

Submission #7957578 - Kyoto University Programming Contest 2019

2019-10-21

Codeforces Round #594 (Div. 1) B. The World Is Just a Programming Task (Hard Version)

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

Problem - B - Codeforces

問題概要

長さ $n$ の括弧列 $S$ が与えられる。長さ $n$ の括弧列のスコアを、「 $S$ を $k$ 回だけ右巡回シフトした文字列が正しい括弧列になっている」という条件を満たす $k (0\le k \lt n)$ の個数とする。

$S$ に対して1度だけ、2箇所を選んでスワップする操作を行うことが出来る（同じ位置を選んでもよい）。操作後の $S$ の最大スコアと、そのスコアを実現するスワップ位置の1例を求めよ。

制約

$1 \le n \le 300000$

解法

巡回シフトが正しい括弧列になる条件

正しい括弧列の問題では ( を $+1$ 、) を $-1$ とした累積和を考えるのが定石です。この値が全て非負でありかつ最後に0になることが、文字列が正しい括弧列である必要十分条件です。

与えられた文字列について、以下のように $\pm 1$ に変換した数列 $\lbrace a_{i}\rbrace$ とその累積和の列 $\lbrace C_{i} \rbrace$ を求めます。

f:id:betrue12:20191020234126p:plain

まず $C_{n} = 0$ であることは大前提です。そうでない場合、シフトやスワップをどうやってもスコアは絶対に0なので適当なスワップ位置を答えて終了します。

巡回シフト後の文字列が正しい括弧列になっている必要十分条件は、 $C_{i}$ の中で最も値が小さい位置が左端になるようにシフトすることです。つまり $C_{i}$ が最小値を取るような $i$ の個数がそのままスコアになります。

このとき $C_{0}$ と $C_{n}$ は同じシフトに対応するのでダブって数えてはいけません。以降は $C_{1}, ..., C_{n}$ を数える対象として扱います。

スワップが累積和に与える影響

次にスワップの影響を考えます。同じ文字同士をスワップした場合は当然何の変化もありません。異なる文字をスワップした場合には、

左側にある $+1$ と右側にある $-1$ をスワップすると、その間にある $C_{i}$ が $-2$ される。
左側にある $-1$ と右側にある $+1$ をスワップすると、その間にある $C_{i}$ が $+2$ される。

という変化があります。

スワップ後の累積和を $C_{i}^{\prime}$ と表記します。 $C_{i}$ の最小値を $m$ とすると、 $C_{i}^{\prime}$ の最小値は $m-2$ 以上 $m+2$ 以下の範囲に存在することが分かります。

最小値とスワップの正負を決め打ってDP

最小値の候補は5個で、スワップによって $-2$ されるか $+2$ されるかは2通りです。これらを決め打って全部試します。

スワップ後の最小値として決めた値を $t$ とします。このとき、 $t$ より小さい $C_{i}^{\prime}$ があってはならず、 $t$ に等しい $C_{i}^{\prime}$ の個数がスコアになります。

また、左側にある $+1$ と右側にある $-1$ をスワップすると仮定します。このときこの2要素の間にある累積和については $C_{i}^{\prime} = C_{i}-2$ となります。

このとき $C_{i}^{\prime}$ は、左から順に

ゾーン0： $C_{i}^{\prime} = C_{i}$ である。
ゾーン1： $C_{i}^{\prime} = C_{i} - 2$ である。
ゾーン2： $C_{i}^{\prime} = C_{i}$ である。

という3つのゾーンに分かれます。

f:id:betrue12:20191021000822p:plain

このゾーンに基づいてDPを定義します。つまり

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 累積和 $C_{i}^{\prime}$ まで見て、 $C_{i}^{\prime}$ はゾーン $j$ に属していて、 $t$ より小さい $C_{i}^{\prime}$ はこれまで存在していないときの、 $t$ に等しいこれまでの $C_{i}^{\prime}$ の個数（スコア）の最大値

というDPを考えることができます。

$dp\lbrack i \rbrack\lbrack j \rbrack$ からの遷移を考えます。まず同じゾーンへの遷移があります。それに加えて今は左側にある $+1$ と右側にある $-1$ をスワップすると仮定しているので、 $a_{i} = +1$ であるときにはゾーン0→1の遷移、 $a_{i} = -1$ であるときにはゾーン1→2の遷移が起こり得ます。

遷移後のゾーンを $k$ とします。遷移後の累積和 $C_{i+1}^{\prime}$ の値は、元の $C_{i+1}$ に遷移後の所属ゾーン $k$ に応じた変化量を足したものです。これが $t$ より小さい場合は遷移を却下します。ちょうど $t$ である場合はスコアを1増やして、そうでない場合にはスコアそのままで、 $dp\lbrack i+1 \rbrack\lbrack k \rbrack$ に遷移します。

最後まで遷移すると、 $dp\lbrack n \rbrack \lbrack 0 \rbrack$ には「スワップしなかった場合の最大スコア」、 $dp\lbrack n \rbrack \lbrack 2 \rbrack$ には「スワップした場合の最大スコア」が入っています。前者を採用する場合は適当に同じ位置をスワップしたことにします。後者を採用する場合はDPの復元を行ってスワップ位置を特定します。

これを最小値の候補5個とスワップによって変化する値2通りの組み合わせ全てについて試し、最も大きいものが答えです。

ACコード

本番コード Submission #62994535 - Codeforces
書き直しコード Submission #63023084 - Codeforces

本番の実装が分かりにくかったので書き直しましたが、定数倍が悪くなってちょっと実行制限時間ギリギリになりました…なので両方リンク貼っておきます。この記事の記法等に合わせているのは書き直しコードのほうです。

2019-10-20

AtCoder Beginner Contest 143 F - Distinct Numbers

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

F - Distinct Numbers

解法

色々な解法があるみたいですが…この記事ではそれぞれの $K$ について独立に解きます。ある $K$ について解くときには、可能な操作回数には単調性があるので二分探索できます。

ある $K$ と操作回数 $n$ を固定したときに、操作を $n$ 回行えるかどうか判定する方法を考えます。まず $nK \le N$ は必ず満たす必要があります。その上で $\lbrace A_{i}\rbrace$ の中から使う整数を $nK$ 個選んで

(*) 全部で $nK$ 個の整数から、「異なる $K$ 個の整数を取り除く」という操作を $n$ 回行うことができる

かどうかを判定したいです。このとき(*)の必要十分条件として、

全ての整数値 $v$ について、 $nK$ 個の中に $v$ が含まれる個数は $n$ 個以下である

というものがあります。

必要性については、もし $n$ 個を超える整数値が存在する場合はそれらを $n$ 回の操作で全て取り除くことができないことから示せます。

十分性については、以下のようにすると実際に構成できることから示せます。（Special Thanks:てんぷらさん）

f:id:betrue12:20191020000241p:plain

つまり $\lbrace A_{i}\rbrace$ から各整数値を $n$ 個以下取ってきて、合計で $nK$ 個確保できればOKということになります。これは以下のように解くことが出来ます。

まず $\lbrace A_{i}\rbrace$ を「整数値○が $B_{1}$ 個、整数値△が $B_{2}$ 個…」という風に集計したときの数列 $\lbrace B_{i}\rbrace$ を求めて、これをソートしておきます。このとき各整数値を $n$ 個以下取ろうとすると、

$B_{i} \lt n$ であるような $B_{i}$ については全て取る。
$B_{i} \ge n$ であるような $B_{i}$ についてはそれぞれ $n$ 個ずつ取る。

ということになります。1.と2.の境界を二分探索などで求めて、1.については累積和を求めておくと、取れる個数の合計を効率的に求めることが出来ます。これが $nK$ 以上かどうか判定すれば良いです。

この解法だと全ての $K$ を試すので $O(N)$ 、答えを求めるための二分探索で $O(\log N)$ 、 $B_{i} \lt n$ を満たす境界を求めるのに $O(\log N)$ で、全体 $O(N(\log N)^{2})$ になります。ちょっと重いですね。 $B_{i} \lt n$ を満たす境界を全ての $n$ について前計算しておくと $\log$ が1個落ちるなど、計算量の改善は色々あると思います。

ACコード

Submission #8035553 - AtCoder Beginner Contest 143

2019-10-19

AtCoder Regular Contest 077 E - guruguru

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

お題箱より。

E - guruguru

後半は公式解説と少し違う方法になっています。

解法

お気に入りで節約できる回数を定式化する

ある1つの $i$ に対する $a_{i}$ から $a_{i+1}$ への移動を考えます。まず簡単のため、 $a_{i} \lt a_{i+1}$ と仮定しておきます。移動元と移動先をそれぞれ $s_{i} = a_{i}, t_{i} = a_{i+1}$ と書くことにします。

お気に入りボタンを使わずに $s_{i}$ から $t_{i}$ に移動するボタン回数は $t_{i}-s_{i}$ です。ここで「 $t_{i}-s_{i}$ と比べて、お気に入りボタンがもし値 $x$ に設定されていたら回数をどれだけ節約できるか？」という値をそれぞれの $x$ について考えましょう。この値を $f_{i}(x)$ と書くことにします。

これは以下のように、 $s_{i} + 2 \le x \le t_{i}$ の範囲において $1, 2, ...$ という等差数列になり、他は0になります。

f:id:betrue12:20191019155240p:plain

ただし $a_{i} \gt a_{i+1}$ のときは途中で明るさがループします。これを扱うのは面倒なので、「ループするときは2周回す」テクニックを使います。

$a_{i} \gt a_{i+1}$ のときは移動先 $t_{i}$ は2周目にあると考えて、 $s_{i} = a_{i}, t_{i} = a_{i+1} + m$ とします。そして $f_{i}(x)$ も2周分、つまり $1 \le x \le 2m$ の範囲で値を持つことにします。このときお気に入りが $x$ に設定されている時の節約回数は、1周目と2周目を合わせて $f_{i}(x) + f_{i}(x+m)$ と求めればよいです。

これを $n-1$ 回の移動について全て足したもの、つまり $\sum_{i}f_{i}(x) + \sum_{i}f_{i}(x+m)$ が「お気に入りを $x$ に設定したときに、お気に入りを全く使わない時に比べて節約できる合計回数」です。この最大値を、お気に入りを全く使わない時の合計回数 $\sum_{i} (t_{i} - s_{i})$ から引いたものが答えになります。

こうなると残る課題はそれぞれの $\sum_{i}f_{i}(x)$ を求めること。つまり「数列に『ある区間だけに等差数列を足す』という操作をいくつも行った結果」を効率的に求めることになりました。

等差数列の重ね合わせを求める

ここで使うのは「階差数列」を利用するテクニックです。

話が変わりますが、「いもす法」というテクニックがあります。1次元のいもす法は「ある区間だけに同じ値を足す」という操作をいくつも行った結果を効率的に求めるテクニックです。これは以下のように、階差数列を利用しているテクニックと思うことが出来ます。

f:id:betrue12:20191019163129p:plain

「ある区間だけに同じ値があり、区間外は全て0」という数列は、1階の階差数列を取ると上記のように0でない値が2箇所だけになります。

「階差数列を取る」という操作と「累積和を取る」という操作はちょうど逆の操作になっていて、かつこれらの操作には線型性があるので、足したい数列たちの階差数列を足してから累積和を取ることで元の数列たちの和が得られます。

同様のことが等差数列でもできます。今回の $f_{i}(x)$ のように「ある区間だけに等差数列があり、区間外は全て0」という数列は、2階の階差数列を取ることで0でない値が3箇所だけになります。

f:id:betrue12:20191019163416p:plain

よって $n-1$ 回の全ての移動についてこれらの値を足した後、2回累積和を取ることで全ての $x$ に対する $\sum_{i}f_{i}(x)$ を求めることができます。

ACコード

Submission #7983845 - AtCoder Regular Contest 077

2019-10-17

Codeforces Global Round 5 E. Balanced Binary Search Trees

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

Problem - E - Codeforces

問題概要

以下の条件を満たす根付き木を二分探索木と呼ぶ。

任意の頂点について以下が成り立つ。
- 「左側の子」と「右側の子」がそれぞれ高々1個存在する。
- 左側の子孫が存在する場合、それら全ての頂点番号は $i$ より小さい。
- 右側の子孫が存在する場合、それら全ての頂点番号は $i$ より大きい。

頂点番号 $1, ..., n$ の $n$ 頂点からなり、以下の条件を満たす二分探索木の個数を $\bmod 998244353$ で求めよ。

頂点数 $n$ の二分探索木の中で、各頂点の深さの合計が最小である。
任意の頂点について以下が成り立つ。
- 左側の子が存在する場合、その頂点番号の偶奇は $i$ と異なる。
- 右側の子が存在する場合、その頂点番号の偶奇は $i$ と等しい。

制約

$1 \le n \le 10^{6}$

解法

$\bmod 998244353$ というハッタリがありますが、実は条件を満たす木は高々1つです。その理由を説明します。

まず深さの合計が最小であるという条件は、直感的にはできるだけ根に近いところに頂点が集まっているということです。これは具体的には、木の最下段以外は頂点が詰まっている、つまり完全二分木になっているということを意味します。

ということでまずは、完全二分木になっている部分の深さの最大値 $D$ を求めます（根を深さ0とします）。これは $2^{D+1}-1 \le n$ を満たす最大の $D$ として求められます。このとき深さ $D+2$ 以上の頂点は存在しません。

f:id:betrue12:20191017195356p:plain

条件を満たす木の構成を、以下のように試みましょう。

まず頂点番号 $1, ..., n$ のうち $2^{D+1}-1$ 個を使って、偶奇の条件を満たすような深さ $D$ までの完全二分木を作る。
上記で使わなかった（飛ばした）頂点たちを、深さ $D+1$ の段に適切に付けられるか考える。

ここで飛ばした頂点は、大小関係から「付ける場合は、深さ $D$ のこの頂点のこちら側に付けなければいけない」という位置が一意に定まります。つまりもし連続して2つ以上の頂点が飛ばされている場合、それはどう頑張っても深さ $D+1$ の段には収まりません。これが完全二分木を作る上で強い制約になります。

完全二分木の頂点番号を、番号の小さい位置から順番に決めていきます。番号が最も小さい頂点は左下の頂点ですが、連続して1, 2を飛ばしてはいけないので、左下の頂点は1または2である必要があります。これはとりあえず両方試すことにします。

ある1つの頂点の偶奇が決まると全ての頂点の偶奇が決まります。各頂点の偶奇が指定され、2つ以上の頂点番号を飛ばしてはいけないので、全ての頂点番号が小さい方から順に一意に定まっていきます。

あとは飛ばした頂点が深さ $D+1$ の段に適切に付くかどうかを確認します。頂点番号を飛ばすようなパターンを実際に列挙してみると、ほとんどの飛ばした頂点は偶奇条件に合うように $D+1$ の段に上手く収まります。NGとなるのは完全二分木の右下の頂点番号が $n$ ではない場合です。 $n$ を超えている場合は当然NG、 $n-2$ 以下である場合はそれ以降を連続で飛ばすことになるのでNG、 $n-1$ である場合はその右下に偶奇の異なる $n$ を付けると条件違反になるのでNGです。

このことから結局、完全二分木の右下の頂点番号は必ず $n$ にならないといけないので、左下の頂点の偶奇も片方しか条件を満たさないことになります。これが、条件を満たす木が高々1つである理由です。

以上の考察より、私の解法は以下のようになりました。

完全二分木の深さ $D$ を、 $2^{D+1}-1 \le n$ を満たす最大の $D$ として求める。
完全二分木の左下の頂点の番号を1または2と仮定してそれぞれ試す。DFSのように完全二分木の頂点番号を小さい順に決めていく。その結果、右下の頂点番号が $n$ となった場合、これは条件を満たす。
条件を満たす木の個数を出力する。これは高々1個である。

もしくは、答えが1になる $n$ を並べてみると単純な漸化式を持つ数列になるようです。これを実験等で突き止めて信じる心を持てば、実際に木を構成しなくても解くことができます。

E、10万以下で作れるN pic.twitter.com/qkWyfLih8z
— アルメリア (@armeria_betrue) October 16, 2019

ACコード

Submission #62712082 - Codeforces

2019-10-12

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$ 。