○○× +0 で 475.24点 61位 1124 -> 1194でした。

問題 ある数列からk個飛ばしのペアをとっていくとき、とった数字の和の最大を求める問題 方針 k+1の余りで分類してやれば、k=0の場合の問題になるのでそれをdpで解いた。

問題 三匹のうさぎの試験に対する解答が与えられるので、 ２匹目と３匹目のとりうる得点の和の最大を求める問題。 ただし、１匹目のうさぎの解答は全て間違っていることが分かっている。 方針 文字列の前から順に見てやるだけ

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

今日は頑張って多倍長整数のライブラリを作りました。

ほうしん まず番号がかぶっているブロックがあるので、番号を振り直す。 そのときついでに、自分の上に乗っているブロックと自分が他のブロックまたは地面と接している部分を求めておく。 一番下の地面に接しているブロックから順に、自分と自分の上に乗って…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1140&lang=jp ほうしん 幅優先探索で、各汚れたタイルと初期位置との距離を全て求めておきTSPにして解く。 ソース #include<iostream> #include<string> #include<cstring> #include<queue> #include<vector> #include<algorithm> using names</algorithm></vector></queue></cstring></string></iostream>…

参加はしてないですが、プラクティスで解いたので

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1126 方針 ある位置までの可能な最大値でDPする。 ソース #include<iostream> #include<string> using namespace std; #define REP(i,a,b) for(int i=a; i</string></iostream>

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

×○××× 1607 -> 1541

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

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1014 概要 温泉とそれぞれの地区の距離が与えられるので、すべての地区に温泉がいきわたるための 最小のパイプの長さを求める。 方針 はじめにヒープに温泉から出ている辺をすべて追加…

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://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1032&lang=jp 概要 最低限の単位数を確保する最小の講義数を求める問題。 ある講義に対して、あらかじめとっておかないといけない講義がある場合がある。 ほうしん うまいやり方が思い…

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

少なくとも50問は解きたい。

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0527 方針 同じ色の碁石が連続する部分を、部分の始まり、部分の終わり、色を要素にもつ構造体で表した。 ソース #include<vector> #include<iostream> using namespace std; #define REP(i,a,b) for(i=a;</iostream></vector>…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0525 方針 行数が最大10行までと小さいので、行のひっくり返し方を決めて全探索する。 行のひっくり返し方が決まれば、列の最適なひっくり返し方は一意に決まる。 ソース #include<cstdio> #inc</cstdio>…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0520 方針 dfsして、先端の方から順番に重さを決める。 ソース #include<iostream> #include<vector> using namespace std; #define REP(i,a,b) for(i=a; i</vector></iostream>

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

概要 10個以下の長さ10以下の文字列が与えられるので、それらの全てを部分文字列に含む最も短い文字列を求める。 複数ある場合は辞書順最小のものを。 方針 すでに他の文字列の部分文字列になっているものは省いてから、つなぎ方を全探索する。 このとき、二…

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>…

PKUやAOJで解いた問題やTopCoderやcodeforcesへの参加の記録をつけていこうと思います。

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>