2023/8/21 文章を修正しました。
問題文(英語) https://codeforces.com/contest/1855/problem/A
問題概要
N人の生徒が1列に並んでおり、生徒 i (1≦i≦N)は椅子 p[i](1≦p[i]≦N)に座っている。先生は生徒を2人選んで交換する動作を行える。この時、すべての生徒と椅子の番号が異なるようにするために必要な最小の交換回数を求めよ。
知っている方向け: 2つの数を選んで入れ替え、完全順列にする時の最小回数を求めよ。
条件
- 1 ≦ (テストケース数) ≦ 1000
- 2 ≦ N ≦ 105
- pは[1, 2,…N]の並び替え
- (全てのテストケースのNの総和)≦105
- 答えは必ず存在する
例:テストケース3
5
1 2 5 4 3
出力例:
2
最初は下図のような状態。
例えば、人1と人2を入れ替え、さらに人2と人4を入れ替えることで2回で椅子の番号と人の番号が異なるようにできる。
解説
まず、「どの人を入れ替えるべきか」を考える。すると、人と席の番号が同じになっている人は入れ替える必要がある。(先ほどの例では人1, 2, 4)
この条件を満たしている人を今後は単に「条件を満たす人」と呼ぶことにする。
もし、「条件を満たす人」が2人いた場合、2人の場所を交換すれば、2人とも人と席の番号が異なるものになる。そのため、「条件を満たす人」から2人組のペアを作っていき、ペア同士でそれぞれ1回交換すれば良いから、ペアの個数が答えになることが分かる。
問題は「条件を満たす人」が奇数人存在する時で、この時は2人ペアを作っていくと1人余ってしまう。しかし、この1人も全てのペアを交換し終わった後に誰とでも交換可能である。それは、条件を満たす人は交換すると番号が変わり、満たさない人も交換先の席と同じ番号は満たす人が持っているため、確実に移動先の席と同じ人の番号ではないからである。
よって、出力すべき答えは、条件を満たす人の人数をa人とすると、
- aが偶数の時、a/2個のペアができるから、a/2
- aが奇数の時、a-1個でペアを作り、残りの1人で1回交換するから、(a-1)/2+1 = (a+1)/2
これをif文で場合分けして出力しても良いが、aが偶数の時 a//2 と (a+1)//2 の値は変わらない。( // は切り捨て除算の記号)。よって、aの値に関わらず (a+1)//2 が答えとなる。
計算量はO(N)。
実装例(Python)
T = int(input()) #テストケースの数 # 各テストケースごとに for t in range(T): # 生徒の数 N N = int(input()) #1始まりなので、先頭に適当な値を入れる P = [None] + list(map(int,input().split())) # 条件を満たす人をカウントする変数 a = 0 # 各iについて、条件を満たすならカウント for i in range(1, N+1): if i == P[i]: a += 1 # 答えを出力 print((a+1)//2)
