Competitive Programming Advent Calendar Div2013の12月2日の分です。ときどき脱線しながらも主にsegment treeの再帰展開について書こうと思います。 はじめに segment treeの資料といえば蟻本やiwiさんのスライドが非常に分かりやすくお勧めです（定番中の…

様々な問題をLPやその双対を駆使して解きまくっているwataさんが格好良すぎるので、ちょっといくつかの最小カットの問題を解き直してみた。 私はLPにも最大流にも詳しくないので、完全ユニモジュラとか言われても「成り立ってることを祈りましょう」くらいし…

初項1、公比r、項数nの等比級数1+r+r^2+...+r^(n-1)を効率的に求めたい。 何も工夫せずにやると def f(r,n): ans = 0 b = 1 for i in xrange(n): ans += b b *= r return ans でO(n)となる。 よく知られている公式を用いると次のようにも書ける。 def f(r,n)…

ちょっと考えたことをまとめてみました。どちらのアルゴリズムも区間を扱うものですが、例によって私の好みで半開区間を主に扱います。 二分探索とは何か 自分なりにまとめると、「ある点を境界に真偽が入れ替わるとき、その境界を効率的に求めるアルゴリズ…

私はしゃくとり法を書くのが苦手です。なので、しゃくとり法について自分なりに考えてみました。 しゃくとり法って結局何？ 二分探索は「ある点を基準に真偽が入れ替わるとき、その基準となる点を見つけるアルゴリズム」と説明できるし、座標圧縮は「何かの…

ここを読んで勉強した。 コメント読むとKMPと等価とか書かれているけどよく分からない。とりあえずパターンマッチングのO(M+N)が使えるのは良い。 原理の解説も元記事にあるけど、とりあえず入力とパターンマッチングへの応用法だけ書いておく。 長さLの文字…