脳log[20240122]

2024年01月22日 (月) [AtCoder] 精進。前回の ABC337-G「Tree Inversion」。diff は F 問題より低いことになっているらしい。問題文が読めて理解できてどういう情報を集めればいいかが把握できれば、することはおなじみではある。把握できないし、実装にも時間がかかるんだけど……。さてさて。ある頂点 v を根とする部分木について、v を含むそれぞれの頂点がそれぞれの部分木に含む自身より小さい頂点の数の合計を g(v) とする。特に v が全体の根であり部分木にすべての頂点を含んでいるとき、f(v) と g(v) が等しい。あとは……解けるな？ 頂点 v が０個か１個の親 p と０個以上の子 c を持つなら、最初のステップで g(c) を、次のステップで親子を逆転した木について g(p) を求めたら、v-1 を足して f(v) にする。g(v) を効率良く求めるためには、DFS の行きと帰りで自分より小さい頂点の数の差分を求めることにして、その記録に BIT を使えば累積和の更新が対数時間で済ませられる。■提出 #49587091 (AC / 870 Byte / 913 ms)。実装するのにとくに罠もなく、しかし時間はかかった。ふりかえりつつ、立ち止まって先を考えつつ、じっくり丁寧に書く必要があった。手に対して頭の方が遅れをとっている。それでいて手が書く量も 870 バイトと少なくない。時間がかかります。