tooh’s diary

半角全角、常体敬体が入り乱れるカオス

復習2/6,2/7

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となるケースが出てきてしまった場合、削除すると決めた辺をもう一度消す事になってしまうから。