概要

\(N\) 人の生徒のテスト点数が与えられ、\(Q\) 個の質問それぞれについて、指定された2人の生徒の点数を比較し、前者が厳密に高いかを判定する問題です。

考察

この問題は、配列の要素を参照して比較するだけのシンプルな問題です。

重要な気づき: - 各質問は独立しており、単純に2つの点数を比較するだけで解ける - 「厳密に高い」とは \(S_{a_i} > S_{b_i}\) のことで、等しい場合（\(S_{a_i} = S_{b_i}\)）は No となる - 同じ生徒同士の比較（\(a_i = b_i\)）も起こりうるが、この場合は当然 \(S_{a_i} = S_{b_i}\) なので No となる

素朴なアプローチで問題ない理由: - 各質問に対して配列の2つの要素にアクセスするだけなので、1回の質問は \(O(1)\) で処理できる - \(Q \leq 10^5\) 個の質問があっても、合計 \(O(Q)\) で十分高速

アルゴリズム

1. 生徒の人数 \(N\) と質問の個数 \(Q\) を読み込む
2. \(N\) 人分のテストの点数を配列 \(H\) に格納する
3. 各質問 \((a_i, b_i)\) について:
   • \(H[a_i - 1]\) と \(H[b_i - 1]\) を比較（配列は0-indexedなので1を引く）
   • \(H[a_i - 1] > H[b_i - 1]\) なら Yes、そうでなければ No を出力

具体例（入力例）:

3 4
80 90 70
2 1
1 3
3 2
1 1

• 生徒1: 80点、生徒2: 90点、生徒3: 70点
• 質問1: 生徒2(90点) > 生徒1(80点)? → Yes
• 質問2: 生徒1(80点) > 生徒3(70点)? → Yes
• 質問3: 生徒3(70点) > 生徒2(90点)? → No
• 質問4: 生徒1(80点) > 生徒1(80点)? → No（同じ生徒なので等しい）

計算量

• 時間計算量: \(O(N + Q)\)
  • 点数の読み込みに \(O(N)\)
  • \(Q\) 個の質問それぞれを \(O(1)\) で処理するので \(O(Q)\)
• 空間計算量: \(O(N + Q)\)
  • 点数を格納する配列に \(O(N)\)
  • 結果を格納するリストに \(O(Q)\)

実装のポイント

• 1-indexed と 0-indexed の変換: 問題では出席番号が1から始まる（1-indexed）が、Pythonの配列は0から始まる（0-indexed）ため、H[a - 1] のように1を引いてアクセスする

• 出力の高速化: 質問ごとに print() を呼ぶと遅くなる場合があるため、結果をリストに溜めて最後に '\n'.join(results) で一括出力している

• 入力の高速化: sys.stdin.readline を使うことで、大量の入力を高速に読み込める

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    H = list(map(int, input().split()))
    
    results = []
    for _ in range(Q):
        a, b = map(int, input().split())
        if H[a - 1] > H[b - 1]:
            results.append("Yes")
        else:
            results.append("No")
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

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