【競技プログラミング】AtCoder Beginner Contest 368_E問題

問題

既存投稿一覧ページへのリンク

一覧ページ

解法手順1

1. 入力の処理

1. N（街の数）、M（電車の数）、X（X1の値）を入力から読み取る。
2. 各電車について、出発地(a)、到着地(b)、出発時刻(s)、到着時刻(t)を読み取る。

2. イベントの作成

1. 各電車の出発と到着を別々のイベントとして扱う。
2. 出発イベントは(時刻, 1, 出発地, 電車番号)のタプルで表す。
3. 到着イベントは(時刻, 0, 到着地, 電車番号)のタプルで表す。
4. これらのイベントをリストDに格納する。

3. 遅延時間の初期化

1. ansにX1の値（X）を設定する。
2. 他の電車の遅延時間（ans[1:]）を0で初期化する。
3. 各街の遅延時間（delay）を0で初期化する。

4. イベントの処理

1. イベントリストDを時刻順にソートする。
2. 各イベントを順番に処理する：
   • 出発イベント（f == 1）の場合：
     • 電車1以外（ind != 0）について、その街の現在の遅延時間から出発時刻を引いた値と0の大きい方を遅延時間として設定する。
   • 到着イベント（f == 0）の場合：
     • 到着地の遅延時間を更新します。新しい遅延時間は、現在の遅延時間と（到着時刻+その電車の遅延時間）の大きい方になる。

5. 結果の出力

1. ans[1:]（電車2からMまでの遅延時間）を出力する。

ACコード1

ac.py

import sys
import logging

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
        
        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)
    
    logger.debug(f"ロガーのセットアップが完了しました。デバッグモード: {debug_mode}")
    return logger

logger = setup_logger(True)

def io_func():
    logger.debug(f"入力処理を開始します")
    N, M, X = map(int, sys.stdin.readline().split())
    D = []
    for i in range(M):
        a, b, s, t = map(int, sys.stdin.readline().split())
        a, b = a - 1, b - 1
        D.append((s, 1, a, i))
        D.append((t, 0, b, i))
    logger.debug(f"入力処理が完了しました: N={N}, M={M}, X={X}, イベント数={len(D)}")
    return N, M, X, D

def solve(N, M, X, D):
    logger.debug(f"解法処理を開始します")
    ans = [0] * M
    ans[0] = X
    delay = [0] * N
    D.sort()
    logger.debug(f"イベントをソートしました")
    
    for t, f, v, ind in D:
        if f:
            if ind:
                ans[ind] = max(0, delay[v] - t)
                logger.debug(f"出発イベント処理: 電車{ind}の遅延時間を{ans[ind]}に設定")
        else:
            delay[v] = max(delay[v], t + ans[ind])
            logger.debug(f"到着イベント処理: 街{v}の遅延時間を{delay[v]}に更新")
    
    logger.debug(f"解法処理が完了しました")
    return ans[1:]

def main():
    logger.debug(f"メイン処理を開始します")
    N, M, X, D = io_func()
    result = solve(N, M, X, D)
    print(*result)
    logger.debug(f"メイン処理が完了しました")

if __name__ == "__main__":
    main()