No.1183 コイン遊び
タグ : / 解いたユーザー数 280
作問者 :
aspi
/ テスター :
AndrewK
問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。