http://poj.org/problem?id=2229 方針 nが偶数の時 f(n) = f(n/2) + f(n-2) nが奇数の時 f(n) = f(n-1) となるため、小さい方から順に求めてやる ソース

http://poj.org/problem?id=3199 方針 求める答えはn^dになる。 頑張って多倍長演算する。 ソース 長いので略

http://poj.org/problem?id=2299 概要 バブルソートする際にswapする回数を求める。 数列の長さが500000以下なので、実際にバブルソートすると間に合わない。 マージソートを行いながら、この数をもとめることが可能で数列の逆転数は、左半分の逆転数、右半…

http://poj.org/problem?id=3272 概要 DAGが与えられる。 初期地点が入ってくる辺のない点、最終地点が一番番号の大きな点となるようなパスをすべて考えて そのようなパスにもっとも多く入っている辺は、いくつのパスに含まれるか求める問題。 方針 ある点か…

http://poj.org/problem?id=3543 概要 黒のタイルと白のタイルが与えられるので、それらを使って作ることのできる 市松模様の正方形の最大サイズを求める。 方針 正方形のサイズ = lに対して lが偶数 -> w >= l^2/2 && b >= l^2/2が必要lが奇数 -> min(b,w) …

http://poj.org/problem?id=2257 ほうしん 結局各個人の払うor払ってもらう金額のつじつまさえ合えばいいので、 各個人についていくら払うor払ってもらうかを計算してから 支払いができるところから順に払っていってやればよい。 ソース #include<iostream> #include<string> #</string></iostream>…

http://poj.org/problem?id=2531 ほうしん グラフの最大カットを求める。 最大カットを求める問題は、NP完全問題らしい 状態数2^20を全探索した ソース #include<iostream> using namespace std; #define REP(i,a,b) for(i=a; i</iostream>

http://poj.org/problem?id=2259 概要 すでに同じチームの人間が並んでいれば、その人のすぐ後ろに入れるようなキューをシミュレートする。 方針 チーム内での順番と全体のチームの順番とを別々のキューで管理した。 ソース #include<iostream> #include<string> #include<map> #inc</map></string></iostream>…

http://poj.org/problem?id=2260 概要 与えられた行列の各列各行の1の数が偶数であるか判定する。 偶数でない場合、ある一箇所を修正することで条件を満たすようにできるか調べる問題。 ソース #include<cstdio> #include<cstring> using namespace std; int main() { int n,a</cstring></cstdio>…

http://poj.org/problem?id=2263 概要 出発点から目的地までのパスの中で、パスの最小容量の辺の容量が最大になるようなパスを見つける問題。 ただ少し入力が面倒。 ソース #include<iostream> #include<cstring> #include<string> #include<map> using namespace std; #define REP(i,a,b) fo</map></string></cstring></iostream>…

http://poj.org/problem?id=2258 概要 グラフが与えられるので最も長いパスの長さを答える。 ソース #include<cstdio> #include<vector> #include<cstring> using namespace std; #define REP(i,a,b) for(i=a; i<b; ++i) #define rep(i,n) REP(i,0,n) int maxdepth; bool used[25][25]; void dfs(int depth,int p,vector<vector<int> > &g) { maxdepth = m…</b;></cstring></vector></cstdio>