ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

ABC #011 D 大ジャンプ

概要


問題文はこちら
http://abc011.contest.atcoder.jp/tasks/abc011_4

解法


本番で解けなかったやつ、2パターンのやり方で解き直した。

まず共通する前処理として、どう頑張っても目的地に辿りつけない場合はそこで終了。
そして上下左右同じ距離を進むので目的地を(X / D, Y / D)として進む距離を1とする。

solve()の解法について
まずパスカルの三角形の求め方を用いてコンビネーションを求めておく。

あとの計算だが、上下左右にそれぞれ何歩進むかをループ処理で決める。
下のコードの流れだと、上下に歩く数を決めることで左右に歩く数も定まり、上に歩く数を決めることで下に歩く数も定まり、左に歩く数を....となる。
それらを計算してやればよい。

solve2()の解法について
上のやり方同様にパスカルの三角形の求め方を用いるが、今回はあらかじめ確率の計算をしておく。

計算については、上下と左右の移動数を決めて条件にあうようなら計算させる。
if文3つの下2つだが、例えば左右100歩進めるとして、最終的にx=10にいたいとする。そのとき左右の移動回数はそれぞれ(100 - 10) / 2回、(100 + 10) / 2回となる。つまり2で割り切れる必要がある。ということ(のはず)
あとは準備しておいた確率テーブルを使って解けばよい。
もちろんsolve()でやったようなコンビネーションのテーブルを使って解くこともできる。

類題


http://arc012.contest.atcoder.jp/tasks/arc012_4
SRM 573 Div1 Hard Div2 Hard

ソースコード

#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
#include <cstring>

using namespace std;

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back

typedef pair<int,int> P;
typedef long long int lli;

int N;
int D, X, Y;
long double  nCr[1001][1001];

long double solve() {
  nCr[0][0] = 1;
  rep(i, 1000) rep(j, i + 1) {
    nCr[i + 1][j] += nCr[i][j];
    nCr[i + 1][j + 1] += nCr[i][j];
  }

  long double ans = 0;

  for(int i = 0; i <= N; i++) {
    for(int up = 0; up <= i; up++) {
      int down = i - up;
      if(up - down != Y) continue;
      for(int left = 0; left <= N - i; left++) {
        int right = N - i - left;
        if(right - left != X) continue;
        ans += nCr[N][up] * nCr[N - up][down] * nCr[N - up - down][left] * nCr[N - up - down - left][right] / powl(4.0, N);
      }
    }
  }

  return ans;
}

long double solve2() {
  nCr[0][0] = 1;
  rep(i, 1000) rep(j, i + 1) {
    nCr[i + 1][j] += nCr[i][j] / 2;
    nCr[i + 1][j + 1] += nCr[i][j] / 2;
  }

  long double ans = 0;
  
  for(int i = 0; i <= N; i++) { // left or right
    int j = N - i; // up or down
    
    if(i < X || j < Y) continue;
    if((i - X) % 2) continue;
    if((j - Y) % 2) continue;
    
    ans += nCr[N][i] * nCr[i][(i - X) / 2] * nCr[j][(j - Y) / 2];
  } 

  return ans;
}

int main() {
  // ios_base::sync_with_stdio(false);
  cin >> N >> D >> X >> Y;
  X = abs(X);
  Y = abs(Y);
  bool canGo = true;
  if(X % D) canGo = false;
  if(Y % D) canGo = false;
  long double ans = 0.0;
  if(canGo) {
    X /= D;
    Y /= D;
    // ans = solve();
    ans = solve2();
  }
  printf("%.15Lf\n", ans);
  return 0;
}