$T$ 個のテストケースが与えられるので、それぞれについて答えてください。 正整数 $K$ と、長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。 各 $i=1,2,\ldots,N$ について、以下で定める $L_i$"> $T$ 個のテストケースが与えられるので、それぞれについて答えてください。 正整数 $K$ と、長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。 各 $i=1,2,\ldots,N$ について、以下で定める $L_i$">
[go: up one dir, main page]

難易度評価

難易度を1〜10段階で評価できます。投票はあとから変更・取り消しできます。

難易度(投票) Lv.5.5 (2票)

投票の分布
  1. Lv.10票
  2. Lv.20票
  3. Lv.30票
  4. Lv.40票
  5. Lv.51票
  6. Lv.61票
  7. Lv.70票
  8. Lv.80票
  9. Lv.90票
  10. Lv.100票

難易度の目安を見る ↗

ログインして難易度を投票

外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

Periodic Noise

作成者 yuki4869

難易度(作成者設定) Lv.5

難易度(投票) Lv.5.5 (2票)

実行時間制限
2 秒
メモリ制限
512 MiB

問題文

TT 個のテストケースが与えられるので、それぞれについて答えてください。

正整数 KK と、長さ NN の整数列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N) が与えられます。

各 i=1,2,…,Ni=1,2,\ldots,N について、以下で定める LiL_i を求めてください。


整数列 BB を B=(B1,B2,…,BN−i+1)=(Ai,Ai+1,…,AN)B=(B_1,B_2,\ldots,B_{N-i+1}) = (A_i,A_{i+1},\ldots,A_N) と定義します。

KK 個の整数 C1,C2,…,CKC_1,C_2,\ldots,C_K を自由に選び、BB の各項に対して、次の操作を同時に 11 度だけ行います。

  • Bj←Bj+C((j−1)  mod  K)+1B_j \leftarrow B_j + C_{((j-1)\ \ mod\ \ K) +1}

C1,C2,…,CKC_1,C_2,\ldots,C_K を適切に選んで操作を行うことで、操作後の BB の先頭 LL 項と AA の先頭 LL 項を一致させることができるような整数 LL (0≤L≤N−i+1)(0\leq L\leq N-i+1) の最大値を LiL_i とします。

なお、KK 個の整数 C1,C2,…,CKC_1,C_2,\ldots,C_K は、ii ごとに独立して選ぶことができます。

制約

  • 1≤T≤1031 \leq T \leq 10^3
  • 1≤K≤N≤2×1051\leq K\leq N\leq 2\times 10^5
  • −109≤Ai≤109-10^9\leq A_i\leq 10^9
  • すべてのテストケースにおける NN の総和は 2×1052 \times 10^5 以下
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

TT case1\mathrm{case}_1 case2\mathrm{case}_2 ⋮\vdots caseT\mathrm{case}_T

各テストケース caset (1≤t≤T)\mathrm{case}_t ~ (1 \leq t \leq T) は以下の形式で与えられる。

N  KN\ \ K A1  A2…ANA_1\ \ A_2 \ldots A_N

出力

TT 行出力せよ。

tt 行目には tt 番目のテストケースについて、L1  L2…LNL_1\ \ L_2 \ldots L_N をこの順に空白区切りで出力せよ。

サンプル 1

入力

1
8 2
1 4 3 7 5 10 7 14

出力

8 2 5 2 3 2 2 1

i=1i=1 の場合、C1=C2=0C_1=C_2=0 を選ぶことで、AA と BB の先頭 88 項を一致させることができます。よって L1=8L_1=8 です。

i=2i=2 の場合、C1=−3,C2=1C_1 = -3,C_2 = 1 を選ぶことで、AA と BB の先頭 22 項を一致させることができます。また、先頭 33 項以上を一致させることはできないため、 L2=2L_2=2 です。