考察
rotation rはCを二つ連結した列C'の長さN window [l,l+N)として扱える。ある色では処理順の1,K+1,2K+1,…個目だけが新しい空箱を要求する「chance ball」になる。
採用する候補: M個目のchance ballまでの最小window端をtwo pointersで追い、答えを差分維持する
棄却する候補: 各rotationを先頭からsimulationする
一回O(N)でN回必要となりO(N^2)になる。
C'を作り、色別総数g、現在window count cnt、chance総数S、収納総数Vを持つ。各左端lで、長さN以内かつS<Mの間右端を進め、色cのceil(cnt/K)変化に応じSとmin(ceil(cnt/K)K,g_c)を差分更新する。Vを答えに記録後、左端ballを同様に削除する。
典型の発動条件
circular列の二重化
発動条件: 全cyclic shiftを同じ線形window処理へ統一したい。
列を二つ連結し、開始l=0,…,N-1の長さN区間として表す。
two pointersと集約値の差分更新
発動条件: 条件S(l,r)≥Mの最小rがlに対して単調で、要素追加削除が一色だけを変える。
右端を戻さず進め、ceil(cnt/K)と収納数の変化だけをglobal値へ反映する。
問題固有の要素
boxを開く可能性があるのは各色でK個ごとのblock先頭だけなので、複雑なsmallest box番号のsimulationは全色chance ballの到着順へ置き換えられる。
別の問題へ持ち帰る視点: 容量付き同種groupingでは、新容器を要求する周期的な要素だけをeventとして抽出する。
正当性
window内の色c個数をcnt_cとすると、そこまでのchance ball数はceil(cnt_c/K)である。先着M個のchance ballが使うbox数を決めるため、最小r with Σ_c ceil(cnt_c/K)≥Mを取り、色cの収納ball数はmin(ceil(cnt_c/K)K,g_c)となる。 開始位置を進めると必要な右端は単調非減少で、各ballを定数回追加削除して全rotationをO(N)で処理できる。
実装上の注意
- M個目のchance ballが長さN内に存在しない場合は右端をl+Nまでに止める。cntがKの倍数を跨ぐ追加・削除時だけceil値が変わることを丁寧に実装する。
復習の核
- Mが十分大きく全ballが入る場合、K=1、一色だけ、M個目がwindow末尾、左端削除でchance数が減る例を愚直simulationと比較する。
計算量と制約
時間
O(N)、円環二周とchance総数の単調window。
空間
O(N)、色頻度と二周列。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All input values are integers.; 1 \leq N \leq 2 \times 10^5; 1 \leq M, K \leq N; 1 \leq C_i \leq N
出典