競プロ忘年会 in 東京 2016 で発表したpalindromic tree(eertree, 回文木) についてのスライドとコードを載せておきます。 Palindromic tree from __math www.slideshare.net gist.github.com

追記3: yosupoが最新版の解説を書いたようです。こちらを見ましょう。 yosupo.hatenablog.com 以下は旧記事です。 AtCoder Regular Contest 059 で出題された F - バイナリハック / Unhappy Hacking の O(n)解法です。 解説はコードに埋め込みました。 カタ…

目次 動機 問題概要 準備 計算量 \(1 \le p_b \le n^{1/4} \) の時 \(n^{1/4} \le p_b \le n^{1/2} \) の時 素直なプログラム 最適化したプログラム 余談 動機 Project Euler で、n以下の素数の合計を求める問題がありました。 Problem 10 - Project Euler …