実に5ヶ月ぶり、今年最後のSRM。 8月はSWoPPといろいろ、9月は旅行いったりなんだり、後半から12月頭まではSCとその後処理 としばらく参加できていなかった… 結果 o--(+0/-0) 228.60pts 219th 1959->1965(+6)維持できてよかった。 250 MonstersValley 典型的…

結果 ooo--(+0/-0)2184pts 135th Rate:1501->1588 A 意外とめんどい。とりあえず10^9以下の三角数を列挙してsetに突っ込んで それらに対して入力からある三角数を引いたものが集合内にあるかどうかでやった。初め全列挙とかしてたら意外と時間かかった。 B …

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=382916 方針 DP。 dp[i][j] := (i-1,j-1)を末尾とする最大の文字列 dp[i][j] = "" ((i,j)がアルファベット) dp[i][j] = max(dp[i-1][j] + (i,j), dp[i][j-1] + (i,j)) (左から来るか、上から来…

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=382422 方針 典型的なDP dp[i][j] := i回振った後にjマス目にいる確率を計算していけばよい。n番のマスに到達した場合それ以上の移動はせず、 答えとしては を出力すればよい。

AOJ上でソースを公開できるようになったのでそのテストも兼ねてソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=376363与えられたN(1 2^15以下の平方数は181個しかないのでDPで dp[i][j][k] := i番目の平方数まででj個使った和がkになるような…

問題 整数nが与えられる。 0,1,...,n-1行にそれぞれn-1,n-2,...1個のスペースがあるとし、左詰めで箱を詰める。 ただし、i行目の箱の数a_はa_i>a_j(i 方針 要は下に行くほど少なくなっていけばよい。 n-1行は0個か1個なので dp[0][0] = 1; dp[0][1] = 1; と…

久々にDPを全部自力で解けた。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0232 方針 dp[i][j] := i-thマスに得点jで来る確率 としてDP。 マスに止まる確率のみだと期待値が計算できないので、得点をDPテーブルに 入れるという発想が出…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0203 方針 配るDP。貰うDPでも書けなくはないと思う。 下から二段目にジャンプ台がある場合に注意。以下ソースコード #include <iostream> #include <cstring> #include <algorithm> using namespace std; int dw[3] = {-1,</algorithm></cstring></iostream>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0191 方針 i回目に選ぶものを決めるために影響するのはi-1回目に何を選んだかのみで、それまでにどういう選び方をしたかは関係ないので dp[i][j] := i回目にjを選んだ場合の最大の長さ とし…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120 方針 左から円を並べていくと考えると、右端の円の大きさと追加する円の大きさによって増加する長さが変わることが解る。n dp[state][back] := state使った右端がbackであるものの長さ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1082 元ネタが解りません… 方針 配る系のDP。 5種類音のある子音列はループするまでは あ->ああ->あああ あい ->い ->いあ ->う というように、最後にa音を1文字つけるor最後の文字を1つ進め…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1056 方針 DP。誤差制限が緩いので dp[n][k] := n回目にゲットできる確率が2^-kである確率 として dp[i+1][0] += dp[i][k] * (1 - pow(0.5,k)) //取れなかったら次の確率は1 dp[i+1][k+1] …

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1020 方針 dp[second][pos]で i+1秒後に次の移動先next_posに移動できるなら dp[i+1][next_pos] += dp[i][pos] * 0.25; そうでなければ dp[i+1][pos] += dp[i][pos] * 0.25; とすればよい…