蟻本
しゃくとり法 POJ 2566 - Bound Found 問題 要素数nの数列aが与えられる。 各クエリでtが与えられるので、連続する部分列の中で、和の絶対値がtに最も近いものを求めよ。 制約 n ai t クエリの数やデータセットの数の制約は書いてない 解法 しゃくとり法で各…
二分探索（k番目を最小化、その他） POJ 2010 - Moo University - Financial Aid(AC) なんか昔解いてた。 メジアンを決めて、その下からN/2匹、上からN/2匹をコストが最も少なくなるように選んだときF以下になってるかどうかを判定する。 priority_queueなり…
二分探索（平均最大化,k番目の値を検索） 二分探索における現在の区間の中央の値をxと表す。 それにしてもPOJは時間制限キツイなあ。 POJ 2976 - Dropping tests 蟻本通り POJ 3111 - K Best 蟻本通り POJ 3579 - Median 問題 長さNの数列Xiが与えれる。 Xi …
二分探索（最小値の最大化） 二分探索における現在の区間の中央の値をxと表す。 POJ 3258 - River Hopscotch http://poj.org/problem?id=3258 石の位置をソートして答えで二分探索。 幅がx未満になるような場合、その石を除くようにする。 POJ 3273 - Monthl…
繰り返し二乗法
ユークリッドの互除法
素数
最小全域木
Union-Find
プライオリティーキュー
最短路
DP（少し考察を要する問題）
DP(漸化式を工夫して高速化する問題)
DP まだ楽
貪欲法（区間）
全列挙
DFS&BFS
貪欲法（その他） ちょっとしんどくなってきた
区間への加算と和の計算がO(log(n))できるセグメント木が良く分からなかったので、図に書いてみた。 （普通のセグメント木はある要素への加算と和の計算がO(log(n))である。）
