概要

時系列順に並んだイベントログを前から順に見ていき、直前に記録したものと同じイベントコードなら読み飛ばす（連続する重複を除去する）問題です。

考察

重要な気づき

この問題で求められているのは「連続する同一要素の重複除去（run-length encoding 的な圧縮）」です。全体での重複除去ではなく、あくまで 記録リストの末尾と一致するかどうか だけを見る点に注意しましょう。

例えば、入力が 1 1 2 2 1 1 3 の場合：

最終的な出力は 1 2 1 3 となります。1 は離れた位置に再度出現しているため、2回記録される点がポイントです。

素朴なアプローチで問題ないか

各ログについて「直前の要素と比較する」だけなので、1回のループで解けます。\(N\) が最大 \(5 \times 10^5\) ですが、\(O(N)\) で十分間に合います。特別なデータ構造やアルゴリズムは不要です。

アルゴリズム

1. 結果を格納するリスト result と、直前に追加した要素を保持する変数 prev を用意する（prev の初期値は「何も追加していない」を表す None）。
2. \(A_1, A_2, \ldots, A_N\) を順に確認する。
   • 現在のイベントコード \(A_i\) が prev と 異なる 場合、result に追加し、prev を \(A_i\) に更新する。
   • 同じ場合は何もしない（読み飛ばす）。
3. result の中身を空白区切りで出力する。

計算量

• 時間計算量: \(O(N)\) — 各ログを1回ずつ確認するだけ。
• 空間計算量: \(O(N)\) — 最悪の場合（重複が一切ない場合）、記録リストのサイズは \(N\) になる。

実装のポイント

• 高速な入出力: Python では sys.stdin.buffer.read() でバイト列として一括読み込みし、split() で分割するのが高速です。正解コードではイベントコードを バイト列のまま（int に変換せず）比較・結合しています。整数値としての演算は不要なので、文字列（バイト列）のまま扱うことで変換コストを省き、大幅に高速化しています。

• b" ".join(result).decode(): バイト列のリストを b" " で結合してから最後にデコードすることで、出力も効率的に行っています。

• prev 変数の活用: result[-1] でリスト末尾を毎回参照する代わりに、別変数 prev に直前の値を保持することで、コードがシンプルになります（計算量は変わりませんが可読性が向上します）。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    n = int(input_data[0])
    a = input_data[1:n+1]
    
    result = []
    prev = None
    for x in a:
        if x != prev:
            result.append(x)
            prev = x
    
    sys.stdout.write(b" ".join(result).decode() + "\n")

main()

この解説は claude4.6opus-thinking によって生成されました。