概要

各生徒の合計点を計算し、「自分より高い点数の生徒の人数 \(+ 1\)」として順位を求める問題です。

考察

問題の整理

各生徒について、正解した問題の配点を合計し、その合計点に基づいて順位を決定します。順位は「自分より真に高い合計点を持つ生徒の人数 \(+ 1\)」なので、同点の生徒は同じ順位になります。

例えば、合計点が \([100, 80, 80, 60]\) の場合、順位は \([1, 2, 2, 4]\) となります（80点の2人はどちらも2位、60点の人は4位）。

素朴なアプローチの問題点

各生徒について他の全生徒と比較して「自分より高い点数の人数」を数えると、\(O(N^2)\) かかります。\(N\) が最大 \(2 \times 10^5\) なので、これでも間に合う可能性はありますが、もっと効率的にできます。

効率的な方法

合計点ごとに人数を集計（Counter）し、スコアを降順にソートして累積人数を管理すれば、各スコアに対する順位を \(O(N \log N)\) で一括計算できます。

具体的には、スコアを降順に見ていき： - 現在のスコアの順位 = それまでに数えた人数（より高いスコアの人数）\(+ 1\) - その後、現在のスコアの人数を累積に加算

こうすることで、各スコアに対する順位を辞書（ハッシュマップ）に格納し、最後に各生徒のスコアから順位を \(O(1)\) で引けます。

アルゴリズム

1. 入力を読み込む: \(N\), \(M\), 配点 \(P\), 各生徒の解答文字列 \(S_i\) を取得する。
2. 合計点の計算: 各生徒 \(i\) について、\(S_i\) の \(j\) 文字目が o なら \(P_j\) を加算し、合計点 \(\text{scores}[i]\) を求める。（\(O(N \times M)\)）
3. スコアごとの人数を集計: Counter を使って各スコアの出現回数を数える。（\(O(N)\)）
4. 順位の計算: ユニークなスコアを降順にソートし、累積人数を使って各スコアの順位を求める。
   • 累積人数 \(= 0\) から開始
   • スコア \(sc\) に対して：\(\text{rank}[sc] = \text{累積人数} + 1\)
   • 累積人数 \(+= \text{cnt}[sc]\)
5. 出力: 各生徒のスコアに対応する順位を出力する。

計算量

• 時間計算量: \(O(N \times M + N \log N)\)
  • 合計点の計算に \(O(N \times M)\)（制約より \(N \times M \leq 5 \times 10^6\)）
  • ユニークスコアのソートに \(O(N \log N)\)（最悪 \(N\) 個のユニークスコア）
• 空間計算量: \(O(N + M)\)
  • スコア配列に \(O(N)\)、配点配列に \(O(M)\)、順位辞書に \(O(N)\)

実装のポイント

• 高速な入力: sys.stdin.buffer.read() で一括読み込みし、split() でトークン分割することで、Python でも入力がボトルネックにならないようにしています。

• Counter + 降順ソートによる順位計算: 全生徒をスコアでソートする代わりに、ユニークスコアだけをソートすれば十分です。同じスコアの生徒が多い場合に特に効率的です。

• 出力の一括書き出し: '\n'.join(out) でまとめて出力することで、print を \(N\) 回呼ぶよりも高速になります。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    N = int(tokens[idx]); idx += 1
    M = int(tokens[idx]); idx += 1
    P = [int(tokens[idx + j]) for j in range(M)]
    idx += M
    
    scores = []
    for i in range(N):
        s = tokens[idx]; idx += 1
        total = 0
        for j in range(M):
            if s[j] == 'o':
                total += P[j]
        scores.append(total)
    
    # Count how many students have each score
    from collections import Counter
    cnt = Counter(scores)
    
    # For each unique score, rank = number of students with strictly higher score + 1
    # Sort unique scores in descending order and compute cumulative counts
    sorted_scores = sorted(cnt.keys(), reverse=True)
    rank_map = {}
    cumulative = 0
    for sc in sorted_scores:
        rank_map[sc] = cumulative + 1
        cumulative += cnt[sc]
    
    out = []
    for i in range(N):
        out.append(str(rank_map[scores[i]]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

---

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