SoundHound Inc. Programming Contest 2018 -Masters Tournament-:D - Saving Snuuk
問題
https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_d
考え方
解は なる 年それぞれについて解を出力する必要がある。各年度それぞれについてダイクストラをするのではTLEになる。
まず からそれぞれの都市への最短距離を求めよう。経路は両替所を とすると となるためである。
最短経路が求められたら、制約の厳しいところから考えていこう。その場合は 年から考えていくことになる。このとき使用できる両替所は の両替所のみである。よって経路は一意に決まって となる。 年の場合は 年の最短経路と の最短距離を比較して小さい値を選択すれば良い。よって 年から考えていくことで各年のコストが で求めることができたので解を求めることができた。
Submission #4148549 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-
どこに着目して考察するべきだったか
条件(制約)の厳しいところから考えていく典型である。
何がバグっていたか
得た知見(典型ポイント)
- 条件の厳しいところから貪欲