概要

同じ品種が連続している「かたまり（連続区間）」の長さが \(K\) 以上ならその区間の花はすべて残し、それ以外の花はすべて取り除いた後の列を出力する問題です。

考察

重要な観察は次のとおりです。

• 「見栄えの良い区間」は 同じ値が連続する区間 に限られます（条件 \(S_l=S_{l+1}=\cdots=S_r\)）。
• ある花 \(i\) が残る条件は、「花 \(i\) が属する同値連続ブロックの長さが \(K\) 以上」であることと同値です。
  なぜなら、花 \(i\) を含む区間 \((l,r)\) が全て同じ値で長さ \(\ge K\) なら、\(i\) が属する最大の連続ブロック自体の長さも \(\ge K\) ですし、逆にブロック長が \(\ge K\) ならそのブロック内に長さ \(K\) の区間を取れて \(i\) を含められるからです。

したがって、問題は - 列を左から見て「同じ値が何個連続しているか」を数え、 - その連続数が \(K\) 以上のブロックだけをそのまま出力する だけになります。

素朴に「各 \(i\) について条件を満たす \((l,r)\) が存在するか」を探すと、区間探索が絡んで \(O(NK)\) や \(O(N^2)\) になり \(N \le 10^6\) では間に合いません。
連続ブロック単位で処理すれば、1 回の走査で解けます。

具体例：\(S=[1,1,2,2,2,3],\ K=2\)
連続ブロックは \((1が2個),(2が3個),(3が1個)\) なので、残るのは \(1,1,2,2,2\) です。

アルゴリズム

1. 左から順に値を読み、現在の値 prev とその連続数 cnt を管理する。
2. 次の値 x が prev と同じなら cnt += 1。
3. 異なる値になったら、直前のブロックの長さ cnt を確認し、cnt \ge K なら prev を cnt 回出力する。
   その後 prev = x, cnt = 1 に更新して次のブロックへ進む。
4. 最後のブロックも同様に判定して出力する。

このとき、出力は最大で \(N\) 個になり得るので、1 個ずつ print すると遅くなる場合があります。コードでは出力用バッファを用意し、まとめて書き出すことで高速化しています。

計算量

• 時間計算量: \(O(N)\)（1 回走査して各要素を定数回処理）
• 空間計算量: \(O(1)\)（入力全体を保持せず、ブロック情報と出力バッファのみ。出力バッファは定数上限でフラッシュ）

実装のポイント

• 高速入力：\(N=10^6\) なので、sys.stdin.buffer.read() から整数をパースする実装にして I/O を高速化しています。

• 高速出力：残す花を大量に出力する可能性があるため、文字列を一定個数ためて " ".join(...) でまとめて出力し、先頭の空白が付かないよう started フラグで制御しています。

• ブロック単位の処理：値が変わった瞬間に前のブロックを確定させて判定することで、追加の配列や二重ループが不要になります。

  ソースコード

import sys


def int_stream():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield num


class Output:
    __slots__ = ("out", "limit", "buf", "started")

    def __init__(self, out, limit=8192):
        self.out = out
        self.limit = limit
        self.buf = []
        self.started = False

    def flush(self):
        if not self.buf:
            return
        chunk = " ".join(self.buf)
        if self.started:
            self.out.write(" " + chunk)
        else:
            self.out.write(chunk)
            self.started = True
        self.buf.clear()

    def emit_repeat(self, s, cnt):
        while cnt > 0:
            space = self.limit - len(self.buf)
            take = cnt if cnt < space else space
            self.buf.extend([s] * take)
            cnt -= take
            if len(self.buf) == self.limit:
                self.flush()

    def finish(self):
        self.flush()
        self.out.write("\n")


def main():
    it = int_stream()
    N = next(it)
    K = next(it)

    out = Output(sys.stdout)

    prev = next(it)
    cnt = 1

    for _ in range(N - 1):
        x = next(it)
        if x == prev:
            cnt += 1
        else:
            if cnt >= K:
                out.emit_repeat(str(prev), cnt)
            prev = x
            cnt = 1

    if cnt >= K:
        out.emit_repeat(str(prev), cnt)

    out.finish()


if __name__ == "__main__":
    main()

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