概要

\(N\) 冊の本が並んだ本棚から、管理番号が \(K\) である最初の本の位置（左から何番目か）を特定する問題です。

考察

この問題で重要なのは、「左から順番に 1 冊ずつ確認し、最初に見つかった時点で終了する」という点です。

• 素朴なアプローチ: 左端の本（1番目）から順に管理番号を確認していきます。もし管理番号が \(K\) と一致すれば、その番号を出力して探索を終えます。最後まで見つからなければ \(-1\) を出力します。
• 制約の確認: 本の数 \(N\) は最大で \(2 \times 10^5\) です。1 つずつ順番に確認する「線形探索」を行っても、計算回数は最大で \(2 \times 10^5\) 回程度です。一般的な競技プログラミングの制限時間（2秒程度）では、1秒間に約 \(10^8\) 回の計算が可能とされているため、この方法で十分に間に合います。
• 管理番号の大きさ: 管理番号 \(A_i\) は最大 \(10^9\) と大きな値ですが、Python などの現代的なプログラミング言語ではこの程度の大きさの整数比較は高速に行えるため、特に工夫は必要ありません。

アルゴリズム

線形探索（リニアサーチ）という手法を用います。

1. 本の情報を左から順に見ていきます。
2. \(i\) 番目の本の管理番号 \(A_i\) が \(K\) と等しいか判定します。
3. もし \(A_i = K\) であれば、その位置 \(i\) を出力してプログラムを終了します。
4. すべての本を確認しても \(K\) が見つからなかった場合は、\(-1\) を出力します。

計算量

• 時間計算量: \(O(N)\) 本棚の端から端まで最大で \(N\) 回の比較を行うため、\(N\) に比例した時間がかかります。
• 空間計算量: \(O(N)\) 入力された \(N\) 冊の本の管理番号をリストとして保持する場合、メモリの使用量は \(N\) に比例します。

実装のポイント

• 1-indexed への変換: 多くのプログラミング言語（Python の range やリストなど）は 0 始まりで数を数えます。問題文では「左から 1 始まりで何番目か」を問われているため、プログラム上の添字に \(+1\) する必要があります。

• 早期終了（break）: 「最も小さい位置」を求める必要があるため、最初に見つかった時点で break を使ってループを抜けるのが効率的です。

• 高速な入出力: \(N\) が \(2 \times 10^5\) と比較的大きいため、Python の場合は sys.stdin.read().split() などを使って一括で入力を読み込むと実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 本の冊数, K: 探している管理番号
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 本の管理番号のリスト
    # 管理番号は最大10^9なので、整数として比較を行う
    found_index = -1
    for i in range(n):
        if int(input_data[i + 2]) == k:
            found_index = i + 1
            break
            
    # 結果を出力
    print(found_index)

if __name__ == "__main__":
    solve()

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