概要

\(N\) 個のイベントログを時系列順に確認し、「直前に追加したログと同じコードなら無視する」というルールに従って記録リストを作成し、その最終的な内容を出力する問題です。

考察

この問題のポイントは、記録リストの末尾（最後に追加された要素）と現在のログを比較することです。

具体例として、ログが 1 2 2 3 3 3 2 の場合を考えてみましょう。 1. 1 を確認：リストは空なので 1 を追加。リスト：[1] 2. 2 を確認：末尾の 1 と異なるので 2 を追加。リスト：[1, 2] 3. 2 を確認：末尾の 2 と同じなのでスキップ。リスト：[1, 2] 4. 3 を確認：末尾の 2 と異なるので 3 を追加。リスト：[1, 2, 3] 5. 3 を確認：末尾の 3 と同じなのでスキップ。リスト：[1, 2, 3] 6. 3 を確認：末尾の 3 と同じなのでスキップ。リスト：[1, 2, 3] 7. 2 を確認：末尾の 3 と異なるので 2 を追加。リスト：[1, 2, 3, 2]

このように、結局のところ「現在のログ \(A_i\) が直前のログ \(A_{i-1}\) と異なるかどうか」だけを判定すればよいことがわかります。

制約として \(N\) が最大 \(5 \times 10^5\) と大きいため、1つずつ要素を比較していく \(O(N)\) のアルゴリズムで解く必要があります。また、入出力の量も多いため、Pythonでは高速な入出力処理を行うのが安全です。

アルゴリズム

1. 最初のログ \(A_1\) を結果用のリスト result に追加します。
2. \(i = 2\) から \(N\) までの各ログ \(A_i\) について、以下の処理を繰り返します。
   • もし \(A_i \neq A_{i-1}\) ならば、\(A_i\) を result の末尾に追加する。
   • もし \(A_i = A_{i-1}\) ならば、何もしない（読み飛ばす）。
3. 最終的な result の中身を空白区切りで出力します。

計算量

• 時間計算量: \(O(N)\)
  • ログの個数 \(N\) に対して、1回ずつ比較と追加の判定を行うため、線形時間で処理が完了します。
• 空間計算量: \(O(N)\)
  • 入力データおよび結果のリストを保持するために、最大で \(N\) 個分のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonで \(N \geq 10^5\) 程度の入出力を扱う場合、input() を繰り返すよりも sys.stdin.read().split() で一括で読み込む方が高速です。

• 文字列の結合: 大量の要素を出力する際、print を繰り返すのではなく " ".join(result) を使って一気に文字列として出力することで、実行時間を短縮できます。

• 比較対象: コード内では input_data[i] != input_data[i-1] とすることで、リストの末尾を直接参照する代わりに「入力された並びにおける直前」と比較しています。これは記録リストの末尾を常に参照することと同義です。

  ソースコード

import sys

def solve():
    # 入力を一括で読み込み、空白で分割してリスト化する
    input_data = sys.stdin.read().split()
    
    if not input_data:
        return
    
    # N はイベントログの件数
    n = int(input_data[0])
    
    if n == 0:
        return

    # 記録リストの最初の要素として A_1 を追加
    # A_1 は input_data[1] に格納されている
    result = [input_data[1]]
    
    # 2番目以降のログについて、直前のログと比較して異なる場合のみリストに追加する
    # 直前のログと異なる＝記録リストの末尾と異なるため
    for i in range(2, n + 1):
        if input_data[i] != input_data[i-1]:
            result.append(input_data[i])
    
    # リストの要素を空白区切りで結合して出力
    sys.stdout.write(" ".join(result) + "\n")

if __name__ == '__main__':
    solve()

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