keyword 最長増加部分列 C++ 概要 最長(広義)減少部分列を求める問題。 数列の長さが与えられなかったり、出力形式が不親切だったり(答えが1でも複数形とか)でよくない印象しかない。計算量O(N*log N)。狭義と広義ではlower_boundとupper_boundを入れ換えた…

keyword Greedy C 概要 少女はM( 左から順に帰るときのコストも含めて距離を伸ばしていく。つまり上りと下りに区別はない。計算量O(T)。

keyword 幅優先探索 C++ 概要 5*5の迷路が与えられる。スタートからゴールまでの最短経路を出力する問題。 息抜き問題。

keyword 区間 Greedy C++ 概要 [0..10^9]の互いに素な区間がN(区間でカバーしたい。必要な区間の最小値を求める問題。 左から貪欲に置いていく。割り算とか掛け算で多少計算を省く必要がある。計算量O(N)。

keyword 動的計画法 C 概要 1,2,3が並んだ長さN( 分かりやすいDP。減少と増加は別々に考える。dp[i項目][i-1項目の数値]とすれば全状態数は3*Nしかない。また状態遷移は1->2, 2->3だけでなく1->3があることにも注意。

keyword 平面幾何 平面走査法 C++ 概要 2次元平面上に点がN( 例に漏れず平面走査法。イメージとしてはx軸上で円を左から右にずらしていく感じ。計算量O(N*log N)。

keyword 2部マッチング 概要 ただの2部マッチング。ソース略。

keyword 幅優先探索 概要 PKU3414 Potsと同じ問題。ソース略。

keyword union-find C 概要 1~N(=30000)の番号が付いた立方体がある。このとき、P( 集合のマージがメインなのでunion-findを使う。集合の個数と、ルートまでの長さを覚えておけばよい。詳細はソース参照。ちなみに自分の場合union-findではランクを使わず経…