問題一覧 > 通常問題

No.1183 コイン遊び

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 202
作問者 : aspiaspi / テスター : AndrewKAndrewK
1 ProblemId : 4872 / 出題時の順位表
問題文最終更新日: 2020-08-22 11:00:44

問題文

$N$ 枚のコインが一列に並んだコイン列 $a,b$ があります。
$a,b$ の状態は数列 $A,B$ によって与えられます。
$A,B$ は $0, 1$ からなる長さ $N$ の数列で、$i$ 番目の数が $1$ のとき $i$ 枚目のコインが表であることを、$0$ のとき $i$ 枚目のコインが裏であることを表します。
ここからあなたは任意の $i,j$ ($1\leqq i\leqq j \leqq N$)を選び、 $a$ の $i$ 枚目から $j$ 枚目までの $j-i+1$ 枚のコインをひっくり返す(それぞれのコインに対して表を裏に、裏を表にする)操作を何回か行うことで、$a$ の状態を $b$ の状態にしたいと思います。
あなたが最小で何回操作する必要があるか求めてください。

入力

$N$
$A_1\;\,A_2\;\,...\;\,A_N$
$B_1\;\,B_2\;\,...\;\,B_N$

数列 $A, B$ は空白区切りで与えられます。
$1\leqq N\leqq 10^6$
$A_i$ および $B_i$ は $0$ または $1$
入力は全て整数

出力

コインを数列 $B$ の状態にするために必要な最小の操作の数を一行で出力し、最後に改行してください。

サンプル

サンプル1
入力
4
0 0 0 1
1 1 0 1
出力
1

$1$ 枚目から $2$ 枚目までのコインを裏返すことで、コインの状態を $(1, 1, 0, 1)$ にすることができます。

サンプル2
入力
7
0 0 1 1 0 0 0
1 1 0 1 1 0 1
出力
3

$1$ 回目の操作で $1$ 枚目から $3$ 枚目までのコインを裏返すことで、コインの状態は $(1, 1, 0, 1, 0, 0, 0)$ となります。
$2$ 回目の操作で $5$ 枚目のコインを裏返すことで、コインの状態は $(1, 1, 0, 1, 1, 0, 0)$ となります。
$3$ 回目の操作で $7$ 枚目のコインを裏返すことで、コインの状態は $(1, 1, 0, 1, 1, 0, 1)$ となります。

サンプル3
入力
20
0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0
1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1
出力
5

$5$ 回の操作でコインを $A$ の状態から $B$ の状態にすることが出来ます。

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