sumf 変数をこの式にしたい。最初の提出の時点で考えなかったことはないけど、全然まとまらないねってそのときは思った。HI/LO を入れ替えた２つの和を左からと右からでまとめてるっぽい？■D 問題「XOR Tree Path」。最初はビット列を掛け合わせて寄せていく解法(名前がわからん)かと思ったけどだんだん木 DP が見えてきた。葉ノードから寄せて上げていく。記録するのは、反転操作を親に伝播させるときに部分木がいくつの黒ノードを含むかと、そうでないときにいくつの黒ノードを含むか。木 DP の肝は子ノードのマージ部分だけど、ここに罠があった。子ノードが１つしかないときに「反転操作を親に伝播させるときに部分木がいくつの黒ノードを含むか」という数字を反転しない場合の数字に反映させる方法はない。反転操作を打ち消し合う他の子ノードが存在しないから。提出 #36339752 (AC / 602 Byte / 286 ms)。■E 問題「Name Value」。制約が、特に A,B 文字列の長さがやばすぎるだろうと思ったけど、クエリ文字列のスキャンが前方/後方から貪欲に行えるので、それを効率的にやるために準備を頑張ればいい。文字種×(A,B 文字列の長さ) = 2000 万要素くらいの遷移表を用意して許されるのか考えたよね。うーん、ありかなあ。でも１要素ずつスクリプトでコピーするとダメかも。提出 #36341147 (AC / 509 Byte / 1309 ms)。許された。最初は遷移表に添字を記録していたけど、遷移先の遷移表を持たせるのがより直接的ではないかと気がついてそのようにした。人間が脳みそに余計なステップを持っているとコンピュータにも無駄な回り道をさせがち。こういう無駄を詰める思考はコードゴルフと通じている。提出 #36348178 (AC / 392 Byte / 1216 ms)。Array#dup メソッドの呼び出しを省いた(20201207)のと遷移表のサイズを半分にしたのと無駄な Array#min を省いたのと添字を記録していたなごりの無駄な変数を省いた。遷移表のサイズを半減した引き替えに整数の引き算がループの中に４回出現している。メモリ大量確保＆コピーとちょっとした整数演算ではどちらが時間を食うかという判断。平均的に速くなったけど重いケースではそれほど変わらず。１度に１要素しか更新しない遷移表を毎回丸々コピーするのがもったいないんだよなあ。空間がではなく時間が。でもたぶんそれをやめると探索が必要になって log が付くのでは？ インチキみたいなうまい方法があればなあ。遷移表の行と列を入れ替えるみたいな方法はたぶんうまくないんだよなあ。２要素の遷移表……。■F 問題からは解けません。■G 問題「Count Arithmetic Progression」を考えてる。傾きに注目するにしても直線の切片に注目するにしても 10 の 12 乗以下という制約がネックになって部分点しか得られない(答えが違えば部分点ももらえないが)。注目するなら 30 万以下の要素しかない L,R 整数列になるのかなあ。それで解く方法が見えないけども。@2022-11-11 部分点をもらいました>提出 #36390042。部分点の制約でも青 diff は下らないと思うなあ。探索できる要素ってある？ １ずつ計算せずに済むような単純な比例関係があったりする？ どっちも(見つから)ないんだよなあ。DL,DU 変数を賢いデータ構造で仮想化して妥当な計算量で求められるとしたらどう？ DU,DL 変数は傾きの上限下限だから傾きを制約する数字が連続的に変化していったら結局 10 の 12 乗に比例したステップが生じると思う。まとめてひと束で計算できる状態の単位が見えない。数列の要素数に比例したステップしか生じなかったりする？ じゃあ傾き制約の変化点を順に知る方法は。■@2022-11-16 解説を読んだ。Convex Hull Trick の名前を知った。「Convex Hull Trickを知っていますか？僕は知っています。 - Qiita」「傾きの単調性が要らない Convex Hull Trick - kazuma8128’s blog」 読んだ。直線をソートして順番に交点を求めて上限/下限の変化が知れるらしい。蟻本で既出だったことも知った(初版 286 ページ K-Anonymous Sequence)。しかし書けない。