概要

参加者を「teacher/doctor」と「student/other」の2グループに分け、前者を先に（かつ各グループ内は入力順を保って）並べたうえで、名前の後ろに適切な敬称（sensei / san）を付けて出力します。

考察

重要なのは次の2点です。

1. 並べ替えは“安定”である必要がある
   グループA（teacher/doctor）を前に、グループB（student/other）を後ろにしますが、同じグループ内では入力順を保つ必要があります。
   例えば入力が

   • A1（teacher）, B1（student）, A2（doctor）
     なら出力順は
     
   • A1, A2, B1
     となり、A1とA2の順序は入力通りでなければいけません。

2. 全体ソートをする必要はない（しない方が簡単）
   「Aを先、Bを後」という条件は、各要素を見て A用配列 / B用配列に振り分けて最後に連結すれば満たせます。
   素朴に全体をソートしようとすると、ソートキーの設計や安定性（stable sort）を意識する必要が出て、実装が複雑になりがちです。さらに \(N \le 2\times 10^5\) なので \(O(N\log N)\) のソートでも間に合うことは多いですが、この問題は \(O(N)\) で素直に解けます。

また、出力するのは肩書きそのものではなく、
- teacher/doctor → sensei
- student/other → san
である点に注意します。

アルゴリズム

1. 空の配列 group_a, group_b を用意する。
2. 各参加者について、肩書き r を読んで
   • r が teacher または doctor なら "{name} sensei" を group_a に追加
   • それ以外（student/other）なら "{name} san" を group_b に追加
3. 最後に group_a + group_b を上から順に出力する。
   こうすると、各配列は入力順に追加しているため グループ内の順序が保たれたまま、A→Bの順に並びます。

計算量

• 時間計算量: \(O(N)\)（各参加者を1回ずつ処理するだけ）
• 空間計算量: \(O(N)\)（出力用の文字列を配列に保存するため）

実装のポイント

• 入力が最大 \(2\times 10^5\) 行なので、sys.stdin.readline を使うと高速です。

• 出力も "\n".join(...) でまとめて書き出すと高速になります。

• 条件分岐は r == "teacher" or r == "doctor" のように明確に書くとミスが減ります。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    group_a = []
    group_b = []
    for _ in range(N):
        s, r = input().split()
        if r == "teacher" or r == "doctor":
            group_a.append(f"{s} sensei")
        else:
            group_b.append(f"{s} san")
    sys.stdout.write("\n".join(group_a + group_b))

if __name__ == "__main__":
    main()

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