問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109&lang=jp 構文解析の基本。 https://gist.github.com/draftcode/1357281 ↑にわかりやすい解説が書いてるので参考にした。 #include<iostream> #include<algorithm> #include<string> using namespace std; int expre</string></algorithm></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2508 シーザー暗号やるだけ。 #include<iostream> #include<vector> #include<algorithm> #include<cstring> #include<string> #include<cctype> #include<cmath> using namespace std; string str="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxy</cmath></cctype></string></cstring></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1176&lang=jp メモ化再帰した。再帰関数の引数は左上の位置と右下の位置+1。 配列uは累積和を計算しておいた。 #include<iostream> #include<algorithm> #define f first #define s second #define INF (1<<29) </algorithm></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1126 上と左の数の後ろにのみ現在の数をつけることができる。最大の数字を出力せよ。 動的計画法。 dp[ y ][ x ]:=最大の数字の文字列 grid[ y ][ x ]:=入力 とすると dp[y][x]=max( dp[ y…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2401 構文解析+全探索。 http://uva.onlinejudge.org/external/111/11108.html ↑の問題が似てる。 #include<iostream> #include<string> #include<algorithm> using namespace std; int now,al; string s; bool formula(</algorithm></string></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2399 やるだけ。情報を知っている人のリストは昇順とは限らない。 #include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<vector> using namespace std; int main(void){ int n,m; while(cin >> n,n){ vec</vector></algorithm></string></cstdio></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1174&lang=jp パネルの変え方は全部で6^5通りなので全部試せる。 #include<iostream> #include<string> #include<vector> #include<algorithm> #define rep(i,n) for(int i=0;i</algorithm></vector></string></iostream>

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1020&lang=jp 確率DP。 dp[使ったバッテリーの量][Y座標][X座標]:=確率dp[k+1][y+dy[ i ] ][x+dx[ i ] ]+=dp[k][y][x]/4もしその方向に動けない場合はdp[k+1][y][x]+=dp[k][y][x]/4 #inclu…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1167&lang=jp 典型的な動的計画法。 i * ( i + 1 ) * ( i + 2 ) / 6 円玉で n 円作るときの最小枚数。dp1[作る正整数]:=正四面体の最小個数 dp2→奇数しか使えないとき #include<iostream> #include<algorithm> #</algorithm></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155&lang=jp 構文解析やるだけ。'-'→2-X '*'→min(X,Y) '+'→max(X,Y) #include<iostream> #include<algorithm> #include<string> #include<cctype> #define rep(i,n) for((i)=0;(i)<(n);i++) using namespace std; int p,q,r,now</cctype></string></algorithm></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1244 構文解析。参考にしたもの https://gist.github.com/draftcode/1357281 #include<iostream> #include<algorithm> #include<string> #include<cctype> #include<map> using namespace std; int now; string str; map<string,int>mp; int Numbe</string,int></map></cctype></string></algorithm></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1055&lang=jp 連結でないグラフが与えられる。このグラフの連結成分は全て輪になっている。この連結成分からコストが最大の辺を一つだけ消してできるものがクランである。 よって一つの連…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089 動的計画法で解いた。 dp[ i行目 ][ j列目 ]:=最大コストとすると、i行目のj列目にはi-1行目の同じj列と i i>N のとき i-1行目のj+1列目 (Nは行数) から来れるので、この2ヶ所までの…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0569 深さ優先探索した。問題文の通りに座標を配列で表現すると(0,0)等は絶対に外側になる。 (0,0)から探索して各マスで隣り合う建物の数を数えた。 #include<iostream> using namespace std; int h,</iostream>…

問題文 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://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://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>

問題文 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>…