問題文 http://uva.onlinejudge.org/external/102/10299.html1以上でnより小さい、nと互いに素な数の個数を求めよ。 包除原理。 互いに素であるという事は共通素因数を持たないということ。 1からn-1のなかでこのような数の個数を求めればよい。 例えばn=30…

問題文 http://uva.onlinejudge.org/external/110/11069.html1~nまでの頂点が一直線につながっている。このグラフから、どの頂点も隣り合っていない物の中で、これ以上頂点を追加できないものの数を数えよ。 dp[頂点]:=場合の数 とすると、頂点が2つ前のもの…

問題文 http://uva.onlinejudge.org/external/109/10991.html3つの円の半径が与えられる。図のように3つの円に囲まれた部分の面積を求めよ。 3つの円の中心を頂点とする三角形の面積から、その三角形の内部の扇型の面積を引いてやればよい。三角形の面積はヘ…

問題文 http://uva.onlinejudge.org/external/113/11310.html o oo oの二つで縦2,幅nのブロックを作るパターン数を求めよ。 ↓類題。 http://d.hatena.ne.jp/TobiasGSmollett/20130618/1371579981 ooooooooo ooooooooo のように長さnのパターン数をf[ n ], oo…

問題文 http://uva.onlinejudge.org/external/114/11428.htmlN=(xの3乗根)-(yの3乗根)となるようなx,yの中でyが最小のものを求めよ。 全部試した。 #include<iostream> #include<algorithm> using namespace std; int main(void){ int n; while(cin >> n,n){ for(int y=1;y<101;y+</algorithm></iostream>…

問題文 http://uva.onlinejudge.org/external/106/10625.html(1文字)->(文字列) のように変換表が与えられる。 さらに、 (文字列) (1文字 x) (数字 n) のようにクエリが与えられるので、文字列を変換表に従ってn回変換した時、文字列中に現れる文字xの個数を…

問題文 http://uva.onlinejudge.org/external/100/10088.html単純多角形が与えらる。その中の格子点の数を求めよ。 x,y座標の範囲は絶対値1000000。 ピックの定理を使った。http://en.wikipedia.org/wiki/Pick%27s_theorem ↑ピックの定理( 格子点の数 ) = ( …

問題文 http://uva.onlinejudge.org/external/107/10739.html文字列が与えられる。ある１文字を追加、削除、置換することができる。 この３つの操作を繰り返すことで回文を作りたい。 操作を繰り返す回数の最小回数を求めよ。 l r l r 追加 e b c d a e b c …

問題文 http://uva.onlinejudge.org/external/9/928.html進む距離を1,2,3,1,2,3のように繰り返してSからEにいくときの最短ステップ数を出力せよ。行けない時はNOと出力せよ。 幅優先探索した。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cstring> #include<cctype> #incl</cctype></cstring></string></algorithm></vector></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://uva.onlinejudge.org/external/111/11130.html横a,縦bインチのビリヤード台があって、その中央から玉を反時計周りにA度の角度に速度vで打ち出す。この玉はs秒間動くが、摩擦でスピードが減ってしまう。ビリヤード台の縦の壁と横の壁に玉が当た…

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

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

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

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

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

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