ABC241ばちゃ, 6完（調子いい）, もし出ていたら286位(Perf 2014). どれも全体的に実装が重いなぁと思った. 比較的簡単に解けたF問題が上位青Diffなのに驚いた. しかし今見返すとそれほど簡単なわけではない.
ARC136, 2完 607位, Perf 1737 (-4). B問題がすぐに解けたのは良かったが, D問題が解けなかったのは実力不足だった.
D問題は, 累積和が高速ゼータ変換的な操作で動かせることに気付かなかった. 余計にかかる解法を書こうとしていた.
Dの解説で高速ゼータ変換と言っていたので, 少し読んでみた. ゼータ変換は累積和に対応する操作で, メビウス変換は階差に対応する操作らしい. ゼータ変換, メビウス変換は任意の半順序関係（xがyの倍数を示すy|xも！）に適応できて, だから実は約数系包除と呼ばれるテクニックは本質的にメビウス変換をしていたことになる.（本当か？）
累積和は2次元だとだったが, これでは時間がかかってしまう(全てのサイズを
として,
). そこで次元ごとに分けて動的計画法で累積和を取ることで, より高次元でも簡単に計算できる. たとえば, 2次元だと縦に累積和を取ったあと, 今度は横に累積和を取ることで次元を
として
で計算できる.
明日からもこの話題について勉強する. 典型030は昔悩んだ末に何も分からなかったが, 今日問題を見て数分で解けてしまった. その問題もこれに関連する.
さて, 典型015に知らないアルゴリズムがでた. 強連結成分分解といい, 一番いい感じの強連結（任意の2頂点が行き来可能）を頂点, 辺
として
で求めてくれるらしい. これはトポロジカルソートのいいところを使っていて, 素晴らしいと思った. そういえば, トポロジカルソートも半順序関係だよね.
