keyword 有向グラフ 強連結成分分解 C++ 概要 ノード数V( なにはともあれ強連結成分分解してDAGに落とす。落とした上で、(1)はDAGのsourceの個数であり、(2)はそのDAGを一つの強連結成分にするのに必要な辺の最小化、とそれぞれ読み替える。(1)は簡単。(2)は…

keyword 無向グラフ 関節点 BruteForce C++ 概要 ノード数V( ノード数が少ないので全てのノードを取り除いて試す。計算量O(V*E)。

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ではランクを使わず経…

keyword 最大流 C++ 概要 豚小屋がM( 最大流を流して解く。まず、ソースからM個のノードに流量x_iの辺を張る。またnext[i] = iと初期化する。次に、1日目に来る客から順次辺とノードを追加していく。持っている鍵に対して、S = {next[key]}を求め、next[key]…

keyword C 概要 ヨーグルトをN( j週目C_jとmin_{i

keyword 2部グラフ 最小点カバー C++ 概要 蟻本を参考にして解いた。2部グラフでは|最小点カバー|=|最大マッチング|なので2部マッチングする。ソース略。

keyword 集合 C++ 概要 要素が[1..T](T 要素が小さいのでどうとでもなる。多分setに突っ込んでset >に突っ込むのでも余裕で間に合う(これだと計算量O(T^2*log T * P * log(P))。setは定数が重いのでvectorでuniqueとか使って定数分早くした。多分union-find…

keyword 平方分割 概要 蟻本を参考にして解いた。2分探索の範囲が広かったり、分割の数が適切でなかったりしてTLEを何度も出した。分割の数を2の巾にして割り算や余りの計算をビット演算に書き直したら通った。ソース略。

keyword C 概要 入力はa+b=cの形で与えられる。a,b,cは7桁以下の10進数。rev(a) + rev(b) = rev(c)であるかどうか判定する問題。 やるだけ、としか。

keyword 幅優先探索 C++ 概要 2次元平面の原点に少女がいる。少女は第一象限を1秒に1マス動ける(4近傍のいずれか)。隕石がM( 幅優先するだけ。ただし安全地帯は[0..302]*[0..302]の中から探さないといけないことに注意。何故か[0..301]*[0..301]でも通った。…

keyword 行列 C 概要 サイズN*N (N 各行の階差数列が等しくなるかどうか判定すれば良い。なぜなら、a[i][k+1] - a[i][k] != a[j][k+1] - a[j][k]ならa[i][k] + a[j][k+1] != a[i][k+1] + a[j][k]だからこの部分を入れ換えればよいから。計算量O(N^2)でこれ以…

keyword 2部グラフ 最大独立点集合 C++ 概要 頂点数V( 色々調べてみると、V-|最大マッチング|になるらしい。計算量O(V*E)。

keyword 整数 C++ 概要 10進数で考える。4桁の整数に対して、それを並び替えてできる最大の数と最小の数(leading 0もOK)の差を引くことを繰り返すと6174か0に落ちることが知られている。それをシミュレートする問題。 やるだけ、としか。あと問題文が色々不…

keyword 最小パス被覆 C++ 概要 ノード数N( 模擬地区予選で類題が出た問題。DAGの最小パス被覆は(u,v)に対してu->v'となるような2部グラフの最大マッチングを頂点数から引けば良い。

keyword 最小重み2部マッチング C++ 概要 N( 見たまま最小重み2部マッチング。計算量O(N^2 log N)。ソース略。

keyword 空間幾何 C 概要 空間状に星がN( 何の工夫もなく角度を求めるだけ。計算量O(N*M)。あとPKUでGCCを選んだときは-lmがついていることも確認できた。

keyword 平面幾何 C++ 概要 頂点数N( 凸多角形の切断を繰り返す。計算量O(N^2)。

keyword 行列 C 概要 行列A,B,Cが与えられる。(N A*B = Cであるかどうか判定する問題。間違っている場合はどの要素が間違えているか出力する。 メモリの局所性に気をつけてO(N^3)で計算する。普通ならこのオーダーはアウトだけど計算は単純だしメモリも連続…

keyword BruteForce C 概要 長さN( Nが小さいので全探索する。パターンが2^N、部分和の計算がNなので全体の計算量はO(2^N * N)。半分全列挙を用いるとO(2^(N/2) * N)に落とせる(2^(N/2) * log(2^(N/2))。

keyword 探索 C++ 概要 nに対するaddition chainとは次を満たす数列である。a_0 = 1, a_m = n, a_0 問題文中に探索しろって書いてあったから探索した。答えが小さいので実際は埋め込みした。以下のソースは埋め込み用に使ったもの。計算量は謎。

keyword 数列 2分探索 C++ 概要 長さN( A[i]をコピーしてソートし、A[i]が上位Kに入っているかどうかは2分探索で判定すれば良い。時間計算量O(N * log N)、空間計算量O(N)。

keyword 整数 素因数分解 C++ 概要 正整数Xに対してX-factor chainを1=x_0 素因数分解したときの指数だけが問題になる。指数の部分を1ずつ増やしていけば良いので最大値は指数の和。組み合わせの数は多項定理のアレ。計算量は素因数分解のO(√X)。