概要

高橋君が勝てる相手の中で最も実力値が高い部員（複数いる場合は番号が最小）を求める問題。

考察

この問題では、高橋君の実力値 \(L\) に対して \(D_i \leq L\) を満たす部員 \(i\) のうち、\(D_i\) が最大でありかつ番号が最小のものを選ぶ必要があります。

素朴な方法として、全員の実力値を確認して条件を満たす人の中から最大値を探そうとするのは自然です。しかし、もし全員と比較しながら毎回ソートなどを行うと、時間計算量が大きくなりすぎて間に合わない可能性があります（特に \(N\) が最大で \(2 \times 10^5\) あるため）。

しかし、実はこの問題はソートなどをしなくても、単純な線形探索で解くことができます。
ポイントは以下です：

• 各部員について、その実力値 \(D_i\) が高橋君の実力値 \(L\) 以下であるかどうかをチェックする。
• 条件を満たす中で、最大の \(D_i\) を持つ部員を探す。
• 最大値が同じ部員が複数いる場合、番号が最も小さい（つまり先に出現した）部員を選ぶ。

したがって、前から順番に見ていくことで、自然と番号が小さい方を優先しつつ、最大の実力値を持つ部員を見つけられます。

アルゴリズム

1. 部員の実力値リスト \(D\) を前から順番に走査する。
2. 各部員 \(i\) （0-indexed）に対して：
   • もし \(D[i] \leq L\) なら、それが今まで見た中で最大の実力値より大きいかを判定。
   • 大きければ、その実力値とインデックスを記録。
3. 走査終了後、記録されたインデックス（+1して1-indexedに戻す）が答え。
4. 一度も更新されなかった場合は -1 を出力。

このように、1回のループで必要な情報を管理することで効率的に解を求めることができます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力の配列を除く）

実装のポイント

• インデックスは0から始まるので、出力時は i + 1 にする。

• 最初に max_d を -1 などの非常に小さな値にしておくと、初期状態での比較が簡単になる。

• 高橋君が誰にも勝てない場合に対応するため、最後まで更新されなかったら -1 を返す処理が必要。

  ソースコード

N, L = map(int, input().split())
D = list(map(int, input().split()))

max_d = -1
ans = -1

for i in range(N):
    if D[i] <= L:
        if D[i] > max_d:
            max_d = D[i]
            ans = i + 1

print(ans)

この解説は qwen3-coder-480b によって生成されました。