No.1818 6 Operations

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

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

問題一覧 > 通常問題

No.1818 6 Operations

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

nok0 / テスター :

Forested

riano

18 ProblemId : 7267 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2022-01-23 11:10:06

問題文

長さ $N$ の非負整数列 $A$ と長さ $M$ の非負整数列 $B$ が与えられます。

あなたは、以下の $6$ 種類の操作を好きな順序で好きな回数繰り返すことができます。

$i (1 \leq i \leq | A |)$ を選ぶ。 $A_{i}$ の値を $A_{i} + 1$ で置き換える。

$i (1 \leq i \leq | A |)$ を選ぶ。 $A_{i}$ の値を $A_{i} - 1$ で置き換える。

$i (1 \leq i \leq | A | - 1)$ を選ぶ。 $A_{i}$ の値を $A_{i} + A_{i + 1}$ で置き換え、 $A_{i + 1}$ を削除する。

$i (1 \leq i \leq | A | - 1)$ を選ぶ。 $A_{i}$ の値を $A_{i} + A_{i + 1} + 1$ で置き換え、 $A_{i + 1}$ を削除する。

$i (1 \leq i \leq | A |)$ 及び非負整数 $x$ を選ぶ。 $A_{i}$ の値を $A_{i} - x$ で置き換え、 $A_{i}$ の直後に $x$ を挿入する。

$i (1 \leq i \leq | A |)$ 及び非負整数 $x$ を選ぶ。 $A_{i}$ の値を $A_{i} - x - 1$ で置き換え、 $A_{i}$ の直後に $x$ を挿入する。

ただし、操作のどの瞬間においても、数列 $A$ の要素は全て非負でなくてはなりません。

数列 $A$ を数列 $B$ に一致させるために必要な操作回数の最小値を求めてください。

制約

入力は全て整数である。
$1 \leq N \leq 10^{3}$
$1 \leq M \leq 10^{3}$
$0 \leq A_{i}$
$0 \leq B_{i}$
$\sum_{i = 1}^{N} A_{i} \leq 3 \times 10^{3}$
$\sum_{i = 1}^{M} B_{i} \leq 3 \times 10^{3}$

入力

 $N$   $M$ 
 $A_{1}$   $A_{2}$   $\dots$   $A_{N}$ 
 $B_{1}$   $B_{2}$   $\dots$   $B_{M}$

出力

$A$ と $B$ を一致させるために必要な操作回数の最小値を出力してください。

サンプル

サンプル1

入力

3 2
3 1 4
1 5

出力

以下では便宜上、問題文で与えられた操作を上から順に操作 $1$ 、操作 $2$ 、 $\dots$ 、操作 $6$ と呼びます。

下記の通りに操作を行うことで、 $3$ 回の操作で $A$ と $B$ を一致させることが可能です。

操作 $2$ で $i = 1$ を選ぶ。その結果 $A = (2, 1, 4)$ となる。

操作 $2$ で $i = 1$ を選ぶ。その結果 $A = (1, 1, 4)$ となる。

操作 $3$ で $i = 2$ を選ぶ。その結果 $A = (1, 5) = B$ となる。

$3$ 回未満の操作で $A$ と $B$ を一致させることは不可能なことが証明できるので、答えは $3$ となります。

サンプル2

入力

1 1
0
3000

出力

サンプル3

入力

6 5
2 7 1 8 2 8
1 8 2 8 4

出力

下記の通りに操作を行うことで、 $8$ 回の操作で $A$ と $B$ を一致させることが可能です。

操作 $2$ で $i = 6$ を選ぶ。その結果 $A = (2, 7, 1, 8, 2, 7)$ となる。

操作 $2$ で $i = 6$ を選ぶ。その結果 $A = (2, 7, 1, 8, 2, 6)$ となる。

操作 $2$ で $i = 6$ を選ぶ。その結果 $A = (2, 7, 1, 8, 2, 5)$ となる。

操作 $2$ で $i = 6$ を選ぶ。その結果 $A = (2, 7, 1, 8, 2, 4)$ となる。

操作 $3$ で $i = 2$ を選ぶ。その結果 $A = (2, 8, 8, 2, 4)$ となる。

操作 $2$ で $i = 1$ を選ぶ。その結果 $A = (1, 8, 8, 2, 4)$ となる。

操作 $5$ で $i = 3, x = 2$ を選ぶ。その結果 $A = (1, 8, 2, 6, 2, 4)$ となる。

操作 $3$ で $i = 4$ を選ぶ。その結果 $A = (1, 8, 2, 8, 4) = B$ となる。

$8$ 回未満の操作で $A$ と $B$ を一致させることは不可能なことが証明できるので、答えは $8$ となります。

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

yukicoder

No.1818 6 Operations

問題文

制約

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力