脳log[20250914]

2025年09月14日 (日) [AtCoder] 精進。今日あった ABC423-E「Sum of Subarrays」。累積和３つと累積和の累積和１つで解いたけど、絶対何か無駄な回り道をしてると思うんだよね。提出 #69368469 (AC / 1424 Byte / 662 ms)。■いろんな累積和という意味で印象に残ってるのは ABC338-G「evall」。たぶん言及するのはこれで３回目。E 問題を累積和でやると決めてから、求めるものがストレートには得られないので区間の始点と終点を分類し包除を考え累積和を組み合わせ１時間以上のあいだに何度も頭を抱えたことをふまえると、G 問題の方が難しかったとは言えない。ただ、適切な道具を適切に組み合わせればすっきり解けるのではないか、無駄にこねくりまわして自分で問題を複雑にしているのではないかという懸念はある。■どうやら累積和が３つで解けるみたい？■■■F 問題「Loud Cicada」。累積和と累積和の逆という説明と図がわかりやすいこちらのツイート「フェネック「このメビウス変換っていうのはゼータ変換の逆のことで、ゼータ変換っていうのは累積和をとることだねー。例えばセミ1,2,3がいたとき「少なくともセミ1,2が発生」は「1,2が発生＋1,2,3が発生」っていう"累積和"をとった状態だから、それを戻してるよ」」を参考にして書いたものはサンプルが合うものの N=20 の最大ケースで数分かかってしまった。累積和の逆を計算するときに各要素ごとに添字の補集合の部分集合を列挙しているのが良くないのだと思う。うまい計算手順があるのだろうか(ゼータ変換、メビウス変換について調べない)。■E 問題。累積和３つがどのようにして導かれるか。「アライグマ「求めたいのはΣ(A[x]×(x-Li+1)×(Ri-x+1))だから、xxA[x],xA[x],A[x]の累積和を求めておけばO(1)で計算できるのだ！ この問題に1点変更クエリもありにしたのがだいたいABC256Fと同じなのだ！」」 おかしいな、簡単な問題に見えるぞ。