問題一覧 > 通常問題

No.1183 Coin Game

レベル : / AI推定難易度 : 189 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 290
作問者 : aspi / テスター : AndrewK
お気に入りにしたユーザー ProblemId : 4872 / 自分の提出
問題文最終更新日: 2020-08-22 11:00:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
技術室奥プログラミングコンテスト#5 Day1 (順位表) の他の問題:

Problem Statement

There are coin rows $a,b$, each consisting of $N$ coins arranged in a row.
The states of $a,b$ are given by sequences $A,B$.
$A,B$ are sequences of length $N$ consisting of $0, 1$. When the $i$-th number is $1$, the $i$-th coin is heads, and when it is $0$, the $i$-th coin is tails.
From here, you want to turn the state of $a$ into the state of $b$ by performing some number of times the operation of choosing any $i,j$ ($1\leqq i\leqq j \leqq N$) and flipping the $j-i+1$ coins from the $i$-th through the $j$-th coin of $a$ (changing heads to tails and tails to heads for each coin).
Find the minimum number of operations you need to perform.

Input

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

The sequences $A, B$ are given separated by spaces.
$1\leqq N\leqq 10^6$
$A_i$ and $B_i$ are $0$ or $1$
All inputs are integers

Output

Output on one line the minimum number of operations required to bring the coins to the state of sequence $B$, followed by a newline at the end.

Sample

Sample 1
Input
4
0 0 0 1
1 1 0 1
Output
1

By flipping the coins from the $1$-st through the $2$-nd, the state of the coins can be made $(1, 1, 0, 1)$.

Sample 2
Input
7
0 0 1 1 0 0 0
1 1 0 1 1 0 1
Output
3

By flipping the coins from the $1$-st through the $3$-rd in the $1$-st operation, the state of the coins becomes $(1, 1, 0, 1, 0, 0, 0)$.
By flipping the $5$-th coin in the $2$-nd operation, the state of the coins becomes $(1, 1, 0, 1, 1, 0, 0)$.
By flipping the $7$-th coin in the $3$-rd operation, the state of the coins becomes $(1, 1, 0, 1, 1, 0, 1)$.

Sample 3
Input
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
Output
5

With $5$ operations, the coins can be changed from the state $A$ to the state $B$.

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