貪欲法とは

最も単純な貪欲法の例を挙げる。

例. 1週間毎日お小遣いを0~100円までもらえるとする。もらえる金額はあなたが決めることができるとする。

Q、1週間後に一番たくさんお金を貯めるにはどうすればいい？ A、毎日100円ずつもらう

以上、最もシンプルだと思う貪欲法である。要は求めたい答えに至るまでの各回で何かしらの行動を選択できる場合に、答えに対して最適な行動を取っていくのが貪欲法だ。

だいたいイメージが湧いたと思うので、例題を踏まえて実装パターンを確認する。…といっても最適な行動は毎回変わるので、考え方さえ分かればそれをコードで表現するだけになるが。

例題: ABC024 C

貪欲法の例題として「巡回セールスマン問題」がよく取り上げられるらしい。のだが、数学が得意じゃない僕からすると初手に巡回セールスマン問題は少し難しい。二次元に移動が発生するうえに、距離を求める計算が必要になる。

なので、貪欲法の勘所を掴むにはもう少し単純なものが良い…と思って見つけたのがこれ。

C - 民族大移動

問題を要約すると、とある民族たちは毎日L~Rの範囲で移動することができる。スタートとゴールはSとTになっている。最短で目的地に着くには何日かかるか？だ。

考え方

この問題は巡回セールマン問題より易しい。なぜかというと、街が一次元にしか存在しないからだ。たとえば街が7つあるとすると、この問題では以下のように街が並んでいることになる。

0 1 2 3 4 5 6

ここでは、ひとまず民族が一つしかいないものとする。この民族は最初3にいるとする。

そのうえで、ゴールが6の場合はその日移動可能な範囲で一番6に近づけるところまで進めば良い。逆にゴールが0の場合は、その日移動可能な範囲で一番0に近づけるところまで進めば良い。いまいる街が移動可能な範囲にない日は動けない。

つまり最初のシンプルな貪欲法に対して、正負の方向と行動制限が付いただけだ。

以上から、僕は以下のように実装した。

n,d,k=map(int, input().split())
LR=[list(map(int, input().split())) for _ in range(d)]
ST=[list(map(int, input().split())) for _ in range(k)]

ans=[]

for s,t in ST:
  # 目的地はどっち向きか
  is_right=t-s>0
  for i in range(d):
    l,r=LR[i]
    # 今日は今いる街から移動できるか
    if l<=s<=r:
      # 移動できるなら目的地に一番近いところまで行く
      # 目的地より先に到達できそうなら、その日がゴールになる
      if is_right:
        s=r
        if s>=t:
          ans.append(i+1)
          break
      else:
        s=l
        if s<=t:
          ans.append(i+1)
          break

for a in ans:
  print(a)

ちなみに今回は「どの民族も D 日以内に目的地に到着できることが保証されている」ので、最終日まで移動しきれない場合を考えなくて良い。