筆者はレート800前後の茶～緑コーダ
ABC436当日にACできなかったE問題を解いていく
実装コード
解説によると
与えられた順列Pを使い、
頂点iと頂点P[i]を結ぶ辺を考えて、そのグラフの連結成分の個数Cを考えれば
最小回数はK=N-Cで求められるらしい…
そこからK回辺を結ぶ作業に言い換えられるようで、
どの辺を結べばいいのかというと、同じ連結成分にある2頂点を選ぶらしい
あとはそれぞれのサイクルの大きさを求めればOK…のようだが
上記の解説では全くわからないのでGPTに解説してもらった。
GPTの解説
main.py がやってることは、**「最小手数で直すとき、1手目として選べる swap (i, j) の個数」**を サイクル分解で数えてる、それだけです。以下、その「だから何？」を「なるほど」に変える説明いくね。
1 この問題、何を数えてる？
問題文はこう：P を swap だけで (1,2,...,N) にしたい。最小手数を K とする。その 最小手数 K を達成できる手順のうち、1手目としてあり得る (i, j) の数を出せ、という話。
2 「i と P[i] を結ぶグラフ」＝置換のサイクルそのもの
解説が言ってるグラフ：
- 頂点は
1..N - 各
iに対してiとP[i]を辺で結ぶ
P は置換（重複なし）だから、各頂点は
-
P[i]側から見ても 1 回つながる -
i -> P[i]も 1 回つながる
みたいな構造になって、**連結成分は全部「サイクル」**になります（解説にもそう書いてある）。
つまりここでいう連結成分数 C って、ふつうに
Pをサイクル分解したときのサイクル個数
と同じ。
3 なぜ最小回数が K = N - C になるの？
ゴールの (1,2,...,N) は「全員が自分にいる」状態なので、サイクルが
-
(1)(2)...(N)の N 個
になります
だから、サイクル個数を C → N に増やす必要がある。
ここで swap の効き方が （ここだけ分かれば勝ち）：
-
i, jが 同じサイクルにいるとき swap すると、そのサイクルが 2つに割れてCが +1 -
i, jが 別サイクルにいるとき swap すると、サイクルが 合体してCが -1
つまり、1回の操作で C を増やせても 最大 +1。
だから N まで増やすには最低でも N-C 回必要。
さらに解説は「N > C の間は、同じ連結成分内の2頂点（例: (i, P[i])）が必ずあるから、C を 1 ずつ増やし続けられる」と言ってて、実際に達成できる。
よって 最小手数 K = N - C が確定。
4 で、「1手目としてあり得る swap」は結局どれ？
最小手数で行くなら、1手目で C を減らす（別サイクルを混ぜる）と、その分あとで取り返す必要が出て手数が増える。
だから 1手目は必ず「同じサイクル内の2頂点」を選ぶ必要がある。
そして解説の強い一言：
同じ連結成分にある 2 頂点であれば、どの組を選んでもよい
つまり答えは
各サイクルの中から 2 個選ぶ組の総数
です。
サイクルサイズが c なら、その中のペア数は c*(c-1)/2。
よって答えは
$$
\sum_{\text{cycle}} \binom{c}{2}
$$
これ。
5 main.py がやってること（これで完全に一致）
コードは
- まだ見てない頂点
iからP[i]を辿ってサイクル長cを数える - そのサイクルに属する全頂点に
ans[v] = cを入れる - 最後に
print((sum(ans)-N)//2)
ここが気持ち悪く見えるポイントだと思うので変形すると：
-
1つのサイクル（長さ
c）では、ansにcがc個入る- だからそのサイクルの
ans合計はc*c
- だからそのサイクルの
-
全体で
sum(ans) = Σ c^2 -
sum(ans) - N = Σ (c^2 - c) = Σ c(c-1) -
それを
//2するとΣ c(c-1)/2 = Σ C(c,2)
つまり出力は、狙い通り **「同じサイクル内の (i<j) の総数」**になってる。
6 5秒で腑に落ちるミニ例
例：サイクルが (1 2) と (3 4 5) の2個だとする（C=2、N=5）
-
最小手数は
K = 5 - 2 = 3 -
1手目に選べるのは「同じサイクル内のペア」
-
(1 2)からは 1 通り -
(3 4 5)からは 3 通り（(3,4),(3,5),(4,5)）
-
-
合計 4 通り
式でも
2*1/2 + 3*2/2 = 1 + 3 = 4 で一致。
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
N = rI()
P = rLI1()
ans = [0] * N
for i in range(N):
if ans[i]:continue
c = 0
p = i
while True:
c += 1
p = P[p]
if p == i: break
while True:
ans[p] = c
p = P[p]
if p == i: break
print((sum(ans)-N)//2)
if __name__ == '__main__':
main()
感想
順列を並び替える作業を
グラフに変換して辺を結ぶ作業に言い換えるっていう点から
なかなか高度な話だし
そこからサイクルを考えて計算しようという話も
正直あまりわかってない。
今回は昨日のABCの解き直しみたいな感覚で取り組んだが、
はっきり言って写経に近い実装になってしまったので、
今の地力を考えて解く問題を選んでいきたい。