repovive starter round 10 C - Museum Records
人が博物館に 1 回ずつ入って出ました。 回の入退場の時刻はすべて異なります。各人 について、
- : が入る前に出ていた人数
- : が出たあとに入ってきた人数
が記録されています。すべての記録が正しくなる入退場の順番があるか判定する問題です(、)。
入る順番と出るタイミング
Section titled “入る順番と出るタイミング”は、入るのが遅い人ほど大きいか等しいです。よって、入る順番は の昇順です。 が等しい人どうしの間では誰も出ていないので、その人たちの入る順番を入れ替えても、ほかの人の は変わりません。
人目が入ってから 人目が入るまでの間を「すき間 」と呼びます(すき間 は最後の人が入ったあと)。 人があとから入ってくるので、人 はすき間 で出ます。同じすき間で出る人どうしの順番は、記録に影響しません。
こうして入退場の順番は(記録に影響しない入れ替えを除いて)決まるので、次の 2 つを満たすか調べれば十分です。人 が 番目に入るとします。
- 入ってから出る:。
- が正しい: は、 である人 の人数に等しい。
が等しい人どうしの順番は 2. に影響しないので、1. を満たしやすい順にします。それは の大きい人(早く出る人)を先にする順です。
の昇順、同じなら の降順に並べます。0-indexed で 番目の人は 番目に入るので、1. は です。
また、2. の人数は、すき間ごとに出る人数を数えて累積和をとれば求まります。 を「すき間 以下で出る人数」とすると、2. は です。
全員がこの 2 つを満たせば Yes、そうでなければ No です。計算量はソートの です。
Python
n = int(input())ab = [tuple(map(int, input().split())) for i in range(n)]ab.sort(key=lambda x: (x[0], -x[1]))c = [0] * (n + 1)for a, b in ab: c[n - b] += 1for i in range(n): c[i + 1] += c[i]for i, (a, b) in enumerate(ab): if i + 1 > n - b or a != c[i]: print("No") exit(0)print("Yes")