概要

与えられた列を先頭から順に見て、直前に記録した値と同じなら捨てる、違うなら記録する、というシミュレーション問題です。
つまり「連続する重複だけを取り除いた列」を作ればよいです。

考察

重要な観察は、「判定に必要なのは記録リストの末尾だけ」という点です。
新しいイベントコード \(x\) を追加するかどうかは、

• 記録リストが空
• または記録リスト末尾 \(\neq x\)

のどちらかで決まります。
それ以外（末尾と同じ）なら追加しません。

例えば
\(A = [5,5,2,2,2,7,5,5]\) のとき、

• 5 を追加 → [5]
• 次の 5 は末尾と同じなのでスキップ → [5]
• 2 を追加 → [5,2]
• 次の 2,2 はスキップ → [5,2]
• 7 を追加 → [5,2,7]
• 5 を追加（末尾7と異なる）→ [5,2,7,5]
• 次の 5 はスキップ → [5,2,7,5]

最終結果は [5,2,7,5] です。

素朴に「毎回これまでの全要素と比較する」ような実装をすると、最悪で \(O(N^2)\) になり、\(N \le 5\times10^5\) では間に合いません。
この問題は末尾との比較だけで十分なので、1回の判定を \(O(1)\) で行い、全体を \(O(N)\) で処理できます。

アルゴリズム

1. 空の配列 res を用意する（記録リスト）。
2. 入力列を先頭から順に x として見る。
3. res が空、または res[-1] != x なら x を res に追加。
4. そうでなければ何もしない（スキップ）。
5. 最後に res を空白区切りで出力する。

提示コードはこの手順をそのまま実装しています。

計算量

• 時間計算量: \(O(N)\)
  各要素を1回ずつ見て、末尾比較と必要なら追加をするだけ。
• 空間計算量: \(O(N)\)
  出力用の res に最大で \(N\) 個入る可能性があるため。

実装のポイント

• Pythonでは if not res or res[-1] != x: と書くと、空配列判定と末尾比較を安全にまとめられます（空のとき res[-1] を触らない）。

• 入力サイズが大きいので sys.stdin.readline を使うのが安心です。

• 出力は print(*res) で空白区切りにできます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    n = int(input().strip())
    a = list(map(int, input().split()))

    res = []
    for x in a:
        if not res or res[-1] != x:
            res.append(x)

    print(*res)

if __name__ == "__main__":
    main()

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