問題一覧 > 通常問題

No.2209 Flip and Reverse

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 163
作問者 : ShirotsumeShirotsume / テスター : AngrySadEightAngrySadEight 👑 ygussanyygussany
6 ProblemId : 8979 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-04 12:24:25

問題文

0, 1 からなる長さ $N$ の文字列 $S, T$ が与えられます。$S$ に対して以下の操作を行って $T$ と一致させるための操作回数の最小値を求めてください。

  • $1 \leq i \leq N$ を満たす整数 $i$ を選ぶ。$S$ の $i$ 文字目を現在とは異なる方の文字に変更する。つまり、 0 なら 1、 1 なら 0 に変更する。その後、 $S$ の前後を反転する。

制約

  • $N$ は整数
  • $1 \leq N \leq 10^6$
  • $S,T$ は0, 1 からなる長さ $N$ の文字列

入力

入力は標準入力から以下の形式で与えられる。

$N$
$S$
$T$

出力

答えを出力せよ。

サンプル

サンプル1
入力
3
001
010
出力
2

操作の一例を以下に示します。

  • $i = 2$ として操作を行う。$S$ の $2$ 文字目を 0 から 1 に変更し、$S$ の前後を反転する。操作後、$S =$ 110 となる。
  • $i = 1$ として操作を行う。$S$ の $1$ 文字目を 1 から 0 に変更し、$S$ の前後を反転する。操作後、$S =$ 010 となる。

$2$ 回未満の操作で $S$ と $T$ を一致させることはできません。

サンプル2
入力
2
01
11
出力
1

操作の一例を以下に示します。

  • $i = 1$ として操作を行う。$S$ の $1$ 文字目を 0 から 1 に変更し、$S$ の前後を反転する。操作後、$S =$ 11 となる。
サンプル3
入力
4
1111
1111
出力
0
サンプル4
入力
10
0110111010
1001010011
出力
5

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