脳log[20230619]

2023年06月19日 (月) [AtCoder] 精進。ABC236-G「Good Vertices」(ぎりぎり橙 diff。この色は前２問の EF ががっつり青 diff だった影響が大いにあると思う)。５日前(20230614)に解いた問題の類題だとのツイートを読んだ>「サーバル「実は「行列の掛け算っぽい計算」さえできれば行列累乗できるから、数え上げ以外の問題でも行列累乗を使うことはあるけど、こっちはかなり難しいね。ABC236Gが例題だよ」 https://t.co/8OvqVZpuLz」。100×100 の行列を 10^9 乗するので３千万の計算量。これを辺を１本１本追加しながら N^2(≦１万)回繰り返すともちろん TLE になる。どうしよう(※)。今回は場合の数を数えるのが目的ではないから、行列の中身に使用した辺が追加された時刻 t の最大値を記録すればいいと思った。(※「どうしよう」この一語にはコンテストが終了してしまうくらいの時間が詰まっている。ときどき思い出しては頭の中で転がしていた)■提出 #42752849 (TLE×52/AC×58)。今回も行列の掛け算を書き間違えたのでこの前の提出を見ながらまねして書いた。そして TLE。ローカルではほぼ９秒以内に完了しているので、ジャッジサーバーでは約半分の 4.5 秒かかる見込み。制限時間は特に長めではない２秒。Ruby でうん千万のオーダーは厳しいよう。■提出 #42753403 (AC / 1995 ms)。.zip().filter_map{}.min を .zip(){} での逐次処理に書き換えたらローカルで５秒になったので提出したら AC だった。案外いけるもんだ。