コンテンツにスキップ

repovive standard round 9 A - Pair Distances

サイト
repovive.com
コンテスト
repovive standard round 9
問題
A - Pair Distances

位置 1,2,…,n1, 2, \dots, n に nn 人が並んでいます(nn は偶数)。全員を 2 人ずつのペアに分けます。人 ii は「自分とペアの相手の位置の差は did_i だ」と言っています。全員の言っていることが正しくなるようにペアに分けられるか判定する問題です(2≤n≤2×1052 \le n \le 2 \times 10^5、1≤di<n1 \le d_i < n、テストケースは最大 10410^4 個で nn の総和は 2×1052 \times 10^5 以下)。

左から順に、まだ相手が決まっていない人を見ていきます。

まだ相手が決まっていない人のうち一番左の人を ii とします。ii の相手は位置 i−dii - d_i か i+dii + d_i にいるはずです。しかし ii より左の人はすでに全員相手が決まっているので、i−dii - d_i は候補になりません。したがって、相手は j=i+dij = i + d_i に決まります。

このペアが作れるのは、次の 3 つをすべて満たすときです。

  • j≤nj \le n である。
  • jj の相手がまだ決まっていない。
  • dj=did_j = d_i である(jj から見ても相手との距離は did_i なので)。

満たしていれば ii と jj をペアにして先に進み、満たしていなければ答えは No です。最後までペアを作れれば答えは Yes です。相手が一通りにしか決まらないので、この方法で作れなければ、どう分けても作れません。

計算量は O(n)O(n) です。

Python
for _ in range(int(input())):
N = int(input())
D = list(map(int, input().split()))
pair = [None] * N
for i in range(N):
if pair[i] is not None:
continue
j = i + D[i]
if j not in range(N) or pair[j] is not None or D[j] != D[i]:
print("No")
break
pair[i] = j
pair[j] = i
else:
print("Yes")

位置は 0 始まりにしています。pair[i] は人 ii の相手の位置で、まだ決まっていなければ None です。j not in range(N) で、相手の位置が列の外に出ていないかを調べています。

for 文に付けた else は、break せずに最後まで回ったときだけ実行されます。途中で No を出力して break したときは Yes を出力しません。