概要

高橋君が勝てる部員（実力値が \(L\) 以下の部員）の中で、最も実力値が高い部員の番号を求める問題です。

考察

問題を解くための重要な気づき

この問題では、以下の2つの条件を満たす部員を探す必要があります： 1. 勝てる条件: \(D_i \leq L\) を満たす（高橋君の実力値以下） 2. 最適な相手: 条件1を満たす中で、\(D_i\) が最大の部員 3. タイブレーク: \(D_i\) が同じ場合は、部員番号が最も小さい部員

具体例で考える

例えば、\(N = 5\)、\(L = 100\) で、各部員の実力値が \(D = [80, 120, 100, 100, 50]\) の場合： - 部員1: \(D_1 = 80 \leq 100\) → 勝てる ✓ - 部員2: \(D_2 = 120 > 100\) → 勝てない ✗ - 部員3: \(D_3 = 100 \leq 100\) → 勝てる ✓ - 部員4: \(D_4 = 100 \leq 100\) → 勝てる ✓ - 部員5: \(D_5 = 50 \leq 100\) → 勝てる ✓

勝てる部員は {1, 3, 4, 5} で、その中で実力値が最大なのは部員3と部員4（どちらも100）です。番号が小さい方を選ぶので、答えは 部員3 となります。

アプローチの検討

• 素朴なアプローチ: 全部員を順番に見て、条件を満たす最大値を持つ部員を探す
• このアプローチで十分効率的（\(O(N)\)）なので、特別な工夫は不要です

アルゴリズム

1. 変数 best_index（答えとなる部員番号）と best_value（その部員の実力値）を初期化する

   • best_index = -1（勝てる部員がいない場合の答え）
   • best_value = -1（まだ候補がいない状態）

2. 部員を番号1から順番に調べる（配列のインデックスでは0から）

3. 各部員 \(i\) について：

   • \(D_i \leq L\) かつ \(D_i > \text{best\_value}\) なら、その部員を新しい候補として記録
   • ここで「より大きい（>）」という条件を使うことで、同じ実力値の場合は先に見つけた（番号が小さい）部員が優先される

4. 最終的な best_index を出力する

計算量

• 時間計算量: \(O(N)\)
  • すべての部員を1回ずつ確認するため
• 空間計算量: \(O(N)\)
  • 入力を格納する配列のサイズ

実装のポイント

1. 1-indexedへの変換: 問題では部員番号は1から始まるが、配列のインデックスは0から始まる。そのため、答えを出力する際に i + 1 とする必要がある。

2. タイブレークの処理: 同じ実力値の部員が複数いる場合、番号が小さい方を選ぶ。これは「より大きい（>）」という厳密な不等号を使うことで自然に実現できる。最初に見つけた部員が記録され、同じ値の後続の部員では更新されない。

3. 勝てる部員がいない場合: best_index を -1 で初期化しておけば、条件を満たす部員が1人もいなかった場合に自動的に -1 が出力される。

   ソースコード

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

best_index = -1
best_value = -1

for i in range(N):
    if D[i] <= L:
        if D[i] > best_value:
            best_value = D[i]
            best_index = i + 1  # 1-indexed

print(best_index)

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