脳log[20210705]

2021年07月05日 (月) [AtCoder] 昨日は ABC 208。E 問題は見た瞬間に競プロ典型 90 問の「025 - Digit Product Equation（★7）」が思い浮かんだ。実際それは外れてなかったっぽい。「ABC208 五分で見ました C：典型 033（小数点以下切り上げ） D：あああああ　なんで今出たの E：典型 025 ほぼそのまま（0 がある場合を場合分けすると速そう） F：？？？ / Twitter」 しかし残る 10 分 15 分で書き上げることはできない。自分は D 問題を通すのだ。■最初の提出 #23975406 (TLE×12 / 21時36分)。k と s を固定してプライオリティキューを使ったダイクストラ法の繰り返し。TLE が出てからが本番です。■２番目の提出 #23980117 (TLE×11 / 21時54分) k から k+1 への遷移にダイクストラ法が必要ないことに気がついた。便宜上 k=0 の場合を想定し、すべての s について１回だけダイクストラ法を実行することに。TLE は１つだけ減った。■３番目の提出 #23981771 (TLE×10 / 22時01分) あれ、k=0 の場合にダイクストラ法っていらなくね？と気がついた。プライオリティキューを削除してダイクストラ法はなし。TLE がまた１つ減った。■４番目の提出 #23983424 (TLE×5 / 22時10分) 余分なものがなくなって遷移ループの最適化に専念。例外値をさっさと検出してループをスキップするのが効くのは TSP 問題の経験が教えている。TLE は 5 つまで減った。そして最後まで 5 つから減らなかった>提出 #23993655 (TLE×5)。■perfect_*.txt と名付けられた全 5 ケースが壁になっていたと後で知った。何が perfect なのかを想像すれば、k が増えるたびにガッツリ最短経路の更新が起こる(ループのスキップができない)のではないかと思う。というより、N×(N-1) の辺がある完全相互通行が可能な網の目ネットワークか。どうやって手を抜けばいいんだ？■コンテスト後にワーシャルフロイド法という名前や、これまでは N≦300 の制約で出題されることが多かった(今回は N≦400)という話が聞こえてきた。アルゴリズムの名前が出てきたからって問題が解けるってことはないよね(負け惜しみ)。■「Ruby によるすべての提出」。コンテスト中の AC はゼロだったけど、最初に tompng さんによる 2893 ms の提出が、次に kojix2 さんによる 1083 ms の提出が AC を取っている。不可能ではないなら自分も通せて然るべきなのだ。ネタバレするのはあきらめたとき。■■■@2021-08-19「ARC035-C アットコーダー王国の交通事情」 これもワーシャルフロイド法っぽくて、しかも N≦400。Ruby での AC は現在に至るまでゼロ！ Ruby のバージョンは 1.9 から 2.7 までと幅があるけど、2015 年と同じことが繰り返されているだけだった。