概要

高橋君が勝てる部員（実力値が \(L\) 以下の部員）の中で、最も実力値が高い部員を特定する問題です。条件を満たす部員が複数いる場合は、最も番号が小さい部員を選びます。

考察

この問題を解くためには、全 \(N\) 人の部員について、以下の条件を順番に確認していく必要があります。

1. 勝てるかどうか: \(L \geq D_i\) を満たしているか。
2. 実力値が最大か: これまでに見つかった「勝てる部員」の中で、今回の \(D_i\) が最も大きいか。
3. 番号が最小か: 最大の実力値を持つ部員が複数いる場合、その中で最も若い番号か。

制約を確認すると、部員数 \(N\) は最大で \(2 \times 10^5\) です。部員を 1 人ずつ順番にチェックする「線形探索」を行えば、計算回数は \(N\) 回に比例する程度で済むため、制限時間内に十分に正解を出すことができます。

特に「番号が最小」という条件については、部員 1 から順に調べていき、「これまでの最大値を更新したときだけ」 記録を書き換えるようにすれば、自然に条件を満たすことができます。同じ最大値が現れても更新しなければ、最初に現れた（＝番号が最も小さい）部員が保持されるからです。

アルゴリズム

以下の手順でプログラムを実装します。

1. これまでの最大実力値を保持する変数 max_d と、その部員番号を保持する変数 best_idx を用意し、それぞれ -1 で初期化します。
2. 部員 \(i = 1, 2, \ldots, N\) について、以下の処理を繰り返します。
   • もし \(L \geq D_i\)（勝てる相手）かつ \(D_i > \text{max\_d}\)（これまでの最大を更新）であれば：
     • max_d を \(D_i\) で更新する。
     • best_idx を \(i\) で更新する。
3. 最終的な best_idx の値を出力します。勝てる部員が一人もいなかった場合は、初期値の -1 がそのまま出力されます。

計算量

• 時間計算量: \(O(N)\)
  • 全ての部員を 1 回ずつ走査するため、部員数 \(N\) に比例した時間がかかります。
• 空間計算量: \(O(N)\)
  • 全ての部員の実力値をリストに格納して保持するため、\(N\) に比例したメモリを使用します。

実装のポイント

• 1-based indexing: 問題文の部員番号は 1 から始まりますが、プログラミング言語の配列は通常 0 から始まります。出力する際に i + 1 とするなどの調整が必要です。

• 更新条件: current_d > max_d とすることで、実力値が同じ場合に「部員番号が小さい方」を優先できます。もし >= にしてしまうと、後から出てきた（番号が大きい）部員に上書きされてしまうため注意が必要です。

  ソースコード

import sys

def solve():
    # 入力を標準入力から取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 部員数, L: 高橋君の実力値
    N = int(input_data[0])
    L = int(input_data[1])
    
    # D: 各部員の実力値
    D = list(map(int, input_data[2:]))
    
    max_d = -1
    best_idx = -1
    
    # 各部員について順番に確認
    for i in range(N):
        current_d = D[i]
        # 高橋君が勝てる相手（L >= D_i）であるか判定
        if L >= current_d:
            # これまでに見つかった最大の実力値よりも大きい場合、情報を更新
            # 同じ実力値の場合は、部員番号が小さい方を優先するため、更新しない
            if current_d > max_d:
                max_d = current_d
                best_idx = i + 1  # 部員番号は1始まり
                
    # 結果を出力
    print(best_idx)

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-preview によって生成されました。