脳log[20220523]

2022年05月23日 (月) [AtCoder] 精進。ARC045-C「エックスオア多橋君」(ギリギリ黄 diff)。一読して全方位(？)木 DP だと思った。提出 #31922668 (AC / 555 Byte / 626 ms)。20211014 で解いた第八回 PAST の H 問題「最短経路」と同じ解答の形。■Ruby での提出一覧を見ると一番速いのが 392 ms のこちら>提出 #2757184。仮に頂点 1 に値 0 を割り振って、その他の頂点の値が何になるかを求めている。それから XOR が X になる値の組を数えている。頂点 1 からのパスによって決まる値だけを考えて答えを出していい理由は、たぶん LCA までのパスが相殺されるからとか？ 最後から２行目の ans -= N if X == 0 がはまりやすい罠に見える。X がゼロの時、同一頂点をペアにして数えてしまうのを除外している。もしやと思って直前の WA 提出 #2757181 を調べてみるとこれが抜けていたのが原因だった。WA から３分半で気がつくかあ。無理だよ。他に Ruby で解いている人はゴルファーが一人いるだけ。古い問題なのもあるだろうけど、一見して面倒くさく見えるのも影響してそう。■ブログ記事を７つ読んだけどどれも LCA で相殺を利用していた。考える前に手を動かしている脳筋はいないのか、脳筋は。