7K12 blog

猫でも分かるアルゴリズム解説

SoundHound Inc. Programming Contest 2018 D - Saving Snuuk

f:id:tkr987:20210913023852p:plain

  • 選択肢の少ない状態から考察すると楽
  • 後ろから考えると値を流用できる

f:id:tkr987:20210913024915p:plain
https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/25168114
0日目から考えると全ての都市で両替できるので最善を考えるのが大変だが n-1 日目なら選択肢は1通りしかない。 n-1 日目の経路は両替する頂点をvとすると s -> v(n) -> t であり n-2 日目は s -> v(n) -> t か s -> v(n-1) -> t の2通りしかなくてminを採用すれば良い。 円での支払いは s からのダイクストラ法、スヌークでの支払いは t からのダイクストラ法を前処理しておけば O(1) で求まる。以下 0 日目まで同様に更新していくことで全ての答えが  O(n) で得られる。ボトルネックは n-1 日目のダイクストラ法で  O((n+m) \log n)

感想: 珍しく青色を自力ACできた