概要

シールを配る過程で「出席番号 2 の高橋君がシールをもらった直後」に限って、高橋君より多くシールを持つ生徒が存在するかを判定し、その回数を数えます。

考察

高橋君が不満を感じるのは 「シールが高橋君(2)に渡された直後」 だけです。したがって各時点で必要なのは次の判定です：

• 高橋君の現在の枚数を \(c_2\)
• 高橋君以外の誰かの最大枚数を \(max\_other\)
• もし \(max\_other > c_2\) なら、そのタイミングで不満を \(1\) 回加算

ここで重要な気づきは、判定に必要なのは「全員の枚数の詳細」ではなく 「高橋君の枚数」と「他の生徒の最大枚数」だけ という点です。

素朴なアプローチが遅い理由

高橋君がシールをもらうたびに、 - 「全生徒を見て、高橋君より多い人がいるか」を毎回チェックすると
1 回のチェックに \(O(N)\) かかります。

最悪の場合、高橋君が \(O(M)\) 回呼ばれるので合計 \(O(NM)\) となり、\(N,M \le 3\times 10^5\) では到底間に合いません。

どう解決するか

各生徒の枚数は配るたびに 1 ずつ増えるだけなので、 - 高橋君の枚数 \(c_2\) - 「高橋君以外の最大枚数」\(max\_other\)

を逐次更新していけば、判定は毎回 \(O(1)\) でできます。

簡単な例

例えば途中で - 高橋君の枚数 \(c_2 = 2\) - 他の誰かが 3 枚持っていて \(max\_other = 3\)

このとき高橋君が次のシールをもらって \(c_2=3\) になっても、判定は - \(max\_other(=3) > c_2(=3)\) は偽
なので不満は増えません。

逆に \(max\_other=4\) のままだったら - \(4 > 3\) なので不満が 1 回増えます。

アルゴリズム

1. 配列 cnt を用意し、cnt[x] を生徒 \(x\) の現在のシール枚数とする。
2. 変数 max_other を「高橋君(2)以外の生徒のシール枚数の最大値」として管理する。
3. 配布順に \(P_1, P_2, \dots, P_M\) を走査する。
   • もし x == 2（高橋君）なら：
     1. cnt[2] += 1
     2. もし max_other > cnt[2] なら ans += 1
   • それ以外（他の生徒）なら：
     1. cnt[x] += 1
     2. もし cnt[x] > max_other なら max_other = cnt[x] に更新
4. ans を出力する。

max_other は「他の生徒が増える」タイミングでしか増えないため、常に正しく保てます。

計算量

• 時間計算量: \(O(M)\)（配布を 1 回ずつ処理し、各回 \(O(1)\)）
• 空間計算量: \(O(N)\)（各生徒の枚数を保持）

実装のポイント

• max_other には 高橋君以外 の最大枚数のみを入れること（高橋君を混ぜると判定が壊れます）。

• 判定は「高橋君がもらった直後」だけ行うこと（それ以外のタイミングで不満は増えない）。

• 入力が大きいので、Python では sys.stdin.buffer.read() のような高速入力が有効です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    P = data[2:]

    cnt = [0] * (N + 1)
    max_other = 0
    ans = 0

    for x in P:
        if x == 2:
            cnt[2] += 1
            if max_other > cnt[2]:
                ans += 1
        else:
            cnt[x] += 1
            if cnt[x] > max_other:
                max_other = cnt[x]

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。