AtCoder ABC020-022[C] - samayotta.show()

今日の分は大変ハードで苦しい時間だった。

[WA解答]

回答状況はこんな感じ。

http://abc020.contest.atcoder.jp/submissions/1405662　何かコーナーケースに引っかかっているようなんですが、どういうケースに撃墜されるのかわからない。もう日を置かないと原因を発見できなそう。

ハイパーパラメータっぽいものを二分探索して解く。

一言コメント：簡単そうに見えて二部構成の問題。まず第一部はワーシャルフロイドによる全点についての最短距離。第二部は得られた最短距離行列を用いての一次元動的計画法。理解のため特に第二部については長くコメントを書いた。

一言コメント：まず頑張ってpythonでDFSを書き、それでうまくいかなかったのに反省してwfを書き、それがTLEしたのでC++という紆余曲折。ACまでがすごく遠い。付け加えると、型はlong longでないと最後のテストケースで落とされます。

今日は本当につらかった。何事も始めたばかりがいちばんつらいものだけれども、それにしたってつらい。人権がない。