Day 003-Q1 | ソート応用

問題

N人の生徒が数学と英語のテストを受け、それぞれのスコアが与えられる。以下のルールで順位付けして、上位K人の生徒番号（1-indexed）を昇順で出力せよ。

2科目の合計点が高い順
合計が同じなら数学のスコアが高い順
それでも同じなら生徒番号が小さい順

入力形式

N K
A_1 B_1
A_2 B_2
...
A_N B_N

制約

$1 \le K \le N \le 1000$

$0 \le A_i, B_i \le 100$

入出力例

入力例 1

出力例 1

1 2 4

全員合計150。数学順: 2(90)→1(80)=4(80)→3(70)→5(60)。1と4は番号順。上位3人{2,1,4}を昇順出力。

ヒント (段階的開示)

ヒント1: 方向性

Pythonのsortにはキーを複数指定できる。sorted() にキー関数を渡そう。

ヒント2: アプローチ

タプルキー (-合計, -数学, 番号) でソート。マイナスで降順を実現。

ヒント3: 誘導

students.append((i+1, a, b))
students.sort(key=lambda x: (-(x[1]+x[2]), -x[1], x[0]))
top_k = sorted(students[i][0] for i in range(K))
print(*top_k)

模範解答 (Python)

N, K = map(int, input().split())

students = []
for i in range(N):
    a, b = map(int, input().split())
    students.append((i + 1, a, b))

students.sort(key=lambda x: (-(x[1] + x[2]), -x[1], x[0]))

top_k = sorted(students[j][0] for j in range(K))

print(*top_k)

Step-by-Step 解説

1データ構造の設計
番号(1-indexed)・数学・英語をタプルで保持。ソート後も元の番号を追えるようにする。

2多条件ソートのキー設計
Pythonのsorted()はタプルを辞書順で比較。-(合計)で降順、x[0]で番号昇順。

3上位K人の抽出と昇順出力
sorted(students[j][0] for j in range(K)) で番号を昇順に並べ直す。

よくあるミス

ミス	原因	正しい書き方
`reverse=True` で降順	第2・第3条件が混在すると使えない	マイナス記号で降順
出力ソート忘れ	「番号昇順」を見落とし	`sorted()` で再ソート
番号を0-indexed	`i` をそのまま	`i+1` を格納

次のステップ

発展: 3科目で「GPA降順→最高点降順→最低点昇順→番号昇順」

自己評価

完全理解おおむね理解要復習

Day 003-Q1 — ソート応用

問題