問題一覧 > 通常問題

No.1818 6 Operations

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 45
作問者 : nok0nok0 / テスター : ForestedForested rianoriano
18 ProblemId : 7267 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-23 11:10:06

問題文

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

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

  • $i\ (1 \le i \le |A|)$ を選ぶ。 $A_i$ の値を $A_i+1$ で置き換える。

  • $i\ (1 \le i \le |A|)$ を選ぶ。 $A_i$ の値を $A_i-1$ で置き換える。

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

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

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

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

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

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

制約

  • 入力は全て整数である。
  • $1 \le N \le 10^3$
  • $1 \le M \le 10^3$
  • $0 \le A_i$
  • $0 \le B_i$
  • $\sum_{i=1}^N A_i \le 3\times 10^3$
  • $\sum_{i=1}^M B_i \le 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
出力
3

以下では便宜上、問題文で与えられた操作を上から順に 操作 $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
出力
3000

サンプル3
入力
6 5
2 7 1 8 2 8
1 8 2 8 4
出力
8

下記の通りに操作を行うことで、 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。