概要

シールを順番に配る過程で、高橋君（出席番号 \(2\)）がシールをもらった瞬間に、自分より多くシールを持っている生徒がいるかどうかを判定し、不満を感じる回数を数える問題です。

考察

重要な気づき

高橋君が不満を感じるのは「高橋君にシールが渡された直後」のタイミングだけです。そのタイミングで「高橋君よりも多くシールを持っている生徒が1人でもいるか」を判定する必要があります。

素朴なアプローチの問題点

高橋君がシールをもらうたびに、全生徒 \(N\) 人のシール枚数を調べて最大値を求めると、最悪 \(O(N \times M)\) の時間がかかり、\(N, M\) が最大 \(3 \times 10^5\) のときに TLE になる可能性があります。

解決策：高橋君以外の最大値を効率的に管理する

「高橋君より多くシールを持っている生徒がいるか？」は、高橋君以外の生徒が持つシールの最大枚数 が高橋君のシール枚数より大きいかどうかで判定できます。

ここで重要なのは、シール枚数は増えることはあっても減ることはないという点です。したがって「高橋君以外の生徒のシール枚数の最大値（max_count）」は単調に増加します。これを変数1つで管理すれば、毎回全生徒を走査する必要がなくなります。

具体的には： - 高橋君以外の生徒にシールが渡されたとき → その生徒の枚数が max_count を超えたら更新 - 高橋君にシールが渡されたとき → max_count > takahashi_count なら不満 +1

アルゴリズム

1. 各生徒のシール枚数を管理する配列 count を用意し、すべて \(0\) で初期化する。
2. 高橋君以外の生徒のシール最大枚数 max_count を \(0\) で初期化する。
3. シールを \(1\) 枚ずつ順番に配る：
   • 出席番号 \(P_i\) の生徒の count を \(1\) 増やす。
   • \(P_i \neq 2\) の場合：count[P_i] が max_count より大きければ max_count を更新する。
   • \(P_i = 2\) の場合：高橋君の枚数を更新し、max_count > takahashi_count なら answer を \(1\) 増やす。
4. 最終的な answer を出力する。

具体例

\(N=3, M=7, P = [1, 1, 2, 1, 2, 2, 1]\) の場合：

\(i\)	\(P_i\)	count[1]	count[2]	max_count	判定
1	1	1	0	1	-
2	1	2	0	2	-
3	2	2	1	2	\(2 > 1\) → 不満！
4	1	3	1	3	-
5	2	3	2	3	\(3 > 2\) → 不満！
6	2	3	3	3	\(3 > 3\) は偽 → 不満なし
7	1	4	3	4	-

答え：2 回

計算量

• 時間計算量: \(O(M)\) — シールを1枚配るごとに \(O(1)\) の処理
• 空間計算量: \(O(N)\) — 各生徒のシール枚数を管理する配列

実装のポイント

• max_count は「高橋君以外の生徒のシール最大枚数」を管理する点に注意。高橋君自身のシール枚数が増えても max_count は更新しません。

• シール枚数は単調増加するため、最大値の管理は「現在の最大値と比較して大きければ更新」するだけで十分です（減少を考慮する必要がない）。

• sys.stdin.buffer.read() で入力を一括読み込みすることで、Python でも高速に処理できます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    
    count = [0] * (N + 1)
    takahashi_count = 0
    answer = 0
    max_count = 0
    
    for i in range(M):
        p = int(input_data[2 + i])
        count[p] += 1
        if p != 2:
            if count[p] > max_count:
                max_count = count[p]
        else:
            takahashi_count = count[2]
            if max_count > takahashi_count:
                answer += 1
    
    print(answer)

main()

---

この解説は claude4.6opus-thinking によって生成されました。