Loading [MathJax]/jax/output/HTML-CSS/config.js

AtCoder Beginner Contest 084 C – Special Trains をPython3で解く

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典：
AtCoder Beginner Contest 084 C – Special Trains

特に深い理由はないが、たまにはいいだろうと再帰関数で解いてみた。
このような、再帰関数で得た値を再利用しない形の関数は末尾再帰と呼ばれる。より具体的には、return分で再帰関数をそのまま帰すような形のものである。

ちなみに末尾再帰で書くと、ごく簡単な書き換えで通常のループ処理にすることができるので、言語によっては勝手に最適化をしてくれることがある（関数呼び出しのコストやメモリ使用量の削減につながる）……のだが、残念ながらPythonでは現在のところしないらしい……。

# AtCoder Beginner Contest 084 C - Special Trains
# https://atcoder.jp/contests/abc084/tasks/abc084_c
# tag: 愚直

# 愚直にシミュレートしていけばいい。
# 駅についた時、次に乗れる電車がいつくるのかを判定する
# ところが、若干ややこしいかも。割った余りをうまく使っていこう

def main():
    N = int(input())
    stations = [list(map(int, input().split())) for _ in range(N-1)]

    # 今回はなんとなく再帰関数で書いてみた。なんとなく。
    # get_cost(駅番号, その駅への到着時間) = 駅 N に着く時間
    def get_cost(st, time):
        # 駅 N に着いたらその時間を返す(0-indexedなので注意)
        if st == N - 1:
            return time

        # 次に乗れる電車の時間を求める
        c, s, f = stations[st]

        # 始発までは待たないとダメ
        if time <= s:
            next_train = s
        else:
            # 前回の電車から何分遅れで到着？
            late = time % f

            # 電車の時間ぴったりなら、その電車に乗れる
            if late == 0:
                next_train = time

            # でなければ、次の電車
            else:
                next_train = time + f - late

        # 次の駅へ到着したとして再帰
        return get_cost(st+1, next_train + c)

    for i in range(N):
        print(get_cost(i, 0))

main()

abc084_c.py view raw

関連

コメントを残すコメントをキャンセル