概要

\(N\) 人の参加者を肩書きに基づいて「グループ A（敬称：sensei）」と「グループ B（敬称：san）」の 2 つに分類し、グループ A の全員を前に、グループ B の全員を後ろに並べ替えて出力する問題です。各グループ内では、入力された順番を維持する必要があります。

考察

この問題を解くために必要なステップは以下の 3 つです。

1. 敬称の決定: 肩書きが teacher または doctor なら sensei、それ以外（student または other）なら san を名前に付け加えます。
2. グループ分け: 敬称が決まった参加者を、グループ A かグループ B のどちらかに振り分けます。
3. 順序の維持: 問題文に「入力で与えられた順番をそのまま保つ」とあるため、各グループをリスト（配列）で管理し、見つかった順に末尾に追加していくことで、相対的な順序を維持できます。

制約として \(N \leq 2 \times 10^5\) と比較的大きいため、計算量が \(O(N)\) または \(O(N \log N)\) のアルゴリズムで解く必要があります。今回の「リストへの追加」と「リストの結合」という操作は \(O(N)\) で完了するため、十分に間に合います。

アルゴリズム

1. グループ A 用の空リスト group_a と、グループ B 用の空リスト group_b を用意します。
2. 入力された各参加者について、以下の処理を \(N\) 回繰り返します。
   • 肩書きが teacher または doctor の場合：名前 + " sensei" という文字列を作り、group_a に追加します。
   • それ以外の場合：名前 + " san" という文字列を作り、group_b に追加します。
3. group_a の全要素を出力し、その後に group_b の全要素を出力します。

計算量

• 時間計算量: \(O(N)\)
  • データの読み込み、各参加者の判定、リストへの追加、最終的な出力のすべてが \(N\) に対して線形な時間で実行されます。
• 空間計算量: \(O(N)\)
  • すべての参加者の名前と敬称を保存するために、入力サイズに比例したメモリを使用します。

実装のポイント

• 入出力の高速化: Python で \(N=2 \times 10^5\) 規模の入出力を扱う場合、input() を繰り返すよりも sys.stdin.read().split() で一括で読み込む方が高速です。また、print() を繰り返すよりも、結果をリストにまとめて "\n".join(result) で一度に出力する方が効率的です。

• 安定性の確保: 自分でソートアルゴリズムを書かなくても、条件に合うものを順番に別のリストに抽出していくだけで、自然に「元の順序を保ったままのグループ分け」が実現できます。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを取得し、空白（改行含む）で分割してトークンのリストにします。
    # N=2*10^5 という制約下で、Pythonにおいてはこの方法が比較的高速です。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 最初のトークンは参加者の人数 N です。
    n = int(data[0])
    
    # 肩書きによってグループ A (teacher, doctor) とグループ B (student, other) に分けます。
    # 各グループ内では入力順を維持する必要があるため、リストに順番に追加していきます。
    group_a = []
    group_b = []
    
    # 参加者ごとのデータは、名前 Si と肩書き Ri のペアで構成されています。
    # data[1] が S1, data[2] が R1, data[3] が S2, data[4] が R2 ... となります。
    for i in range(1, 2 * n + 1, 2):
        name = data[i]
        title = data[i+1]
        
        # 肩書きに応じた敬称の決定とグループ分け
        if title == 'teacher' or title == 'doctor':
            # グループ A: 敬称は sensei
            group_a.append(name + " sensei")
        else:
            # グループ B: 敬称は san
            group_b.append(name + " san")
    
    # グループ A の全員をグループ B の全員より前に配置して出力します。
    # 各参加者の情報を改行で区切って一括で出力することで高速化を図ります。
    result = group_a + group_b
    if result:
        sys.stdout.write("\n".join(result) + "\n")

if __name__ == "__main__":
    main()

この解説は gemini-3-flash-thinking によって生成されました。