以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Lamps
ランプ(Lamps)
長い廊下にN 個のランプが一列に並んでいる.ランプには左から順に1 からN までの番号が付いてい
る.各ランプの状態はoffまたはon のいずれかである.
ランプの状態を変える特殊な機構が用意されており,1 回の操作で以下の3 つのいずれかができる:
• 1 ≦p ≦q ≦N なる整数p, q を選び,ランプp, p + 1, . . . , q をすべてoffにする.
• 1 ≦p ≦q ≦N なる整数p, q を選び,ランプp, p + 1, . . . , q をすべてon にする.
• 1 ≦p ≦q ≦N なる整数p, q を選び,ランプp, p + 1, . . . , q の状態をすべて変更する(offならon に,
on ならoffにする).
現在のランプの状態は長さN の文字列A で表される.A のi 文字目(1 ≦i ≦N) は,ランプi がoffであ
るならば0 であり,on であるならば1 である.これから,できるだけ少ない回数の操作を行い,長さN の
文字列B で表される目標の状態にしたい.B のi 文字目(1 ≦i ≦N) は,ランプi をoffにしたいならば0 で
あり,on にしたいならば1 である.
ランプの個数,現在の状態と目標の状態が与えられたとき,必要な操作回数の最小値を求めるプログラム
を作成せよ.
入力
入力は以下の形式で標準入力から与えられる.
N
A
B
出力
標準出力に,必要な操作回数の最小値を1 行で出力せよ.
制約
• 1 ≦N ≦1 000 000.
• A, B は長さN の文字列である.
• A, B の各文字は0, 1 のいずれかである.
ランプ– 1 / 2
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Lamps
小課題
1. (6 点) N ≦18.
2. (41 点) N ≦2 000.
3. (4 点) A の各文字は0 である.
4. (49 点) 追加の制約はない.
入出力例
入力例1 出力例1
8 4
11011100
01101001
この入力例では,例えば以下のような4 回の操作によって目標の状態を作ることができる:
1. ランプ1, 2, 3, 4 の状態を変更する.ランプの状態は00101100 になる.
2. ランプ2 をon にする.ランプの状態は01101100 になる.
3. ランプ6, 7, 8 の状態を変更する.ランプの状態は01101011 になる.
4. ランプ6, 7 をoffにする.ランプの状態は01101001 になる.
3 回以下の操作では目標の状態を作ることはできないので,4 を出力する.
入力例2 出力例2
13 3
1010010010100
0000111001011
入力例3 出力例3
18 5
001100010010000110
110110001000100101
ランプ– 2 / 2