A - Volume Control Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

ストーリー

AtCoder社は年に一度、企業合同演奏会を開催している。 高橋社長は演奏会で指揮者をすることになった。 演奏者の音量を調整して最高の演奏にしてほしい。

問題文

演奏会では NN 人の演奏者が横一列に並び TT 秒の曲を演奏している。 左から ii (0≤i≤N−1)(0\leq i\leq N-1) 番目の演奏者を演奏者 ii と呼ぶことにする。

各演奏者について、デフォルトの音量を基準値 00 とする。指揮者は毎秒、0≤L≤R≤N−10\leq L\leq R\leq N-1 を満たす整数の組 (L,R)(L,R) と整数 dVdV を選択し、L≤i≤RL\leq i\leq R を満たす全ての演奏者 ii に、dVdV だけ音量を変更するよう指示を出すことができる。 時刻 tt に指示を出された演奏者は時刻 tt 以降（tt を含む）の音量が dVdV だけ変化する。

複数回音量変更の指示をした場合、変化量は累積される。例えば、時刻 00 に演奏者 ii の音量を 11 変化させ、時刻 11 に演奏者 ii の音量を −2-2 変化させた場合、時刻 11 における音量は 1−2=−11-2=-1 となる。

各時刻 tt、各演奏者 ii について、理想的な音量 Vt,iV_{t,i} が入力として与えられるので、 実際の音量と理想的な音量との差の絶対値の総和が出来るだけ小さくなるように指揮をして欲しい。

得点

時刻 tt における演奏者 ii の実際の音量を Vt,i′V_{t,i}' とし、理想的な音量とのずれの総和を S′=∑t=0T−1∑i=0N−1∣Vt,i−Vt,i′∣S'=\sum_{t=0}^{T-1}\sum_{i=0}^{N-1}|V_{t,i}-V_{t,i}'| とする。何も指示をしなかったときのずれの総和を S0=∑t=0T−1∑i=0N−1∣Vt,i∣S_{0}=\sum_{t=0}^{T-1}\sum_{i=0}^{N-1}|V_{t,i}| としたとき max⁡(S0−S′+1,0)\max(S_{0}-S'+1, 0) がそのテストケースの得点となる。

テストケースは全部で 100 個あり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。

入力

演奏者の人数 NN、演奏の長さ TT、 時刻 tt における演奏者 ii の理想的な音量 Vt,iV_{t,i} が以下の形式で与えられる。 

NN TT
V0,0V_{0,0} ⋯\cdots V0,N−1V_{0,N-1}
⋮\vdots
VT−1,0V_{T-1,0} ⋯\cdots VT−1,N−1V_{T-1,N-1}

各値はそれぞれ以下の制約を満たす。

  • N=50N=50
  • T=500T=500
  • −3≤Vt,i≤3-3\leq V_{t,i}\leq 3

出力

各時刻での指示を以下の形式で出力せよ。

L0L_{0} R0R_{0} dV0dV_{0}
⋮\vdots
LT−1L_{T-1} RT−1R_{T-1} dVT−1dV_{T-1}
  • Lt,RtL_{t}, R_{t} は音量変更する演奏者の範囲を表す整数値であり、0≤Lt≤Rt≤N−10\leq L_{t}\leq R_{t}\leq N-1 を満たさなければならない。
  • dVtdV_{t} は音量を変更する量を表す整数値であり、∣dVt∣≤50|dV_{t}|\leq 50 を満たさなければならない。

例を見る

入力生成方法

Vt,iV_{t,i} は以下の方法で生成される。

  1. Vt,iV_{t,i} を0で初期化する。
  2. 各 tt ごとに、0≤a,b≤N−10\leq a,b\leq N-1 を満たす整数値 a,ba,b と d∈{−1,1}d\in\{-1,1\} を一様ランダムに生成し、min⁡(a,b)≤i≤max⁡(a,b)\min(a,b)\leq i\leq \max(a,b) を満たす全ての ii に対して Vt,iV_{t,i} に dd を加える。
  3. 2を3回繰り返す。

ツール(入力ジェネレータ・ビジュアライザ)

コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。

入力例1Copy

Copy
5 3
0 0 0 0 0
0 -1 -1 -1 0
1 2 2 2 2

この入力例は例示のためのもので、制約を満たさないことに注意せよ。

出力例1Copy

Copy
0 0 0
1 3 1
1 4 -3

2025-04-10 (Thu)
21:09:53 +00:00