ABC408 C – Not All Covered

全く解法が浮かびませんでした、、、imos法という方法で解くらしいです。

C - Not All Covered

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

解き方

imos法では以下のような表を考えると、わかりやすいのかなと思います。入力例1で考えます。

imos法の詳細な解説はこちらを確認するのが良さそうです。

砲台4の行までは砲台が守っている壁をoで表しています。Cは最初1-11まで全て0です。

①では砲台1-4まで1から順にみてoがつき始めた場所を+1、oがなくなった場所を-1します。

Cのi=2をスタートとして、i-1とiを足した値をC[i]に代入していったものがC – ②になります。

こうするとそれぞれの壁を守っている砲台の数が算出されます。

あとはCの0-N（入力例1では10）までの中で最小の値を出力すれば良いです。（C[N+1]は必ず0になります）

以下のコードでACできました。

def i_map():
    return map(int, input().split())


def i_list():
    return list(map(int, input().split()))


n, m = i_map()
c = [0] * (n + 1)

# ①
for i in range(m):
    l, r = i_map()
    l -= 1
    r -= 1
    c[l] += 1
    c[r + 1] -= 1

# ②
for i in range(1, n + 1):
    c[i] = c[i] + c[i - 1]

print(min(c[0:n]))