問題文 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://uva.onlinejudge.org/external/104/10404.htmlStanとOllieが石をnum[ i ]個ずつ取っていって最後のひとつを取ったほうが勝ち。どちらが勝つか判定せよ。 蟻本4-2章そのまま。解きなおした。 dp[ 残っている石の個数 ] := 勝敗dp[ 0 ] = 負け d…

問題文 http://uva.onlinejudge.org/external/105/10503.html無向グラフが与えられる。スタートからゴールまでちょうどn回のステップで行くことができるか判定せよ。 全探索した。 #include<set> #include<iostream> #include<vector> #include<algorithm> #include<string> #define f first #define s </string></algorithm></vector></iostream></set>…

問題文 http://uva.onlinejudge.org/external/116/11665.htmlいくつかの多角形(凸とは限らない)を墨で塗りつぶしたときいくつの多角形ができるか求めよ。 点-多角形包含判定。本番はライブラリが間違ってたらしく通せなかった。spaghetti sourceさんを参考に…

問題文 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://uva.onlinejudge.org/external/111/11130.html横a,縦bインチのビリヤード台があって、その中央から玉を反時計周りにA度の角度に速度vで打ち出す。この玉はs秒間動くが、摩擦でスピードが減ってしまう。ビリヤード台の縦の壁と横の壁に玉が当た…

問題文 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://uva.onlinejudge.org/external/111/11108.html WFFという文法が与えられる。以下のようなものだ。 1.p,q,r,s,tはWFFである。 2.WFFである文字列をwとおくと、NwはWFFである。 3.WFFである文字列二つをw,xとおくと、Kwx,Awx,Cwx,EwxはWFFである…

問題文 http://uva.onlinejudge.org/external/114/11463.html ワーシャルフロイドで全点間の最短距離を求めておいて、始点sと始点から最も遠い頂点の距離と、その頂点から終点dまでの距離を求めた。 #include<iostream> #include<algorithm> #define INF 10000000 using namespace</algorithm></iostream>…

問題文 http://uva.onlinejudge.org/external/101/10168.htmlnを4つの素数の和で表す。その表し方のうちの一つを出力せよ。不可能な場合は"Impossible."と出力せよ。 http://ja.wikipedia.org/wiki/%E3%82%B4%E3%83%BC%E3%83%AB%E3%83%89%E3%83%90%E3%83%83%…

問題文 http://uva.onlinejudge.org/external/109/10911.htmln*2個の点の座標が与えられる。これらの点をペアにしたときの2点間の距離の和の最小値を求めよ。 ビットDPした。 dp[使った点の集合]:=距離の和の最小値 #include<iostream> #include<vector> #include<algorithm> #include<string> #in</string></algorithm></vector></iostream>…

問題文 http://uva.onlinejudge.org/external/2/216.htmln個の点が与えられる。これらの点を一筆書きしたときの最短距離とそのときのパスを出力せよ。ただし各点の間の距離は16を足したものとし、パスは入力で先に来る方の端点を始点とする。 点は8個までし…

問題文 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://uva.onlinejudge.org/external/109/10918.html2×1のタイルを使って3×nの長方形を作るときの作り方が何通りあるかを求めよ。 f[横の長さn]:=3×nの長方形の作り方の総和 g[横の長さn]:=3×nの長方形から隅を一つ消した形の作り方の総和 ....... A…

問題文 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://uva.onlinejudge.org/external/9/907.htmln個の休憩地点がある山をk回の休憩をして登る。 一回あたりの登る距離の最悪の長さを最小化せよ。 解を決め打ちして二分探索した。 動的計画法でも解けるらしい。 #include<iostream> #include<algorithm> #include<vector> using n</vector></algorithm></iostream>…

問題文 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://www.prefield.com/algorithm/sort/quicksort.html ↑spaghetti source様から拝借しました。↓は要素数nとソートしたい要素を与えると…

モンテカルロ法で図形の面積を求めることができる。x*x/4+y*y=1 の式で示される楕円の面積をモンテカルロ法で求める。乱数 0≦x≦2 , 0≦y≦1 を2×1の長方形の中に均一に落とす。 1/4の楕円の中に入った乱数の数をr 落とした乱数の総数をn 1/4の楕円の面積をSと…

モンテカルロ法で円周率を求めるプログラムを簡単に書いてみた。 円周率の計算にはもっとよい方法があるのでこの方法は使われていない。1辺の長さが1の正方形とそれに内接する4分の1円(扇形)がある。正方形の面積 : 扇形の面積 = 1 : π / 4この正方形のなか…

問題文 http://uva.onlinejudge.org/external/115/11579.html辺の長さがいくつか与えられるので 作ることができる三角形の最大の面積を求めなさい。 ソートして連続する三つの辺を使った三角形が候補になる。 それを全部試して面積を求めた。 面積求めるのは…

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