Problem G Traffic ACM/ICPC Japanese Alumni Group 講評担当: 吉野 問題概要 • 牟田によるオリジナル問題 • 信号の待ち時間を加味した最短経路の計算 – 格子状に道路が配置されており、格子点には信号がある – 信号が青のときは進め、赤のときは青になるまで 止まって待たなければならない • 交通法規は守らないと大変なことになりますよ？ • 道路は縦横それぞれ 100 本まで – 間隔は 1000 以下 Submit 状況 • Total 14 submits – うち 3 チーム accepted • Kitsune- (2), Makegumi (1), CLAGGANO (2) – First acceptance: 153min. (kitsune-) – Wrong Answer の山もありますが • トータルでは 4 チームからのトライがありました 解法 • Dijkstra 法の変形 – 交差点と、スタート・ゴールを頂点とするグラフ – 次に行く頂点が交差点である場合は信号待ちの 分を加味 – 時々コンテスト本番でも出ることがあります • World Final 2003, Problem J: Toll など • とにかくルールどおりに実装すれば報われる はずです 変形 Dijkstra 法 • 用意するもの – – • priority queue (時間順), 最短時間テーブル 基本的には通常の Dijkstra 法とかわらない 手順 1. 2. 3. 4. 開始点を時間 0 で queue に挿入 queue から点を一つ取り出す。ゴールなら終了 すでに最短時間が求まっている頂点ならば 2. に戻る 最短時間テーブルを更新し、その頂点から隣接した 頂点へ展開する • このときちょっと手を加える(今回では信号待ち) ケースが多い 信号待ちの計算 • 信号は一定の周期で青⇔赤を繰り返す – 南北方向と東西方向それぞれが青になる時間は あらかじめ定められている • たがいに排他的 … 南北方向が青 ⇔ 東西方向は赤 – 時刻 0 (スタートと同時)に状態変化が起こったと 仮定されている 南北 t=0 東西 南北方向 南北 東西 南北 東西方向 東西 信号待ちの計算 • 信号のところに到達する時間をこの周期で mod を とって場合わけ – 剰余(cur) ＜ 目的の方向が青になる時間(start) • 青になる時間まで待つ : (start – cur) 単位時間待つ必要 – 青になる時間 ≦ 剰余 ＜ 赤になる時間 • ノーウェイトで進むことができる : 0 – 赤になる時間 ≦ 剰余 • 次のラウンドを待つ必要がある : (start + period – cur) • 等号の入る場所を間違えないようにしてください – 特に、次のラウンドを待つ必要があるか否かの判定 • 待ち時間がこの点で不連続になりますので – 問題の読み落としのないように はまるかもしれないところ • 1x1 (単位距離)ずつのマップを作っては× – 最大で一辺 105 くらいの座標範囲になるので、 40GB くらい必要になります ⇒ 明らかに無理ですね • やったチームはいないようでした • このへんの見積もり計算には慣れてください – 道路の途中の点は必要ないので削りましょう • 夏合宿 3 日目の Problem F: Web 0.5 と同様 実際にはまっていたところ • スタートとゴールが同じ通り上にある可能性が あります – これを取り扱えないと Wrong Answer です – 実際にはまっていたチームがあります • スタートとゴールが同一地点の可能性もあります – 上のケースに含まれていますが – 問題文では禁止されていないので ;-) – これもうまく扱えないと Wrong Answer です ⇒ 構造に忠実なグラフをつくるか、特別なケースだけ は判別して処理してしまうかのどちらか まとめ • 中程度の難易度の実装系問題です – 問題文をよく読めば解く方針は見えるでしょう (でもちょっと実装量は多いかもしれません) – はまりどころが何箇所かありますが、それを抜ければ 通ります • どういうケースではまりやすいか、をコンテスト中に考える癖を つけるとよいでしょう • 中盤戦以降の問題数稼ぎには有効かも – 頭で考えるより腕力で解ける問題なんです • 解かないのはもったいないです – 他の問題のアルゴリズムを考えている間にゴリゴリ実装 してしまえばよろしい
© Copyright 2024 ExpyDoc
