問題文 https://icpcarchive.ecs.baylor.edu/external/56/5689.pdf色のついた円が与えられる。各データセットには色が400.0の円と789.0の円がひとつずつ含まれる。この円の上を通って、400.0の円から789.0の円に行って戻ってくることができるかどうか判定せ…

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

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1140&lang=jp 幅優先探索でスタート位置と汚れについて全点対間最短距離を求めておいて、パスを全部試す。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<queue> #define INF 100000000 #define </queue></string></algorithm></vector></iostream>…

問題文 http://poj.org/problem?id=3468 蟻本でも紹介されている問題。 セグメント木を実装した。各節点は次の2つのデータをもつ。 whole[ ] その節点の区間全体に一様に加えられた値 part[ ] その節点の区間に一様でなく加えられた値 #include<iostream> #include<vector> #in</vector></iostream>…

問題文 http://poj.org/problem?id=3692 最大クリーク問題。 二部グラフになっているので補グラフの最大独立集合を求める。 最大クリーク=補グラフの最大独立集合 が成り立つ。また二部グラフなら、 最大独立集合=頂点数-最大マッチング が成り立つ。 #inclu…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415 Monge DP。 週刊spaghetti_sourceさんにわかりやすい説明があったので参考にしながら解いた。 http://topcoder.g.hatena.ne.jp/spaghetti_source/20120915dp[ 左端 ][ 右端 ] := その…

問題文 http://poj.org/problem?id=1967 宝の位置とその宝を取れる制限時間が与えられる。任意の位置からスタートして、宝を全て拾うときの最短時間を求めよ。 区間DP。 l[訪れた区間の左端][右端]:=訪れた区間の左端を終端とする最短時間 r[訪れた区間の左…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1262無限にエネルギーのある車でレースをする。距離0の地点からスタートし、途中n個のチェックポイントがある。チェックポイントではタイヤの交換ができる。タイヤの交換にはb秒かかる。タ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1266 星と望遠鏡が与えられる。すべての望遠鏡を使って見える星の数を数えよ。 aとbをそれぞれ望遠鏡の方向ベクトルと星の位置ベクトルとすると、 cosθ=a•b/|a||b| θ=acos(a•b/|a||b|) で…

問題文 https://icpcarchive.ecs.baylor.edu/external/61/6139.pdf数列とクエリが与えられる。クエリは以下の2種類である。C a b 数列のa番目をbに更新する。 P a b 数列の区間[a,b]の積が負であれば-、0であれば0、正であれば+を出力する。 セグメント木を…

問題文 https://icpcarchive.ecs.baylor.edu/external/61/6138.pdf与えられた数字が、時計の短針と長針が作る角度に含まれるかどうかを判定せよ。短針は長針が12進んだときに1進む。 短針と長針が作る角度を全て生成しておく。工夫は必要ない。 #include<iostream> #in</iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1186&lang=jp 最初に問題の範囲で考えられる全ての整長方形を列挙。 後はソートして、入力と同じ長方形の次の整長方形を出力。 P3はP3( 対角線, P( 高さ, 幅 ) ) #include<iostream> #include<vector> #inclu</vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1188&lang=jp 構文解析した。 数字は全部n/2+1して、括弧ではソートして小さい方から過半数とる。 #include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; int now; string s; int num</algorithm></string></vector></iostream>…

問題文 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://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0580 座標圧縮した。 #include<iostream> #include<vector> #include<algorithm> #include<map> #define all(c) (c).begin(),(c).end() #define f first #define s second using namespace std; typedef long long ll; struct</map></algorithm></vector></iostream>…

文字列aとbの編集距離を求めるプログラムを書いた。 wikipediaの擬似コード↓を参考にした。 http://en.wikipedia.org/wiki/Levenshtein_distance文字の挿入や削除、置換によって一つの文字列を別の文字列に変形するのに必要な手順の最小回数を編集距離という…

問題文 http://poj.org/problem?id=3180N頭の牛がM本のロープでつながれている。 タンクの周りを正しく踊れている牛のグループの数を求めよ。 強連結成分分解して、含まれている頂点の数が2以上の強連結成分の数を数えた。 #include<iostream> #include<vector> #include<algorithm> using</algorithm></vector></iostream>…

問題文 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://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1175&lang=jp ビットDPで解いた。 dp[ 残っている円盤 ] := その状態がありえるかどうかcheckは円盤同士が重なっているかを判定する関数。 i countは立っているビットの数を数える関数。 #…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120 ビットDPで解いた。 dp[ すでに置いたケーキ ][ ケーキの番号 ] := 横幅countは立っているビットの数を数える関数。 #include<iostream> #include<vector> #include<string> #include<cstdio> #include<cmath> #include<algorithm> #include<climits></climits></algorithm></cmath></cstdio></string></vector></iostream>…

問題文 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://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秒間動くが、摩擦でスピードが減ってしまう。ビリヤード台の縦の壁と横の壁に玉が当た…