脳log[20220726]

2022年07月26日 (火) [AtCoder] 精進。ABC212-E「Safety Journey」(水 diff)。TLE 解は以前からできていた。N と M と K の上限が 5000 のときに O(K(N+M)) は Ruby にはたいへん厳しい。しかし不可能ではないみたいで、Ruby によるすべての提出を見ると AC が３つある。１つは numo/narray を使うもので、２つはループ展開した文字列を eval するもの。そんなテクニック初めて見たよ！ 横目でちらちら見ながらまねしてみたけど、なんでか同等の速度は出なかった。繊細なのね。■提出 #33540024 (AC / 1981 ms)。まねできなかったからこれは正統派のコード。原型は以前からあった。ポイントは K のループがおよそ K/2 回というところ。定数倍２分の１。コードテストで実験して確かめたんだけど、13,14 行目を多重代入にして１行にまとめると 10 ms ほど制限時間をオーバーする。d1.values_at(*vs).sum が vs.sum{|v| d1[v] } だともっとオーバーする。頂点ごとにまとめた辺(E)の代わりに辺の集合(UV)をそのまま使うと制限時間を数倍オーバーする。色々な積み重ねの上できわっきわの AC なんだ。