SoundHound Inc. Programming Contest 2018 -Masters Tournament- Virtual
目次をつけてみた
-
結果
A, B, D の３完（41:31）、予想順位 1838 位中 367 位、予想パフォーマンス 1722。C 問題の解法が分からなかった。
-
A - F
-
問題
-
解法
やるだけ
-
解答
Submission #2828976 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-
-
B - Acrostic
-
問題
-
解法
やるだけ
-
解答
Submission #2828979 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-
-
D - Saving Snuuk
-
問題
N 個の都市と M 本の電車があり、それぞれの電車は２都市間を両方向に結んでいて、２つの通貨ごとにコストが決まっている。都市 S から T まで移動する際に途中１回持っている円を「スヌーク」に両替したい。両替できる都市は年数が経つごとに減っていく。最初 10^15 円持っているとき、各年数ごとに都市 T まで移動したときの残り「スヌーク」の最大値を求める問題。
-
解法
まず 10^15 円で十分足りる（全ての辺を通っても 10^14 円）。ある頂点までは円、ある頂点からは「スヌーク」で移動したいので、コストの単位が円のグラフと「スヌーク」のグラフの２つをつくる。それぞれ、頂点 S と T からダイクストラをして最短経路を求めて置く。そうすれば、両替する頂点を全通り試し、その頂点ごとにコストはどれだけかかるかを前計算しておく。後は、そのデータを std::priority_queue に入れておくなどして各年数ごとに使える両替できる頂点の中で答えを出せばよい。実装ミスをし 1WA してしまった。
-
解答
Submission #2829242 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-
