No.2169 To Arithmetic

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.2169 To Arithmetic

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 :

first_vil / テスター :

hamamu

milkcoffee

2 ProblemId : 8414 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2022-12-18 16:02:18

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。あなたは $A$ に対して以下の操作を $0$ 回以上の好きな回数行うことができます。

整数組 $(l,r)\ (1 \le l \le r \le N)$ を選び、各 $i\ (l \le i \le r)$ について $A_i:=A_i+1$ とする。

各 $i\ (1 \le i \le Q)$ について、 $A$ を公差が $d_i$ である等差数列にするまでの操作回数の最小値を求めてください。

入力

 $N$   $Q$ 
 $A_1$   $A_2$   $\dots$   $A_N$ 
 $d_1$ 
 $d_2$ 
 $\vdots$ 
 $d_Q$

入力はすべて整数
$2 \le N \le 2 \times 10^5$
$1 \le Q \le 2 \times 10^5$
$1 \le A_i \le 10^9$
$|d_i| \le 10^9$

出力

$Q$ 行出力してください。

$i\ (1 \le i \le Q)$ 行目には、 $A$ を公差が $d_i$ である等差数列にするまでの操作回数の最小値を出力し、最後に改行してください。

サンプル

サンプル1

入力

出力

4
6
7

$d_1=2$ については以下のような操作列が操作回数を最小化します。

$(l,r)=(1,1)$ とした操作を $1$ 回行う。 $A=(2,4,6,5)$ となる。
$(l,r)=(4,4)$ とした操作を $3$ 回行う。 $A=(2,4,6,8)$ となる。

$d_2=0$ については以下のような操作列が操作回数を最小化します。

$(l,r)=(1,1)$ とした操作を $3$ 回行う。 $A=(4,4,6,5)$ となる。
$(l,r)=(1,2)$ とした操作を $2$ 回行う。 $A=(6,6,6,5)$ となる。
$(l,r)=(4,4)$ とした操作を $1$ 回行う。 $A=(6,6,6,6)$ となる。

$d_3=-1$ については以下のような操作列が操作回数を最小化します。

$(l,r)=(1,1)$ とした操作を $4$ 回行う。 $A=(5,4,6,5)$ となる。
$(l,r)=(1,2)$ とした操作を $3$ 回行う。 $A=(8,7,6,5)$ となる。

サンプル2

入力

出力

0
12

サンプル3

入力

15 8
5 4 5 19 7 7 6 28 19 6 6 9 12 10 25
-6
6
-19
-28
36
13
19
-10

出力

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

No.2169 To Arithmetic

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力