問題一覧 > 通常問題

No.1767 BLUE to RED

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 112
作問者 : first_vilfirst_vil / テスター : saksak 👑 ygussanyygussany
4 ProblemId : 7034 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-26 14:45:12

問題文

ALiCEちゃんは $10^{100}$ 個のマスが横一列に並んだマス目を見つけました。マス目の左から $A_1,A_2,\dots,A_N$ 個目のマスは赤く、左から $B_1,B_2,\dots,B_M$ 個目のマスは青く、その他のマスは白く塗られています。

青が嫌いなALiCEちゃんは以下の操作を $0$ 回以上繰り返すことで青いマスを無くしたいと考えています。

  • いずれかの赤いマスに隣り合うマスを選び、そのマスの色を赤に変更する。

ALiCEちゃんが目標を達成するために必要な操作回数の最小値を求めてください。

入力

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_M$
  • 入力はすべて整数
  • $1 \le N,M \le 2 \times 10^5$
  • $1 \le A_i,B_i \le 10^9$
  • $A_i \lt A_{i+1}$
  • $B_i \lt B_{i+1}$
  • $A_1,A_2,\dots,A_N,B_1,B_2,\dots,B_M$ はすべて異なる

出力

ALiCEちゃんが目標を達成するために必要な操作回数の最小値を出力し、最後に改行してください。

サンプル

サンプル1
入力
5 2
1 3 14 19 20
6 15
出力
4

以下のように操作することで操作回数の最小値 $4$ が達成できます。

  1. マス $3$ に隣り合うマス $4$ を赤にする。
  2. マス $4$ に隣り合うマス $5$ を赤にする。
  3. マス $5$ に隣り合うマス $6$ を赤にする。
  4. マス $14$ に隣り合うマス $15$ を赤にする。
サンプル2
入力
7 10
4 16 18 20 22 37 99
6 7 29 38 55 64 68 70 92 97
出力
50

サンプル3
入力
1 20
7
24 25 26 32 40 41 46 53 59 60 64 74 81 85 90 93 95 98 99 100
出力
93

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