ABC 011 D
今回はこの問題です。
高橋君は上下左右に距離dだけ移動できます。それぞれ1/4の確率で移動します。初期値が(0, 0)で目標地点が(x, y)であるとき、ちょうどn回の移動で目的地点に辿り着ける確率はどれだけでしょうか、という問題です。
100点は得られましたが最後の最後でつまったので解説を見ました。解答は以下のようになりました。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 double solve(int n, int d, int x, int y) { if(x % d != 0 || y % d != 0 || (x + y) / d > n || (n - (x + y) / d) % 2 == 1) return 0.0; // cout << x / d << " " << y / d << endl; double kumiawase[1001][1001] = {}; for(int i = 0; i <= n; i++){ kumiawase[i][0] = 1; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ kumiawase[i][j] = (4 * kumiawase[i - 1][j] + kumiawase[i - 1][j - 1]) * 0.25; } } double result = 0.0; for(int k = 0; k <= (n - (x + y) / d) / 2; k++){ double tmp = kumiawase[n][x / d + k]; // 右 tmp = tmp * kumiawase[n - x / d - k][y / d + (n - (x + y) / d) / 2 - k]; // 上 tmp = tmp * kumiawase[(n - (x + y) / d) / 2][k]; // 左 tmp = tmp * pow(0.25, (n - (x + y) / d) / 2 - k); // 下 result += tmp; } return result; } int main() { int n, d, x, y; cin >> n >> d >> x >> y; x = abs(x); y = abs(y); double ans = solve(n, d, x, y); printf("%.10f\n", ans); return 0; }
xとyはあとで使う時正数のほうがいいので絶対値を取っておきます。
まず、xまたはyがdで割り切れない時、ジャンプ回数が足りない時、残りのジャンプ回数が2で割り切れない時(割り切れないと正しい位置にたどり着けません)は0.0を返すようにします。
次に組み合わせを求めます。kumiawase[i][j] = iCj * pow(0.25, j)となるようにしています。
目的地にたどり着くのに必要なジャンプ以外は、上下の組もしくは左右の組が合わせて(n - (x + y) / d) / 2回出るようにすれば目的地にたどり着けます。左右がk回、のこりは上下に飛ぶとして考えます。このとき右にはx/d + k、上にはy/d + (n - (x + y) / d) / 2 - k、左にはk、下には (n - (x + y) / d) / 2 - k回飛ぶことになります。あとはk = 0からk = (n - (x + y) / d) / 2までこの確率を求め、その和をとれば解になります。
nの最大値が1000ということで動的計画法で組み合わせの数がもとめられるじゃん！と思いましたが、int型では溢れてしまうんですね。なので確率と組み合わせておくことであふれずに計算できます。覚えておきたいなと思いました。
