ABC011 D - 大ジャンプ

D - 大ジャンプ

部分点100点の解法。

概要

XY平面上の(0, 0)にいる。下記の移動のうちランダムにどれか1つを実行することN回繰り返した後、(X, Y)にいる確率を求めよ。

• X軸に平行に+Dだけ移動する
• X軸に平行に-Dだけ移動する
• Y軸に平行に+Dだけ移動する
• Y軸に平行に-Dだけ移動する

制約

1 ≦ N ≦ 30
1 ≦ D ≦ 10^9
-10^9 ≦ X, Y ≦ 10^9

方針

X, Y がDでどちらも割り切れる必要がある。そうでないなら到達できないので0を出力する。
X, Y がDでどちらも割り切れる場合は、X, Y をそれぞれDで割り、かつ移動を1と考えることが出来る。

メモ化再帰を行う。
dfs(count, nowX, nowY) : (X, Y)からスタートし、N - count回移動して(nowX, nowY)に到着する確率とする。

感想

公式解説を参考にしました。
https://www.slideshare.net/chokudai/abc011/23

「ある試行の結果の確率は、その試行が起きた状態の確率を1とし、そこから逆にたどってゆく」という考え方は重要そうです。

解答

Submission #4435964 - AtCoder Beginner Contest 011

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int N, D;
int X, Y;
 
vector<vector<vector<double>>> memo(40, vector<vector<double>>(80, vector<double>(80, -1.0)));
 
double dfs(int n, int nowX, int nowY){
	if(n == N){
		if(nowX == X + 40 && nowY == Y + 40) {
			return 1.0;
		}else{
			return 0.0;
		}
	}
 
	if(memo[n][nowX][nowY] != -1.0) return memo[n][nowX][nowY];
 
	double ret = 0.0;
	ret += 0.25 * dfs(n + 1, nowX + 1, nowY);
	ret += 0.25 * dfs(n + 1, nowX, nowY + 1);
	ret += 0.25 * dfs(n + 1, nowX - 1, nowY);
	ret += 0.25 * dfs(n + 1, nowX, nowY - 1);
	memo[n][nowX][nowY] = ret;
	return memo[n][nowX][nowY];
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N >> D;
	cin >> X >> Y;
 
	if(N > 30){
		cout << 0.0 << endl;
		return 0;
	}
 
	if(X % D != 0 || Y % D != 0){
		cout << 0.0 << endl;
		return 0;
	}
 
	X /= D;
	Y /= D;
 
	cout << fixed << setprecision(11) << dfs(0, 40, 40) << endl;
 
}