概要

各生徒の正解した問題の配点合計（合計点）を求め、その点数が高い順に「自分より高得点の人数 + 1」で順位を出力します。同点は同順位になります。

考察

まず各生徒の合計点は、文字列 \(S_i\) を左から見て o の位置の配点 \(P_j\) を足せば求まります。

次に順位付けですが、点数で降順ソートして位置を見れば良さそうに見えます。ただし注意点があります：

• 同点の扱い：単純に「ソート後のインデックス + 1」を順位にすると、同点の人でも順位がズレてしまいます（例：100点が2人いると、1位と2位になってしまう）。
• 全員をソートして順位を割り当てる方法でも正しくはできますが、同点処理のために「同点の塊」を管理する必要があります。

そこで、点数ごとの人数を数えて（度数分布）、高得点から順に「自分より高い人数」を累積して順位を決めるのが簡潔で確実です。

例：点数が [80, 100, 80, 60] のとき
- 100点：人数1 → 自分より高い人数0 → 順位1
- 80点：人数2 → 自分より高い人数1 → 順位2
- 60点：人数1 → 自分より高い人数3 → 順位4
となり、同点は同順位になります。

アルゴリズム

1. 入力された配点 \(P_1 \ldots P_M\) を配列で保持。
2. 各生徒について文字列 \(S_i\) を走査し、o の問題の配点を足して合計点 scores[i] を計算。
3. Counter（連想配列）で「点数 → 人数」を数える。
4. 点数の種類（キー）だけを降順にソートする。
5. 高得点から順に、
   • その点数の順位 =（これまでに見た人数＝自分より高い人数）+ 1
   • その後「これまでに見た人数」にその点数の人数を加算
     して rankmap[score] を作る。
6. 最後に各生徒の点数 scores[i] から rankmap を参照して順位を出力。

計算量

• 時間計算量:
  合計点計算が \(O(NM)\)（ただし制約で \(NM \le 5\times 10^6\)）、
  点数種類数を \(K\) としてソートが \(O(K\log K)\)、
  よって全体で \(O(NM + K\log K)\)
• 空間計算量:
  scores が \(O(N)\)、Counter と rankmap が \(O(K)\) なので \(O(N+K)\)

実装のポイント

• 入力が大きいので sys.stdin.buffer.readline を使うと高速です。

• Pythonでは文字列を bytes として受け取り、b == 111（ord('o')）で判定すると少し速くできます。

• 順位は「高得点の人数の累積 + 1」で決まり、同点は同じ順位になるように Counter（点数ごとの人数）を使うのが簡単です。

  ソースコード

import sys
from collections import Counter

def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    P = list(map(int, input().split()))

    scores = []
    for _ in range(N):
        s = input().rstrip()  # bytes
        total = 0
        for j, b in enumerate(s):
            if b == 111:  # ord('o')
                total += P[j]
        scores.append(total)

    cnt = Counter(scores)
    uniq = sorted(cnt.keys(), reverse=True)

    rankmap = {}
    higher = 0
    for sc in uniq:
        rankmap[sc] = higher + 1
        higher += cnt[sc]

    out = "\n".join(str(rankmap[sc]) for sc in scores)
    sys.stdout.write(out)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。