ABC084 C - Special Trains

AtCoder Python3

備忘録

問題

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 = ii()
    CSF = [il() for _ in range(N-1)]
    times = [0] * N

    for n in range(N-1):
        # 西に位置する駅から順に、N番目の駅までの到着時間を求める
        sc, ss, sf = CSF[n]
        time = sc + ss
        for nc, ns, nf in CSF[n+1:]:
            # 次の駅に到着したときの処理
            if time <= ns:
                # 始発より早く、駅に到着する場合
                time += abs(time - ns) + nc
            else:
                # 始発の後、駅に到着する場合
                if time % nf == 0:
                    # 到着した時間に、次の電車が出る場合
                    # i駅からi+1駅までの電車の移動時間Ciを加算
                    time += nc
                else:
                    # 到着した時間から、次の電車まで待ち時間がある場合
                    # i駅からi+1駅までの電車の移動時間Ciと待ち時間を加算
                    time += nc + (nf - (time % nf))
        times[n] = time
    print(*times, sep="\n")


if __name__ == '__main__':
    main()

考え方

西に位置する駅から順に、最速で電車に乗ることができる時間を求めます。
最速で乗る時間を求めるには、始発が出るより早く駅に到着することができるか否かで
場合分けをする必要があります。

  • 回答概要
    • 駅に着いた時間と駅から出る始発の時間を比較して場合分けをする
    • 始発より早く駅に着いた場合には、始発まで待つ必要がある
    • 始発より後に駅に着いた場合には、始発以降の電車に乗る必要がある

まず、どのような乗り方が最速で電車に乗ることができるのかを考えます。

仮に始発(開通式開始後に初めて運行される列車)がS秒後に運行される駅iを例に考えると、
駅iに到着した時間tがS以下の場合(t <= S)には、まだ始発が出ていないため、
始発に乗ることが最善です。
そのため、到着時間と始発までの時間の差分(S - t)が待ち時間となります。

駅iに到着した時間tがSより後の場合(t > S)には、始発に乗ることができないため、
始発以降のF秒おきに運行される電車に乗る必要があります。
そのため、到着時間と次の電車までの時間の差分が待ち時間となります。

ただし、始発以降の電車には、待ち時間が必要ない場合が存在します。
到着した時間が次の電車の運行時間の場合には、待ち時間が必要ありません。
そのため、到着時間tが運行時間Fで丁度割り切れる場合(t % F == 0)には、待ち時間の発生がありません。

また、始発以降の電車に乗る場合かつ待ち時間が必要な場合の待ち時間の求め方は、
前回運行された電車から何分経過しているかを求め、定期運行の時間を引くことで求めることが出来ます。
(到着時間t、定期運行の時間をFとしたとき、t % Fで前回の電車から何分経過しているか求めることが出来る。
そのため、F - (t % F)で待ち時間を求めることができる。）