CodeChef February Lunchtime 2018: Couples sit next to each other

CodeChefのコンテスト"February Lunchtime 2018"の問題。

問題: https://www.codechef.com/LTIME57/problems/COUPLES
問題名: "Couples sit next to each other" (Code: COUPLES)

N組のカップルがいて、2N人は2N個の椅子に座っている。椅子は円形に並んでおりi番目と(i+1)番目、2N番目と1番目の椅子は隣接しており、i番目の椅子には ${A_i}$ 番目のカップルの人が座っている。
ここから、隣接する人同士を入れ替えることで、最終的に各カップルが隣接するようにしたい。この状態を作るのに必要な最小交換回数は何回か、を答える問題。

コンテスト中、うまく解法が降ってきて解けた。そのメモ。

解法

この問題は、解をどのように計算するかを考えて部分点 ${(N \le 1000)}$ をとり、その上で計算を改善して満点 ${(N \le 500000)}$ を取る。

部分点解法

まず、最小交換回数を考える。今回は、人の並びをどのように入れ替えていくか、ではなく、何を入れ替える必要があるか、を考察する。

ここで、各カップルiの2人について、一方の人を時計回りもしくは反時計周りでもう一方に交換しながら近づけて隣接させることを考える。
まず、カップルiと、あるカップルjの位置関係に注目する。この時、 ${A_1, \dots, A_{2N}}$ における並びのパターンは２つ存在する。

パターン1: 2組の関係がクロスする場合
- 並び: "i, j, i, j" or "j, i, j, i"
パターン2: 2組の関係がクロスしない場合
- 並び: "i, i, j, j" or "j, j, i, i" or "i, j, j, i" or "j, i, i, j"

パターン1については、iとjのクロス関係を解消しなければそれぞれのカップルを隣接関係にできないため、どちらの方向に近づけても1回交換する必要がある。そして、このクロス関係は1回の交換で1つのみ解消できるため、このパターンではクロス関係となるペア(i, j)の数だけ交換回数が増える。
パターン2については、カップルiの人を近づける方向によってはカップルjの2人との交換を回避でき、その場合は交換回数が増えないが、回避せず交換した場合は2回交換することになる。これを考慮し、各カップルiに対してパターン2の関係になる全てのカップルjを列挙した上でそれぞれの方向から近づけた際に必要となる交換回数の和を計算し、回数が少なくなる方向を選ぶとよい。*1

この考察を元に、交換回数は以下のように計算できる。

パターン1の関係にある ${i, j (i < j)}$ のペア数 ${P}$ を計算
各カップルiについて、時計回りと反時計回りの2つの区間についてパターン2のカップルを列挙し、その交換回数が少ない方の回数を ${Q_i}$ とする
最終的な交換回数として ${P + \sum_{i} Q_i}$ を出力する

この解は単純に ${O(N^2)}$ で計算でき、部分点が取れる。
提出(Python3): Solution: 17527725 | CodeChef

満点解法

実は、各カップルiに対してクロスするカップルの組数 ${C_i}$ を計算できれば、2つの区間の長さをそれぞれ ${L_i, R_i (= 2N - 2 - L_i)}$ とする時、最終的な交換回数は ${\frac{1}{2}\sum_i C_i + \sum_i (\min(L_i, R_i) - C_i)}$ で計算できることが分かる。
そのため、この ${C_i}$ を計算することを考える。

ここで ${A_1, \dots, A_{2N}}$ を前から順番に見た時にi番目で ${A_i = k}$ が出現したとする。
この時点で数字kが初めて出現した場合、以下のことが言える。

ここまでで1度だけ出現した数字lとはクロスした関係になりうる
- "l, k, l, k" もしくは "l, k, k, l" の一方の順序になる
- ここで ${C_l \leftarrow C_l + 1}$ と更新

この時点で数字kが2度目の出現の場合、以下のことが言える。

ここまでで1度だけ出現し、kが出現する前に出現した数字lについて、kとlはクロスした関係にならない
- "l, k, k, l"という順序になる
- ここで ${C_l \leftarrow C_l - 1}$ と更新
ここまでで1度だけ出現し、kが出現した後に出現した数字lについて、kとlはクロスした関係になっている
- "k, l, k, l"という順序になる
- ここで ${C_l \leftarrow C_l + 1}$ と更新

この各 ${C_i}$ を計算するための値の管理はBITでできる。そのため、各 ${C_i}$ は ${O(N \log{N})}$ で計算できる。

自分のBIT解法は大雑把に以下の通り。

${A_1, \dots, A_{2N}}$ を前から順番に見ていき、各数字を出現順に1,2,...とラベル付けし直した ${B_1, \dots, B_{2N}}$ を考える。この ${B_i}$ について ${B_1}$ から順番に見ながらBITを更新し、各 ${C_i}$ を計算することを考える。
まで見て、が始めて出現する数字(k)の場合、BITで区間を+1して更新する。
- "1, ..., k-1"はkが出現する前に出現した数字
が2回目に出現した数字(k)の場合、この時点のBITにおけるk番目の値をとする。そしてBITで区間を-1、区間を+1して更新する。
- "k+1, ..." はkが出現した後に出現する数字