repovive standard round 9 A - Pair Distances
- サイト
- repovive.com
- コンテスト
- repovive standard round 9
- 問題
- A - Pair Distances
位置 に 人が並んでいます( は偶数)。全員を 2 人ずつのペアに分けます。人 は「自分とペアの相手の位置の差は だ」と言っています。全員の言っていることが正しくなるようにペアに分けられるか判定する問題です(、、テストケースは最大 個で の総和は 以下)。
左から順に、まだ相手が決まっていない人を見ていきます。
まだ相手が決まっていない人のうち一番左の人を とします。 の相手は位置 か にいるはずです。しかし より左の人はすでに全員相手が決まっているので、 は候補になりません。したがって、相手は に決まります。
このペアが作れるのは、次の 3 つをすべて満たすときです。
- である。
- の相手がまだ決まっていない。
- である( から見ても相手との距離は なので)。
満たしていれば と をペアにして先に進み、満たしていなければ答えは No です。最後までペアを作れれば答えは Yes です。相手が一通りにしか決まらないので、この方法で作れなければ、どう分けても作れません。
計算量は です。
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] は人 の相手の位置で、まだ決まっていなければ None です。j not in range(N) で、相手の位置が列の外に出ていないかを調べています。
for 文に付けた else は、break せずに最後まで回ったときだけ実行されます。途中で No を出力して break したときは Yes を出力しません。