【競プロ精進メモ】区間スケジューリング問題は区間の終端に注目する

ダイの大冒険という漫画が大好きなbun913です。

私は趣味で競技プログラミングをしており、不定期に学習した内容やコンテストへの参加記録を吐き出しています。

今日はD - Destroyer Takahashiという問題を解いていて、区間スケジューリング問題という定型問題に触れたのでそのメモを出力しています。

※ このシリーズは特にメモ的要素が強いため、お役立ち情報の発信という側面が非常に少ないためご了承ください。

自分なりまとめ

• 今回は与えられた範囲のうち終端が小さい順に処理していく
  • 最後に殴った位置を覚えておく
  • ループ中の区間の始端の位置と最後に殴った位置を見比べる
  • すでに壊せているようなら殴らずに次の区間へ
• この問題のようにいくつかの区間が与えられて（右端が）小さい順に処理をしていく問題を区間スケジューリング問題というらしい

N, D = map(int, input().split())
walls = [list(map(int, input().split())) for _ in range(N)]
# 右の位置を基準にソートする
walls = sorted(walls, key=lambda x: x[1])

ans = 0
last = -1 #初期状態
for l,r in walls:
    if last == -1:
        last = r
        ans += 1
        continue
    # 最後のパンチからD以上離れていたらパンチをする
    if last + D <= l:
        last = r
        ans += 1

print(ans)

区間の終端が小さい順にソートする

直観的には区間スケジューリング問題 | アルゴ式の解説で出てきた言葉が非常にわかりやすかったです。

終了時刻が早い予定を選ぶことで、 その後の残りの時間のプランニングにより多くの選択肢を残せるのです。
このような「あとにより多くの選択肢を残せるようにする」という視点は、 貪欲法を考えるときに重要です。

今回も同様で終端が小さい順にソートしていますので、区間をループする際に自分より終端が左側にあるものはないということですね。

ソート後の区間をループしていき、まだ壊れていない壁があれば殴りつつ、最後に殴った位置を更新すれば良さそうです。

厳密になぜなるのかというのは解説をみるとよさそうです。（解説 - AtCoder Beginner Contest 230）

ということで、以下のようにコードを提出することで正解となりました。

N, D = map(int, input().split())
walls = [list(map(int, input().split())) for _ in range(N)]
# 右の位置を基準にソートする
walls = sorted(walls, key=lambda x: x[1])

ans = 0
last = -1 #初期状態
for l,r in walls:
    if last == -1:
        last = r
        ans += 1
        continue
    # 最後のパンチからD以上離れていたらパンチをする
    if last + D <= l:
        last = r
        ans += 1

print(ans)

おぉぉぉ。面白い。

この辺りの仕組みを脳内で理解しておくことで、他の問題にも応用できそうです（小並感）