atcoder.jp
＜ずる＞
O((HW)**2)とは分かったものの一個だけTLEが取れない。全部道である場合のみ特例で除外したら通ったけどこれPythonの正攻法はなんなんやろね。
atcoder.jp
＜解説AC＞
ロボットアームの動ける範囲の右端でソート→右端が小さい方から順番に、次のアームの左端が範囲に引っかかってたら入れない、大丈夫なら入れる、を繰り返す。右端を常に更新して管理しておくこと。
atcoder.jp
＜凡ミス＞
発想はあってたのに計算順序をミスったらWAが取れず1時間溶けた。たかが掛け算・割り算の順序と侮ってはいけない。次からはこういうことがないようにする。
atcoder.jp
＜解説AC＞
問題文の意味が理解できなかった。最初に与えられているのは「全点間の最小距離」である。
一回ワーシャルフロイドっぽいことをしてみて、与えられた全点間の距離のデータより小さくなってしまう（三角不等式において、a+b < cとなってしまうような状況。ここでa,b,cは全て「最短距離」であるはずなので、a+bがc未満になってしまうと都合が悪い）ケースが出てきてしまったら、その時点で調査を打ち切る。
a+b == cとなるケースにおいては、迂回した場合と直接向かった場合の距離が等しい→直接向かうような辺は削除してもオッケー（というか削除するべきで、なぜなら迂回した方が回れる点が多いので）なので削除。
ここで気をつけるべきは、一回削除したら「迂回するケース」の探索を打ち切ること。なぜなら、探索を続けてもう一つでもa+b == cとなるケースが出てきてしまった場合、削除すると決めた辺をもう一度消す事になってしまうから。
