概要

与えられた花の列から、同じ品種が \(K\) 本以上連続している「見栄えの良い区間」に含まれない花をすべて取り除き、残った花を順番に出力する問題。

考察

この問題では、各花について「自分を含む長さ \(K\) 以上の同じ品種の連続部分列が存在するか？」を判定する必要があります。

素朴な方法として、各位置 \(i\) に対して前後を見て同じ値が何個続くかを毎回調べるやり方がありますが、これは最悪の場合 \(O(N^2)\) の計算量となり、\(N\) が最大 \(10^6\) なので間に合いません。

重要な観察は、「同じ品種が連続している区間」をまとめて扱うことです。つまり、連続する同じ値を持つ区間（以下、グループ）ごとに分けて、その長さが \(K\) 以上かどうかだけを見ればよいのです。もしグループの長さが \(K\) 以上であれば、そのグループ内のすべての花は残すことになります。

したがって、まず入力の配列を「同じ値が続く区間」に分割し、それぞれの区間の長さを調べて、\(K\) 以上ならその区間に属する花をすべて残すという処理を行うのが効率的です。

例えば、入力が 1 1 2 2 2 3 で \(K=3\) の場合： - 値1の区間：長さ2 → 残らない - 値2の区間：長さ3 → 残る - 値3の区間：長さ1 → 残らない
結果として残るのは 2 2 2 です。

このように、グループ単位で考えることで、全要素を個別に確認せずとも答えを得ることができます。

アルゴリズム

1. 入力をリスト \(S\) として受け取る。
2. 配列 \(S\) を先頭から走査し、連続する同じ値を持つ「グループ」を検出していく。
   • 各グループは (値, 開始位置, 長さ) の情報を持つ。
3. 各グループについて、長さが \(K\) 以上であれば、その範囲の花を「残す」フラグを立てる。
4. 「残す」フラグが立っている花だけを集めて出力する。

具体的には、groupby を使ってもよいですが、ここでは手動でループを使って実装しています。これは、開始インデックスと長さを正確に取得するためです。

計算量

• 時間計算量: \(O(N)\)
  各要素を一度だけ読むだけで済むため、線形時間で処理できます。
• 空間計算量: \(O(N)\)
  入力配列およびフラグ管理用の配列 keep に \(O(N)\) 必要です。

実装のポイント

• グループの抽出時に、開始位置と長さを正確に記録することが重要。

• フラグ管理用の配列 keep を使うことで、どの花を残すべきかを後で簡単に判定できる。

• 最終的な出力は、空の場合も「改行のみ」を出力する必要があることに注意。

  ソースコード

import sys
from itertools import groupby

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    S = list(map(int, data[2:]))

    # Group consecutive same elements
    # groups will store (value, start_index, length)
    groups = []
    i = 0
    while i < N:
        val = S[i]
        start = i
        while i < N and S[i] == val:
            i += 1
        length = i - start
        groups.append((val, start, length))
    
    # Create a boolean array to mark whether each flower should be kept
    keep = [False] * N
    for val, start, length in groups:
        if length >= K:
            # Mark all flowers in this group as keep
            for j in range(start, start + length):
                keep[j] = True
    
    # Collect the result
    result = [S[i] for i in range(N) if keep[i]]
    
    if result:
        print(' '.join(map(str, result)))
    else:
        print()

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。