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