概要

この問題は、\(N\) 人の生徒のテスト結果から各生徒の合計点を計算し、その合計点に基づいて順位を求める問題です。同じ点数の生徒は同じ順位になります。

考察

各生徒の合計点は、正解した問題の配点を足し合わせることで計算できます。素朴なアプローチでは、各生徒の合計点を計算した後、各生徒について他の全生徒と点数を比較して順位を求めることが考えられます。しかし、この方法では \(O(N^2)\) の時間がかかり、\(N\) が最大 \(2 \times 10^5\) まで大きくなるため、制限時間内に実行することができません。

そこで、効率的に順位を求めるためには、全生徒の合計点を降順にソートし、各生徒の点数がソートされた配列のどこに位置するかを二分探索で求める方法が有効です。これにより、順位の計算を \(O(N \log N)\) で行うことができます。

アルゴリズム

1. 各生徒について、解答結果の文字列を読み取り、正解した問題の配点を合計して合計点を計算します。
2. 全生徒の合計点を降順にソートします。
3. 各生徒の合計点について、ソートされた配列の中でその点数より真に大きい点数の人数を二分探索で求め、順位（人数 + 1）を計算します。
   • 二分探索では、ソートされた配列の中で対象の点数より大きい値が最初に現れなくなる位置（左端）を探します。
   • この位置のインデックスが、対象の点数より真に大きい点数の人数に相当します。

計算量

• 時間計算量: \(O(NM + N \log N)\)
  • 合計点の計算に \(O(NM)\)、ソートに \(O(N \log N)\)、各生徒の順位の二分探索に \(O(N \log N)\) かかります。
  • 制約 \(N \times M \leq 5 \times 10^6\) より、\(NM\) は最大 \(5 \times 10^6\) なので、十分高速です。
• 空間計算量: \(O(N)\)
  • 合計点のリストとソートされたリストを保持するためです。

実装のポイント

• 合計点の計算時には、各生徒の解答文字列と配点リストをインデックスで対応させます。

• ソートは降順で行い、二分探索では降順の配列に対して「対象の点数より大きい値」の境界を探します。

• 二分探索の終了時、left が対象の点数より真に大きい点数の人数を表すため、順位は left + 1 となります。

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    n, m = map(int, data[0].split())
    P = list(map(int, data[1].split()))
    
    scores = []
    total_scores = []
    
    for i in range(2, 2 + n):
        s = data[i].strip()
        scores.append(s)
        total = 0
        for j, char in enumerate(s):
            if char == 'o':
                total += P[j]
        total_scores.append(total)
    
    sorted_scores = sorted(total_scores, reverse=True)
    
    results = []
    for score in total_scores:
        left, right = 0, len(sorted_scores) - 1
        while left <= right:
            mid = (left + right) // 2
            if sorted_scores[mid] > score:
                left = mid + 1
            else:
                right = mid - 1
        rank = left + 1
        results.append(rank)
    
    for rank in results:
        print(rank)

if __name__ == "__main__":
    main()

---

この解説は deepseekv3 によって生成されました。