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))。