AtCoder ABC103 参戦記(D問題) - アールグレー特売所

AtCoder ABC103参戦記の後編です。D問題を尺取り法の考えで解くことができました。ちなみに公式の解説をちらっとだけ見ましたが、全く方針が違いました...

D問題 (Island War)

N, M = map(int, input().split())
AB = []
for i in range(M):
    AB.append([int(i) for i in input().split()])
AB.sort()
 
MinBar = 1
abar = AB[0][0]
bbar = AB[0][1]
for i in range(1, M):
    if AB[i][0] < bbar:
        bbar = min(bbar, AB[i][1])
    else:
        MinBar += 1
        abar = AB[i][0]
        bbar = AB[i][1]
print(MinBar)

与えられたa_iとb_iのセットを昇順でソートして、a_iがb_{start ~ i-1}の最小値を超えるまで動し、超えたら橋の破壊を確定する、という方針です。ここでb_startは初期状態ではb₁です。以降a_iがb_{start ~ i-1}を超えるごとにb_startをb_iに更新します。例を挙げて考えてみます。N = 5, M = 4, AB = [(1, 4), (2, 3), (4, 5), (1, 2)]とします。最初のAB.sort()でABの中身は[(1, 2), (1, 4), (2, 3), (4, 5)]となります。下図はこの条件を視覚化した図になります。この条件では1-2、2-3、4-5間の3本の橋を切らないといけません。

f:id:earlgrey_yh:20180722112208p:plain

abarはaiと読み替えて大丈夫です。bbarは上記にあるようにb_{start ~ i-1}の最小値です。(a₁, b₁) = (1, 2)なので、初期状態はabar = 1, bbar =2, minBar = 1です。(a₂, b₂) = (1, 4)なので、abarの位置は変わらず、bbarもmin(2, 4) = 2なので変わりません。因みに破壊する橋はabarとbbarの間のどこかに設置されています(間ならばどこでもいい）。次の(a₃, b₃)でabarがbbarに追いついてしまうので、1-2、1-4間で1本目の破壊を確定してしまいます。abar = 2, bbar = 3にリセットして、新たに破壊する対象を1本追加します(minBar = 2)。

f:id:earlgrey_yh:20180722111201p:plain