脳log[20210717] AtCoder Beginner Contest 210／E 問題 Ring MST (+D 問題)

最終更新: 2022-01-25T19:28+0900

♪ [AtCoder]AtCoder Beginner Contest 210／E 問題 Ring MST (+D 問題)

A 問題から WA を出して、D 問題も 4 WA のち AC だったけど、D 問題が水 diff だったおかげで４完最遅に近かったはずでもそこそこのパフォーマンスがもらえた。棚ぼた。E 問題が解けなかった。

 提出 #24322478 (RE×11 / AC×19)

30 分考えて出したコンテスト中唯一の提出。ソースを見ればわかるけど、３分岐のうち２つしか埋まっていない未完成の状態。未実装部分に 1/0 (ZeroDivisionError) を埋めておくことでジャッジ結果を AC/WA の２択ではなく AC/WA/RE の３択にするテクニック。WA がなかったということで、中身のある２分岐にミスはなさそう。

 提出 #24337207 (AC / 273 ms)

複数の A 要素の関係について、中国剰余定理が関係してくる気がしてお手上げだと思っていたのだけど、GCD で良かったらしい。まだ理解していない。

 D 問題 National Railway

DP です。１行目から行ごとに考える。

1. ある行について。処理済みの地点に建てた駅からこの行この列に至る最小のコストを記録することにする。
2. その次の行にて。各列 Aij の費用を払って駅を建てたとする。前の行の j 列に記録されたコスト(の先にある地点)をもうひとつの駅として、建設費用を計算する。
3. 建設費用の最小値が答え。

罠があるとすれば、同じ行から２つの駅を選ぶ場合を見落とさないこと。見落とさないこと。慌てて対応をミスって WA を重ねないこと。

 提出 #24314328 (AC / 559 ms)

m1 が同じ行内からもう１駅を選んだ場合の建設費用。m2 が前の行の同じ列から下に線路を引いてきたときの建設費用。

その他の処理は「この行この列に至る最小のコスト」を記録するためのもの。上の行から引っぱってきた線路を延長するのがいいか、Aij を払ってその場に駅を建てるのがいいか、同じ行の左右から線路を引いてくるのがいいか、最小費用を記録する。

ところでこの問題、「鉄道建設にかかる費用として考えられる最小値を出力してください。」で問題文が締められているのだけど、２、３回読み直したよね。え？ どのような鉄道を敷けばいいのか示されてましたか。まさか「高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています」が真実その通りで、1000000 マスのうち最低でたったの 2 マスをカバーする鉄道を敷設するだけでお茶を濁すつもりだなんて、一読しただけでは飲み込めなかった。高橋王国民甘すぎ。