いもす法 (imos法)でABC408のC問題
ABC408 の C 問題 Not All Covered をコンテストの時間内に正解できなかったが、解説にあった「いもす法 (imos 法)」を使うとエレガントに正解できるとあったので、自分でも「いもす法 (imos 法)」を実装してみた。
問題 C - Not All Covered
- N 枚の壁があり、壁は砲台で守られている。
- 各砲台は、守る壁の範囲があり、その範囲が与えられる。
- 最も守りの薄い壁を見つけて、そこをカバーする砲台の数を答える。
方法
コンテスト時間内には、壁を表す配列を作成し、各壁の防御する砲台の数を加算していった。しかし、この方法では予想通り制限時間を超えてしまった。
簡単そうなのに正解できず悔しかったので解説を読むと、「いもす法 (imos 法)」を使うと簡単ということで想像以上に短いコードが提示されていた。コードを読んでもアルゴリズムが分からなかったが、「いもす法 (imos 法)」の解説サイトを読んだら「なるほど！」なアルゴリズムだった。
いもす法 (imos 法)
いもす法 (imos 法)は、ある場所にいる人数を把握することを想像すると分かりやすいです。例えば、危険物を扱う広い工場です。終業時間に工場内に人が残っていない事を確認する必要があるが、全てを巡回しても見落としがあるかも知れません。そんな時に使われているのが、この「いもす法 (imos 法)」です。
要は、敷地内への入場者と退出者の人数を把握していてば、その時点で敷地内にいる人数が分かるという仕組みです。
壁の問題に戻ると、
- 壁は常に左から右にスキャンをするとします。
- 砲塔がカバーする左端に来たら、壁に「+1」のマークを書きます。
- 砲塔がカバーする左端に来たら、壁に「-1」のマークを書きます。
- スキャンする時に壁に書かれたマークを加減算すると、そこをカバーする砲塔の数がわかります。
となります。
技術的工夫
N 枚の壁を表す変数として[0] … [N-1]を考えると、上手く表現できません。
そこで、壁ではなく壁を挟む柱を考えることにしました。1 番の壁は柱 0 と柱 1 に挟まれている、N 番の壁は柱(N-1)と柱 N に挟まれている。この柱に砲塔のカバーマークを書いておけば、上手く範囲を表現できます。
これで柱をスキャンすると、\(壁_i\)をカバーする砲塔の数は、\(柱_{i-1}\)の加減算値でわかります。また最後の\(柱_N\)は、常に 0 となることに注意が必要です。
n, m = map(int, input().split())
pole = [0 for _ in range(n + 1)]
# (0) =1= (1) =2= (2) =3= (3) =4= (4) ... (n-1) =n= (n)
for _ in range(m):
l, r = map(int, input().split())
pole[l - 1] += 1
pole[r] -= 1
result = []
temp = 0
for v in pole:
temp += v
result.append(temp)
print(min(result[0:-1]))