ABC024 C - 民族大移動

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, D, K = il()
    LR = [il() for _ in range(D)]
    ST = [il() for _ in range(K)]
    days = [-1] * K

    for i, st in enumerate(ST):
        s, t = st
        for day, lr in enumerate(LR):
            l, r = lr
            if s < t and s in range(l, r+1):
                if t in range(l, r+1):
                    s = t
                else:
                    s = r
            if s > t and s in range(l, r+1):
                if t in range(l, r+1):
                    s = t
                else:
                    s = l
            if s == t:
                days[i] = day + 1
                break
    print(*days, sep="\n")


if __name__ == '__main__':
    main()

考え方

各民族は、移動できる範囲の最大値を常に取り続ける移動が最適解となります。
そのため、貪欲法で回答を得ることができます。

• 回答概要
  • 常に移動範囲の最大値を取り続ける
  • 現在位置と目的地の位置関係から左右のどちらに進むか判定する

---

各民族の位置と目的地を数直線上に存在していると考えます。
民族が1日で移動できる最大位置まで移動を行っても、
損（目的地への到着が遅れる）ことはありません。
そのため、常に最大値を取り続ける貪欲法で回答を求めます。

各民族の移動方向は現在位置と目的地の関係から判定を行います。
現在位置Sより目的地Tの方が右に存在する場合(S < T)、
移動範囲L ~ Rの右端(R)を取り続けるのが最適です。
現在位置Sより目的地Tの方が左に存在する場合(S > T)、 移動範囲L ~ Rの左端(R)を取り続けるのが最適です。

以上の判定を、全ての民族に対して行い、
何日目に目的地へ到達することができるのか探索します。