概要

参加者を肩書きに基づいて2つのグループに分け、グループA（teacherまたはdoctor）をグループB（studentまたはother）の前に配置し、それぞれの参加者に適切な敬称（senseiまたはsan）を付けて出力する問題です。

考察

この問題では、参加者を肩書きによって2つのグループに分類し、グループAをグループBの前に配置する必要があります。重要な点は、各グループ内では元の入力順序を保持することです。つまり、グループ内での相対的な順序は変更してはいけません。

素朴なアプローチとして、全ての参加者を一度に読み込み、条件に応じてグループ分けしながら別々のリストに保存します。その後、グループAのリストを先に出力し、続けてグループBのリストを出力すれば、要件を満たすことができます。

アルゴリズム

1. 入力から参加者数を読み取る
2. グループA（teacherまたはdoctor）とグループB（studentまたはother）用の空リストを用意する
3. 各参加者データを順に読み込みながら：
   • 肩書きが teacher または doctor の場合 → グループAに (名前, "sensei") を追加
   • それ以外の場合 → グループBに (名前, "san") を追加
4. グループAの全要素を順に出力
5. グループBの全要素を順に出力

この方法では、入力順序を保持しながら効率的にグループ分けと出力が行えます。

計算量

• 時間計算量: \(O(N)\)
  • 各参加者を1回ずつ処理し、各処理は定数時間で完了します
  • 出力も合計\(N\)回の操作で完了します
• 空間計算量: \(O(N)\)
  • グループAとグループBを合わせて\(N\)要素分のメモリを使用します

実装のポイント

• グループ分けの条件判定は、肩書きが teacher または doctor かどうかで行います

• 各グループでは入力順序を保持する必要があるため、リストへの追加順序が重要です

• 出力時には、名前と敬称を半角スペースで区切って表示します

• 大きな入力（最大20万人）に対応できるように、効率的なアルゴリズムを選択しています

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    n = int(data[0])
    group_a = []
    group_b = []
    
    for i in range(1, n + 1):
        parts = data[i].split()
        s = parts[0]
        r = parts[1]
        
        if r == "teacher" or r == "doctor":
            group_a.append((s, "sensei"))
        else:
            group_b.append((s, "san"))
    
    for person in group_a:
        print(f"{person[0]} {person[1]}")
    
    for person in group_b:
        print(f"{person[0]} {person[1]}")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。