問題 Cleaning Robot 解法 dpでやった、dp[i][y][x] := iターン目に(y,x)につく確率。 漸化式は dp[i+1][次のy座標][次のx座標] += dp[i][今のy座標][今のx座標] * 0.25 if(進めるなら) dp[i+1][今のy座標][今のx座標] += dp[i][今のy座標][今のx座標] * 0.2…

問題 KND is So Sexy。 解法 シュミレーション問題です。 ヘロンの公式っての使った。あとは三角形の周長が同じ場合は正三角形が一番大きくって一辺が固定されているなら２等辺三角形が極大。知りませんでした。 コード int main(){ double a, l, x; while(~…

問題 Fibonacci Sets f(i) = f(i-1) + f(i-2) フィボナッチ数です。で、1001で割って。 i...Vのノードがあって、iとjが | F(i) - F(j) | < d ならiとjは同じ集団に属している。 集団の数はいくつか 解法 Union_Find木を使うと解けます。 蟻本の出番。 コード…

問題 たくさんのなんかコロニーみたいなのがあって、全部のコロニーに行ったり来たりできるようにしたい。 各コロニーのx,y,z座標と半径rが与えられるのでコロニー間に設置する道の最短総距離を求める。 解法 似たような座標から距離求めて最短経路を求める…

問題 DNA Sorting 解法 ソートするだけの問題。 逆順になっている要素を数える。 コード int n, m; char c[64]; bool cmp(const string &a, const string &b){ int ac = 0, bc = 0; rep(i, a.size()){ REP(j, i, a.size()){ if(a[i] > a[j]) ac++; if(b[i] >…

問題 Eleven Puzzle。 解法 BFSだと間に合わない。地球は爆発しないよね。 id:nanikakaさんのはてなダイアリーで両側探索というものがあるのを知った、 実装はJavaだったので見ずに勘で実装してみた。 一発AC。 嬉しかったです。 コード vi p, next, now; ve…

問題 Bowling。 解法 シュミレーションの問題でいいんだよね。 ストライクとスペアに関するフラグを立てて、 ２倍足す(f--); 1と一緒 ３倍足す(f=1); って処理してく。10フレーム目はめんどくさい。 実装量が多いというか、きれいなコードにならなかった。 …

問題 (http://poj.org/problem?id=1005)。翻訳されてます。 解法 (0,0)から家までの距離を求めて、円の半径がそれを超えたら浸食される。 コード double x, y, d; int N; int main(){ scanf("%d", &N); rep(i, N){ scanf("%lf%lf", &x, &y); d = sqrt(x*x+y*…

問題 (http://wikiwiki.jp/pku/?1002%20487-3279)。 解法 map使うと簡単、入力を全部数えていって、複数あるやつだけ表示させる。 cin使うとTLEになった コード int n; vector<string>s; char in[100]; int main(){ map<char, int>m; m['A'] = m['B'] = m['C'] = '2'; m['D'] = </char,></string>…

問題 Hangover。 日本語訳。 解法 カードを落とさないように重ねていくクイズみたいなの解いたことあったような気がする。 カードが1枚から一つずつ増やしていって、つ長さを超えるのか計算していきます。 コード double d; int main(){ while(scanf("%lf", …

問題 Grid。 解法 縦横斜めで走査していって1の数をカウントする 斜めに走査するループの回し方が自分で書いたのにどうなってるのかよくわからない コード int n; char grid[256][256]; int solve(){ int res = 0, c; rep(i, n){ c = 0; rep(j, n){ if(grid[…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0119)。 解法 なんか論理の問題かな、推論とかするのかなと思っていたら、 (きこえますか...あなたの脳内に...直接語りかけています...トロピカル...いえ...トポロジカルソートを使うのです…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0157) 解法 DPで解きます。ソートした後最長増加部分列を求めます。 コード int n, m; vector<pi>s; int dp[1024]; int main(){ while(scanf("%d", &n) && n){ s.clear(); int h, r; rep(i, n){</pi>…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2153)。 解法 BFSで解く。今まで通った場所を記憶するのにmapを使うとメモリが足りなくなる。 コード int W, H, used[52][52][52][52]; int dy[] = {0,-1,0,1}, dx[] = {-1,0,1,0}; char le…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2026) N枚のカードがあったそれを一枚ずつ出していく。出せるのは今までに出した、カードの総和の約数だけ。 解法 DFSで解く。普通に解いても無理だった。逆から解くとできるんだって コー…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1218) 図だけでもなんとか分かるよね。ゴールまで最短で何回動かせばいいか 解法 BFSで動かしていきます。押す方向と逆の方向に人が立てるか、現在いるところからそこにいくことができるか…

問題 AからHのカードを並べてく、カードのセットに相対的な位置だけでカウントしていくから AとBのセットをかえても同じ 解法 DFSで解きます。 コード int board[4][4]; int dy[4], dx[4]; int dfs(int n){ if(n >= 8) return 1; int res = 0; int y, x; rep…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011) 解法 詳しくはhttp://www.deqnotes.net/acmicpc/p0017/。 コード ````cpp int m[64][64], in[64][32]; int main(){ int n, f, day; while(scanf("%d", &n) && n){ memset(m, 0, sizeo…

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0169) 解法 DFSが楽。あとは1以外を全部足してから1をどうするかってやる。 コード DFS int a[512], p; int dfs(int n, int c){ if(n > 21) return 0; if(c == p) return n; if(a[c] == 1) …

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1210) top、north、westはそれぞれ1,2,3とする さいころを指示通りに転がした時、topに来る面は何か？ 解法 シュミレーション問題です。 コード int n, top, west, north; string op; int m…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1210。 top、north、westはそれぞれ1,2,3とする さいころを指示通りに転がした時、topに来る面は何か？ 解法 シュミレーション問題です。 コード int n, top, west, north; string op; int m…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0199。 解法 シュミレーション問題です。 Cの座る条件をいくつか見逃していてWA連発。 『How to Solve It』に問題を理解することって書いてあったのに。 ちゃんと問題を読むようにします コ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0178。 解法 シュミレーション問題です。 指示通りに処理すればできる高さは十分にとっておかないとRUNTIME ERROR吐かれる コード int t[UNDER+10][5], n; int count(){ int res = 0; rep(i,…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1117。 所々、虫食いになってる表が与えられるからそれを埋める。 解法 一カ所だけ?の行(列)なら埋められる。 コード int p, s; char row[10]; int a[128][128], b[128][128]; int main(){ b…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1248。 ２つの重りと計りたい分量が与えられる。それぞれ重りをいくつ使えば計れるか？ 重りはより少なく、軽いものを選ぶ。 解法 aの数、xがでれば、yは一つに定まる。xに関するループを回…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1248。 ２つの重りと計りたい分量が与えられる。それぞれ重りをいくつ使えば計れるか？ 重りはより少なく、軽いものを選ぶ。 解法 aの数、xがでれば、yは一つに定まる。xに関するループを回…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0165。 解法 p-m以上p+m以下の素数数えていく。素数を用意する配列にはa[i]、i以下の素数の数を累積和で記録しておかないとTLEになる コード int p[MAX_P], n, sum[MAX_P]; int main(){ p[0]…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1006。 チャンネル数とCMの時間が与えられる。CMを見ずに何分間テレビを見れるか。 解法 実装するだけ コード int n, p, q, m, s, e; int t[100000]; int main(){ while(scanf("%d%d%d", &n,…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1214。 antが自分の巣に帰る最短距離を求める。四方向に一つ進むのに1timeかかる。初期の体力が6で1timeごとに1ずつ減っていく、食べ物のマスを通ると体力が6になる。 解法 食べ物は２回以上…

gitの使い方分からないのでいちいち書く git add * git commit -m 'コミットするよ' git push sedgewick master これでできる