脳log[20220621]

2022年06月21日 (火) [AtCoder] 精進。ABC187-E「Through Path」(水 diff)。コンテスト当日に 25 分で D まで解いていながら残り 75 分で解けなかった問題。翌日のふりかえり>20210103p01。「全然ループの軸が見えなかった」と書いてあるが、以前も今日(の最初)も問題の形式に引っぱられて辺を中心としたループしか考えられていなかった。考えるのは頂点について。■仮に定めた木の根によって決まる親子関係とクエリの種類(t)によって、クエリは、a か b を根とする部分木に x を加算するか、部分木以外に x を加算すると理解される。部分木に加算するのはオイラーツアーと累積和の組み合わせでいけるし、部分木以外に加算するには全体に x を加算してから部分木を対象に -x を足せばいい。■提出 #32649747 (AC / 577 Byte / 832 ms)。以前の日記に「筆塗りを思い出した」とも書いてあるから当時からオイラーツアーは知っていた。硬直した視点が解けなかった唯一の理由。■解説を読めばオイラーツアーはいらなかった。それはクエリを処理しながら質問にも答えたいときに BIT を使って累積和の構築を高速化する方法。解説の最後に「また、各クエリで辺 e 以外では cai​​−cbi​​ の値が変わらないことに注目し、c1​ と cai​​−cbi​​ の値を管理しても同様に解くことができます」とも書いてあるけど、えっと、よくわかりません。■■■木の全体を変化量(差分)の連鎖として見る。頂点の値は変化量の累積。変化量の累積は相対値なので木全体の値を一意に定めるアンカー(初項)として c1 に代表させる。根っこの値を代表値にすると都合がいいのは、親子関係で辺の向きが判別できるから。■提出 #32651136 (AC / 408 Byte / 958 ms)。時間もメモリ使用量もさっきの提出に劣ってるのが納得いかない。いやまあ、判断と計算を先送りしたせいでややこしくて、判断と計算の材料を蓄えるために余計なメモリを使ったんだろうなあとはわかる。報いがない。でも先送りせんと辺に注目してるのか頂点に注目してるのかわからんようになるのでしかたなかった。解説の最後の１行ってこういうことだと思ったんだけど違うかな。