脳log[20220313]

2022年03月13日 (日) [AtCoder] 昨日あった ABC243。特に書くことはないかな。E 問題までノータイムで実装に取りかかれたけど結果は ABCD の４完。E 問題は？ 300 の３乗のワーシャルフロイド法が無しだと思って迷走して TLE で終わってしまった。■E 問題>提出 #30084536 (AC / 1281 ms)。辺のコストが２点間距離より大きい場合と、等しいけど代替経路がある場合に取り除ける。代替経路は中継地点の存在によって見つかる。あとから中継地点を探索しても計算量は変わらないけど、ワーシャルフロイド法のついでにメモしておくとちょっとは速いかな、と思いました。その他にはスタート地点までの距離を 0 にしないで初期値のままにしておくと中継地点の探索が楽になるとか(中継地点が端点のどちらかと一致する場合を除外しないで済む)、初期値を無限大ではなく nil にしておいて nil を検出したらループをさっさと抜けるとか、そういう小手先 Tips。実装量からいっても水 diff 下位だと思ったけどギリギリ青 diff だったもよう。意外。■次のステップはこういう回で F 問題に時間を残して通せないと来ないんだよ。今回の F 問題は解答の提出フォーマットがすでに謎なんだけども。■■■E 問題。「Numo::NArray でワーシャル–フロイド法の多重ループを記述削減 - Qiita」■E 問題の考察がノータイムだったのって 第七回 PAST の K 問題「急ぎ旅」を解いていたからかもしれない>20210721p01.11。最短経路はどの２点間を取り出しても最短だし、最短経路同士はどの２本も分岐と合流を繰り返しながら平行して走っているってやつ。