概要

この問題は、数列を左から順に見ていき、直前に記録した値と同じなら無視し、違うなら追加する だけです。
つまり、連続する同じ値を 1 個にまとめる 問題と考えられます。

考察

記録リストに追加するかどうかを決める条件は、

• 記録リストが空なら追加
• 記録リストの末尾と現在の値が異なれば追加
• 同じなら追加しない

の 3 つです。

ここで大事なのは、比較すべき相手は 記録リスト全体ではなく末尾だけ ということです。
たとえば

\(A = [1, 1, 2, 2, 2, 3, 1, 1]\)

のとき、処理は次のようになります。

• \(1\) を追加 → \([1]\)
• 次の \(1\) は末尾と同じなので無視 → \([1]\)
• \(2\) は末尾と異なるので追加 → \([1, 2]\)
• 次の \(2, 2\) は無視 → \([1, 2]\)
• \(3\) を追加 → \([1, 2, 3]\)
• \(1\) は末尾 \(3\) と異なるので追加 → \([1, 2, 3, 1]\)
• 次の \(1\) は無視

最終的な答えは

\([1, 2, 3, 1]\)

になります。

重要な気づき

この問題で消したいのは 連続している重複 だけです。
たとえば \([1, 2, 1]\) は、最後の \(1\) を消してはいけません。
「同じ値が過去に出たことがあるか」を調べる問題ではない点に注意が必要です。

素朴な考え方での問題点

たとえば毎回

• 記録リスト全体を見て重複判定する
• 連続部分をあとからまとめて削除する

のような方法を取ると、不要に時間がかかる可能性があります。
\(N \leq 5 \times 10^5\) と大きいので、各要素を 1 回ずつ見る \(O(N)\) の方法で処理したいです。

そこで、最後に記録した値だけを覚えておく ことで、各要素を定数時間で処理できます。

アルゴリズム

以下の手順で処理します。

1. 空の配列 res を用意する
   ここに最終的な記録リストを作る。

2. last に「最後に追加した値」を持たせる

3. 数列を左から順に見ていく
   各値 x について:

   • res が空なら x を追加
   • そうでなく、x != last なら追加
   • x == last なら無視

4. res を先頭から順に出力する

この方法なら、「今の値が直前に採用した値と同じかどうか」だけを見ればよいので、非常にシンプルです。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• N が大きいので、コードでは sys.stdin.buffer.read() を使って高速に入力しています。

• 末尾要素との比較は res[-1] でもできますが、このコードでは last を別変数で持つことで分かりやすくしています。

• last は「追加したときだけ」更新します。
  こうすることで、常に「現在の記録リストの末尾」と一致した値を保持できます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:1 + n]

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

    sys.stdout.write('\n'.join(map(str, res)))

if __name__ == "__main__":
    main()

---

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