概要

各生徒のテスト結果と問題の配点から、各生徒の順位を求めよ。順位は得点が高い人数に依存する。

考察

まず、各生徒の得点を計算する必要がある。これは、各生徒の解答文字列 \(S_i\) を見て、o になっている問題の配点 \(P_j\) を足していけばよい。この部分は \(O(NM)\) で可能。

しかし、単純に全員の得点を比較して順位を求める方法（たとえば、各生徒に対して他の全生徒と得点を比較する）では、最悪の場合 \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) では間に合わない（TLE）。

そこで、得点ごとに何人がいるかをカウントしておき、得点の高い方から順位を前計算しておくことで、各生徒の順位を高速に求めることができる。

具体的には、以下のように処理を行う： 1. 各生徒の得点を計算する。 2. 各得点ごとの出現回数をカウントする。 3. 得点の高い順に並べて、各得点に対応する順位を計算する。 4. 各生徒の得点に対応する順位を出力する。

これにより、全体で \(O(N + M + N \log N)\) 程度で解くことができる。

アルゴリズム

1. 各生徒の得点を計算する：文字列 \(S_i\) に対して、o の位置に対応する配点 \(P_j\) を合計する。
2. 各得点の出現回数をカウントする：defaultdict や連想配列を使って集計。
3. 得点の降順リストを作り、各得点に対応する順位を前計算する。
   • 高い得点から順に、順位を更新しながら割り当てていく。
4. 各生徒の得点に対応する順位を出力する。

例えば、得点が [80, 90, 80] なら、 - 得点 90 → 順位 1（1人） - 得点 80 → 順位 2（次に多いので）

というように順位を設定できる。

計算量

• 時間計算量: \(O(NM + N \log N)\)
  • 生徒の得点計算に \(O(NM)\)、得点のソートに \(O(N \log N)\)
• 空間計算量: \(O(N + M)\)
  • 得点リスト、カウント用辞書、順位辞書など

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している。

• 得点の重複が多い場合でも、順位を正しく計算するために得点の頻度を管理している。

• 各得点に対応する順位を前計算することで、最終的な出力を高速に行っている。

  ソースコード

import sys
from collections import defaultdict

input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    P = list(map(int, data[2:2+M]))
    S_list = data[2+M:2+M+N]
    
    # 各生徒の得点を計算
    scores = []
    for S in S_list:
        score = 0
        for j in range(M):
            if S[j] == 'o':
                score += P[j]
        scores.append(score)
    
    # 得点の頻度をカウント
    score_count = defaultdict(int)
    for score in scores:
        score_count[score] += 1
    
    # 各得点に対する順位を前計算
    unique_scores = sorted(score_count.keys(), reverse=True)
    rank_dict = {}
    current_rank = 1
    for score in unique_scores:
        rank_dict[score] = current_rank
        current_rank += score_count[score]
    
    # 各生徒の順位を出力
    for score in scores:
        print(rank_dict[score])

if __name__ == "__main__":
    main()

---

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