最終更新: 2022-01-25T19:28+0900
A 問題から WA を出して、D 問題も 4 WA のち AC だったけど、D 問題が水 diff だったおかげで4完最遅に近かったはずでもそこそこのパフォーマンスがもらえた。棚ぼた。E 問題が解けなかった。
30 分考えて出したコンテスト中唯一の提出。ソースを見ればわかるけど、3分岐のうち2つしか埋まっていない未完成の状態。未実装部分に 1/0 (ZeroDivisionError) を埋めておくことでジャッジ結果を AC/WA の2択ではなく AC/WA/RE の3択にするテクニック。WA がなかったということで、中身のある2分岐にミスはなさそう。
複数の A 要素の関係について、中国剰余定理が関係してくる気がしてお手上げだと思っていたのだけど、GCD で良かったらしい。まだ理解していない。
DP です。1行目から行ごとに考える。
罠があるとすれば、同じ行から2つの駅を選ぶ場合を見落とさないこと。見落とさないこと。慌てて対応をミスって WA を重ねないこと。
m1 が同じ行内からもう1駅を選んだ場合の建設費用。m2 が前の行の同じ列から下に線路を引いてきたときの建設費用。
その他の処理は「この行この列に至る最小のコスト」を記録するためのもの。上の行から引っぱってきた線路を延長するのがいいか、Aij を払ってその場に駅を建てるのがいいか、同じ行の左右から線路を引いてくるのがいいか、最小費用を記録する。
ところでこの問題、「鉄道建設にかかる費用として考えられる最小値を出力してください。
」で問題文が締められているのだけど、2、3回読み直したよね。え? どのような鉄道を敷けばいいのか示されてましたか。まさか「高橋君は国民の利便性を上げることよりも、鉄道建設にかかる費用を少なく抑えることを優先したいと考えています
」が真実その通りで、1000000 マスのうち最低でたったの 2 マスをカバーする鉄道を敷設するだけでお茶を濁すつもりだなんて、一読しただけでは飲み込めなかった。高橋王国民甘すぎ。