概要

参加者を肩書きに応じて2つのグループ（teacher/doctor のグループと student/other のグループ）に分け、前者を先に出力する問題です。各参加者の名前には肩書きに応じた敬称（sensei または san）を付けます。

考察

この問題で重要なポイントは以下の通りです。

1. 敬称の変換ルール

肩書きをそのまま出力するのではなく、以下のように敬称に変換する必要があります。 - teacher / doctor → sensei - student / other → san

2. 安定ソート（グループ内の順序保持）

参加者をグループ A（sensei 組）とグループ B（san 組）に分けますが、各グループ内では入力順を保つ必要があります。

例えば、入力が以下の場合を考えます：

4
alice teacher
bob student
carol doctor
dave other

• グループ A（teacher/doctor）：alice, carol（入力での順序を保持）
• グループ B（student/other）：bob, dave（入力での順序を保持）

出力は alice sensei, carol sensei, bob san, dave san の順になります。

3. 素朴なアプローチで十分

\(N \leq 2 \times 10^5\) と制約が大きいですが、この問題は1回のループで各参加者をグループ A かグループ B に振り分けるだけなので、特別なアルゴリズムは不要です。ただし、Python では入出力が遅いため、sys.stdin での高速読み込みや '\n'.join() でのまとめて出力が有効です。

アルゴリズム

1. 入力を読み込む。
2. 2つのリスト group_a（sensei 組）と group_b（san 組）を用意する。
3. 各参加者について肩書き \(R_i\) を確認し：
   • teacher または doctor なら group_a に "名前 sensei" を追加
   • student または other なら group_b に "名前 san" を追加
4. group_a の全要素の後に group_b の全要素を連結して出力する。

入力順にループするだけなので、各グループ内の順序は自然に保たれます。

計算量

• 時間計算量: \(O(N)\) — 各参加者を1回ずつ処理するだけ
• 空間計算量: \(O(N)\) — 全参加者の出力文字列を保持

実装のポイント

• 高速な入出力: Python では sys.stdin.buffer.read() で一括読み込みし、出力も '\n'.join() でまとめて1回の print で行うことで、大量データでもTLEを回避できます。

• グループ分けにソートは不要: 入力順にループしながら2つのリストに振り分けるだけで、安定な並び替えが実現できます。わざわざソート関数を使う必要はありません。

• 肩書きと敬称の混同に注意: 出力するのは肩書き（teacher など）ではなく敬称（sensei / san）です。問題文をよく読まないと WA になりがちなポイントです。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().decode()
    lines = input_data.split('\n')
    N = int(lines[0])
    group_a = []
    group_b = []
    for i in range(1, N + 1):
        parts = lines[i].split()
        s, r = parts[0], parts[1]
        if r == 'teacher' or r == 'doctor':
            group_a.append(s + ' sensei')
        else:
            group_b.append(s + ' san')
    print('\n'.join(group_a + group_b))

main()

---

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