優先度付きキューを用いてダイクストラ法によってたこ焼きを効率よく投げる ARC008 C - THE☆たこ焼き祭り2012
問題
C: THE☆たこ焼き祭り2012 - AtCoder Regular Contest 008 | AtCoder
解法
以下のステップで解くことができる。
- ダイクストラ法を用いて始点から各点までの最短時間を算出
- 始点から離れている点からたこ焼きを配る
- たこ焼きを受け取った時間が最も遅かった物を出力
それぞれ見ていく。
ダイクストラ法を用いて始点から各点までの最短時間を算出
各点間の「たこ焼きを投げるスピード」と「距離」が入力値により分るので、これらからある点からある点へたこ焼きを投げる時の時間が分る。これをグラフの辺の「重み」としてダイクストラ法を用いる。
ここで、問題文の
たこ焼きを投げてから 1 秒間は次のたこ焼きを投げることができません。
を考える。この問題の制約では、ある点が同時刻に２つ以上のたこ焼きを持つことはない。これは、始点からたこ焼きを投げる際に、１秒ずらして投げるためだ。
ダイクストラ法は最短経路を求める。そのため同時にたこ焼きを投げた場合、ある中継点では同時刻に複数のたこ焼きを受け取る場合がある。しかし、たこ焼きを１秒ずつずらして投げた場合は、その中継点では同時刻で受け取るはずであった複数のたこ焼きは１秒ずつづれて到着する。よって同時刻に２つ以上たこ焼きをもつ点は存在しない。
始点から離れている点からたこ焼きを配る
ダイクストラ法によって始点から各点までたこ焼きを投げた場合の最短時間を算出できたので、始点から離れている(時間的に)点からたこ焼きを配るようにする。今回の問題ではダイクストラ法を用いてる際に「時間」によって重み付けを行った。また、たこ焼きを投げる制約も１秒毎という「時間」のみの制約になる。よって最も時間的に離れている点から配ることで最も効率良くたこ焼きを配る事ができる。
計算量
優先度付きキューを用いてダイクストラ法の計算量は大体O(Nlog N)である。Nの最大値は103なので間に合う。
