Overview

Given each student’s test results and the point values of each problem, determine each student’s rank. The rank depends on the number of people with higher scores.

Analysis

First, we need to calculate each student’s score. This can be done by looking at each student’s answer string \(S_i\) and summing up the point values \(P_j\) for problems where the character is o. This part can be done in \(O(NM)\).

However, a naive approach of comparing all students’ scores to determine ranks (for example, comparing each student’s score against every other student’s score) would be \(O(N^2)\) in the worst case, which is too slow (TLE) given the constraint \(N \leq 2 \times 10^5\).

Instead, by counting how many people have each score and precomputing ranks from the highest score downward, we can efficiently determine each student’s rank.

Specifically, the process is as follows: 1. Calculate each student’s score. 2. Count the number of occurrences of each score. 3. Sort the scores in descending order and compute the rank corresponding to each score. 4. Output the rank corresponding to each student’s score.

This allows us to solve the problem in approximately \(O(N + M + N \log N)\) overall.

Algorithm

1. Calculate each student’s score: For string \(S_i\), sum up the point values \(P_j\) corresponding to positions where the character is o.
2. Count the occurrences of each score: Use a defaultdict or associative array for aggregation.
3. Create a list of scores in descending order and precompute the rank corresponding to each score.
   • Assign ranks sequentially from the highest score, updating the rank as we go.
4. Output the rank corresponding to each student’s score.

For example, if the scores are [80, 90, 80], then: - Score 90 → Rank 1 (1 person) - Score 80 → Rank 2 (next highest)

Ranks can be assigned in this manner.

Complexity

• Time complexity: \(O(NM + N \log N)\)
  • \(O(NM)\) for computing student scores, \(O(N \log N)\) for sorting scores
• Space complexity: \(O(N + M)\)
  • Score list, counting dictionary, rank dictionary, etc.

Implementation Notes

• sys.stdin.read is used for fast input reading.

• Score frequencies are tracked to correctly compute ranks even when there are many duplicate scores.

• By precomputing the rank corresponding to each score, the final output can be produced efficiently.

  Source Code

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()

---

This editorial was generated by qwen3-coder-480b.