問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0530 DAGの最短経路はDPで簡単に求めることができる。 dp[i行目][左からj番目][1行飛ばしの残り回数]:=最小コスト #include<iostream> #include<vector> #include<queue> #include<cmath> #include<algorithm> #define f first #define</algorithm></cmath></queue></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181 本棚１段あたりの最小の幅xを仮定して、二分探索で探す。 #include<iostream> #include<algorithm> #include<vector> using namespace std; int m,n; vector<int>v; bool C(int x){ int cnt=0,sum=0,i=0; while(i</int></vector></algorithm></iostream>

問題文 http://uva.onlinejudge.org/external/115/11506.htmlコンピュータを頂点、ケーブルを辺とした無向グラフが与えられる。 コンピュータとケーブルを破壊して番号1のコンピュータから 番号Mのコンピュータへのパスをなくしたい。 コンピュータとケーブ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568 動的計画法で解いた。dp[i日目][j種類目のパスタ][l日連続]:=組み合わせの数 #include<iostream> #include<algorithm> #include<vector> #define A first #define B second using namespace std; typedef pair<int,int> P; i</int,int></vector></algorithm></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0232 動的計画法で解いた。dp[マスの番号][所持金]:=マス i に所持金 j で行ける確率とすると、 人生ゲームにイベントマスがなければ dp[i + v[k] ][j] += dp[i][j]/xv[k]はルーレットの数…

問題文 http://uva.onlinejudge.org/external/115/11567.html整数nが与えらるれので以下の3つの操作をして 0をnにする最小手数を求めよ。1を足す 1を引く 2を掛ける 3つの操作でnを0にする最小手数を再帰関数で数えた。 奇数なら-1と+1をどちらも試して、偶…

問題文 http://uva.onlinejudge.org/external/115/11565.htmlA,B,Cが与えられる。x+y+z=A xyz=B x^2+y^2+z^2=C以上の3つの条件を同時に満たすような 辞書順最小の3つの異なる整数(x,y,z)を求めよ。 整数なのでマイナスも含まれる。 xyz=B B x,y,zそれぞれに…

問題文POJ http://poj.org/problem?id=1088UVa http://uva.onlinejudge.org/external/102/10285.html縦r,横cのグリッドが与えられる。 上下左右で、数字が現在のセルより小さいセルにのみ移動可能。 移動できる最長経路の長さを求めよ。 メモ化再帰した。 PO…

問題文 http://poj.org/problem?id=1014 1から6までの価値がついたビー玉を二人で分けたい。 ビー玉の個数が与えられるので同じ価値になるように わけられるかどうか判定せよ。 動的計画法で解いた。 ビー玉の価値の合計の半分が作れればよい。 個数制限つき…

問題文 http://uva.onlinejudge.org/external/103/10308.html重み付きの無向の木が与えられるので 最遠頂点間の距離(木の直径と言う)を求める問題。 木の直径は２回の深さ優先探索で求めることができる。 まず適当な頂点から深さ優先探索して最も遠い頂点vを…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2274 0と1だけの列をランダムに作って条件を満たしていたら出力した。読んだもの http://d.hatena.ne.jp/jetbead/20110912/1315844091 http://www.slideshare.net/iwiwi/ss-13293754解説 h…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2361 ダイクストラでソートされた状態から全ての状態までの最短経路を 求めて、その中で最長のもののコストを出力した。各ノードはvec[4]={1,2,3,4}だったら、0001 0010 0011 0100のように…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0069全部試した。 #include<iostream> #include<algorithm> using namespace std; int d,a[31][12]; bool ok(int s,int g){ for(int i=0;i</algorithm></iostream>

問題文 UVa http://uva.onlinejudge.org/external/101/10117.htmlPOJ http://poj.org/problem?id=1271 高さhの牛乳に凸多角形のパンをk回浸す。 牛乳に浸されたパンの面積の最大値を求めよ。 パンの辺との距離がhかつ辺に平行な直線でパンを切り取る。 これ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2431 (全ての荷物の重さ)-(最長増加部分列の重さ)が答えになる。dp[ i ]:= i 番目を最後尾とする最長増加部分列の重さ dp[ i ]=max(dp[ j ] | 0 i未満の番号の最長増加部分列の最大値を求…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531 座標圧縮してからテープ張って幅優先探索で領域の数を数えた。 テープ張るのは↓のimosさんのやり方を参考にした。 http://imoz.jp/algorithms/imos_method.html #include<iostream> #include<vector> #i</vector></iostream>…

n個の点が与えられるので移動する時間の最大値が 最小になるような点を求める問題。 http://d.hatena.ne.jp/y_mazun/20121218/1355851934 ↑y_mazunさんの解法を参考にして解いた。 #include<iostream> #include<cmath> #include<cstdio> #include<vector> #include<algorithm> using namespace std; doubl</algorithm></vector></cstdio></cmath></iostream>…

重みなし無向グラフが与えられるので、 1からn駅までz回のステップで行けるかどうか判定する問題。 ただし直前の駅には戻れない。 z回のステップで1からnまで行くパターン数はグラフの隣接行列のn乗。 ノードを(現在の駅,直前の駅)としてグラフの隣接行列を…

sからgへの最小コストを求める問題。 まず各会社ごとに、その会社の路線だけを使った全駅間の最短経路を求める。 各会社ごとに運賃表も作っておく。 そうしたら上の二つを使って各会社ごとの全駅間の最小コストが求めれる。 この各会社のグラフから、各駅間…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251N件の家がM本の道でつながっている。 L個のプレゼントを届ける家の番号と届ける時間が与えられる。 プレゼントを予定通りに届けることができる最小のサンタの人数を求める問題。 https…

多角形の頂点がn個反時計回りに与えられる。 多角形の各頂点と多角形の内側の点Cを端点とする線分が 全て多角形の内側にあるような点Cが存在するような 多角形をstar shapeとする。 与えられた多角形がstar shapeであるかどうか判定する問題。 十分に大きい…

n個の黒い点とm個の白い点が与えられる。 黒い点と白い点を1本の直線でわけることが できるかどうかを判定する問題。 黒い点と白い点をそれぞれを凸包してから 2つの多角形が交差するかどうか判定した。 #include<cmath> #include<algorithm> #include<iostream> #include<vector> #include<climits> #incl</climits></vector></iostream></algorithm></cmath>…

蟻本を参考にした。 ビットDPで解いた。 dp[使った乗車券の集合][都市の番号]:=最小コスト #include<iostream> #include<vector> #include<algorithm> #include<cstdio> #define INF (1<<29) using namespace std; int main(void){ int n,m,p,a,b,x,y,z,in; double dp[(1<<8)][31],graph[31][31]; </cstdio></algorithm></vector></iostream>…