土下座しながら探索中

主に競技プログラミング

Typical DP Contest J : ボール

問題リンク :
J: ボール - Typical DP Contest | AtCoder

問題概要:略

解法:
期待値苦手すぎて謎だったので以下の解説記事を参考にしました
Typical DP Contest J - ボール - Lilliput Steps

ビットDP (orメモ化再帰)
まだ倒れていないものがある場所に対応するビットを1にしておきます
dp[bit] := 倒れていないものの状態がbitで、ここからすべて倒すまでに必要なボールを投げる回数の期待値

状態bitからボールを投げるとき、次に投げるボールを落とす位置をすべて試してみて、その中で最小の期待値をdp[bit]にいれる

状態bitから全て倒すために必要な期待値は、狙った場所をxとしたとき
dp[bit] = dp[bit&~(1<< ( x - 1 ) ) ] / 3 + dp[bit&~ ( 1 << x ) ] / 3 + dp[bit&~(1<< ( x + 1 ) ) ] / 3
このxを全てためしてみてその最小値をdp[bit]にいれる
ただし、x,x-1,x+1のうち、すでに倒した場所orそもそもない場所に落ちたときはdp[bit]が左辺に残ることになる
なので、そのときはその部分を左辺に以降すること

コード1(メモ化再帰):

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

const double DINF = DBL_MAX;

int n,bitmask,x[20];
double memo[1<<20];

double dfs(int state) {
  if( !state ) return 0;
  if( !equals(memo[state],DINF) ) return memo[state];
  REP(i,1,17) {
    double ex = 1;
    double same = 0;
    REP(dx,-1,2) {
      int p = i + dx; 
      int nstate = state;
      nstate = state & ~(1<<p);
      if( state == nstate ) ++same;
      else {
	ex += dfs(nstate) / 3.0;
      }
    }
    ex = ( ex * 3.0 ) / ( 3.0 - same );
    memo[state] = min(memo[state],ex);
  }
  return memo[state];
}

int main() {
  cin >> n;
  rep(i,n) {
    cin >> x[i];
    ++x[i];
    bitmask |= (1<<x[i]);
  }
  rep(i,(1<<18)) memo[i] = DINF;
  printf("%.10f\n",dfs(bitmask));
  return 0;
}

コード2(ビットDP):

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

const double DINF = DBL_MAX;

int n,x[20],bitmask;
double dp[1<<20];

int main() {
  cin >> n;
  rep(i,n) {
    cin >> x[i];
    ++x[i];
    bitmask |= (1<<x[i]);
  }
  rep(i,(1<<20)) dp[i] = DINF;
  dp[0] = 0;
  for(int state=1;state<=bitmask;state++) {
    if( state & ~bitmask ) continue;
    double mini = DINF;
    for(int p=1;p<=16;p++) {
      double ex = 0;
      double same = 0;
      bool fail = false;
      for(int dx=-1;dx<=1;dx++) {
	int np = p + dx;
	int next_state = state;
	if( (bitmask>>np) & 1 ) next_state &= ~(1<<np);
	if( next_state == state ) ++same;
	else if( equals(dp[next_state],DINF) ) { fail = true; break; }
	else ex += dp[next_state]/3.0;
      }
      if( !fail ) mini = min(mini,((1.0+ex)*3.0)/(3.0-same));
    }
    dp[state] = mini;
  }
  printf("%.10f\n",dp[bitmask]);
  return 0;
}

ここからは2016/6/10に追記:

既に解いていたことをすっかり忘れて再度解いたので解説を追加

ものを倒す順番に意味はないので左から順番にものを倒していくことを考える
f:id:tei3344:20160610013907p:plain
左から順番にものを倒していくので、ボールを投げるべき座標は一意に定まる
その座標は、一番左にあるものの座標をxとしたとき、x+1である
f:id:tei3344:20160610014452p:plain
この理由は次の通り
座標xにある物を倒せる座標はx-1,x,x+1のいずれか
しかし、左から順番に倒していくためx-1以下の座標にはものは存在しない
そのためx-1を狙ってボールを投げると、絶対にボールが存在しない座標x-1とx-2にボールが落ちる可能性があり、その分が無駄である
同様の理由から、xを狙ってボールを投げると絶対にボールが存在しない座標x-1にボールが落ちる可能性があり、その分が無駄である
x+1を狙ってボールを投げた場合、ボールが落ちる可能性があるのは座標x,x+1,x+2である
これらの座標にはものが存在する可能性があり、先ほどの2つと比べて無駄がない
そのためx+1を狙ってボールを投げれば良いことが分かる

x+1にボールを投げればよいということが分かった
ここで、x+1にボールを投げた際にボールの落ちる可能性のある場所の状態は次の4通りである
状態1.
f:id:tei3344:20160610015457p:plain
状態2.
f:id:tei3344:20160610015517p:plain
状態3.
f:id:tei3344:20160610015534p:plain
状態4.
f:id:tei3344:20160610015555p:plain

それぞれの状態について考える
状態1.
座標xにあるものを倒すまでに必要な投げる回数の期待値は3である
この期待値は次の様にして求まる
1回目で倒せる確率は1/3
2回目で倒せる確率は2/3 * 1/3
3回目で倒せる確率は2/3 * 2/3 * 1/3
...
n回目で倒せる確率は(2/3)^(n-1) * 1/3
期待値はi回目で倒せる確率*i (1<= i <= ∞)の総和となる
8byteのdouble型で計算することを考えると、(2/3)^500はもう0といっていいくらい小さいことが分かる
なので、先ほどの計算を1から500くらいまで愚直にやってみると良い
すると期待値が3に収束していることを確認できる
手でやるなら式をたてて極限でやれば良い


状態2.
座標x,x+1にあるものを倒すまでに必要な投げる回数の期待値は4.5である
この期待値はサンプル1にある通り(xからx+2までの範囲にたっているものの数が同じであれば状態が異なっても期待値は同じ)
x,x+1,x+2にものが1つしか立っていない状態からそれを倒すまでに必要な投げる回数の期待値は3であることから、
x,x+1,x+2にものが2つ立っている状態からものが1つ立っている状態にするために必要な投げる回数の期待値は1.5であることが分かる ( 4.5 - 3.0 = 1.5 )
この結果を用いて次の様に期待値を求めることができる

座標x+1にボールを投げたとき、
xにあるものを倒せたなら、状態1か状態5に遷移する
x+1にあるものを倒せたなら、状態1に遷移する
これらが確率1/2で起こるので、この時の期待値は
(たっているものの数を2個から1個するための期待値=1.5) +
(xにあるものを倒した後、残り全てを倒すまでに必要な期待値) / 2 +
(x+1にあるものを倒した後、残り全てを倒すまでに必要な期待値) / 2

状態3.
状態2とほとんど同じ
x+1がx+2になるだけ

状態4.
座標x,x+1,x+2にあるものを倒すまでに必要な投げる回数の期待値は5.5
なぜなら、3個立っている状態から1個倒すまでに必要な投げる回数の期待値は1(どこに落ちても必ず1本は倒せるから)
2個立っている状態から1個倒すまでに必要な投げる回数の期待値は1.5なので
3個立っている状態から2個倒すまでに必要な投げる回数の期待値は2.5
1個立っている状態から全て倒すまでに必要な投げる回数の期待値は3なので
3個立っている状態から全て倒すまでに必要な投げる回数の期待値は 2.5 + 3 = 5.5

ものが2個立っている状態から全て倒すまでに必要な投げる回数の期待値が4.5なので、
ものが3個たっている状態からものが2個たっている状態にするまでに必要な投げる回数の期待値は1 ( 5.5 - 4.5 = 1 )
また、座標x+1にものを投げると座標x,x+1,x+2のどれか1個が倒れるので、このときの期待値は
(たっているものの数を3個から1個にするまでに必要な投げる回数の期待値=1) +
(xにあるものを倒した後、残り全てを倒すまでに必要な期待値) / 3 +
(x+1にあるものを倒した後、残り全てを倒すまでに必要な期待値) / 3
(x+2にあるものを倒した後、残り全てを倒すまでに必要な期待値) / 3

これらを再帰的に計算すると良い

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

/*
  1->0 : 3
  2->1 : 1.5 2->0 4.5
  3->2 : 1   3->1 2.5 3->0 5.5
 */

int n,x[16];
double memo[1<<18];

double dfs(int bitmask) {
  if( !( memo[bitmask] < 0.0 ) ) return memo[bitmask];
  if( bitmask == 0 ) return 0.0;

  int use = bitmask & -bitmask;
  int x   = log2(use);
  int state = (bitmask>>x&1) | (((bitmask>>(x+1))&1)<<1) | (((bitmask>>(x+2))&1)<<2);
  if( state == 1 ) {
    memo[bitmask] = 3.0;
    return memo[bitmask] += dfs(bitmask&(~use));
  } else if( state == 3 ) {
    memo[bitmask] = 1.5;
    return memo[bitmask] += ( dfs(bitmask&(~use)) * 0.5 + dfs(bitmask&(~(1<<(x+1)))) * 0.5 );
  } else if( state == 5 ) {
    memo[bitmask] = 1.5;
    return memo[bitmask] += ( dfs(bitmask&(~use)) * 0.5 + dfs(bitmask&(~(1<<(x+2)))) * 0.5 );
  } else if( state == 7 ) {
    memo[bitmask] = 1;
    return memo[bitmask] += ( dfs(bitmask&(~use)) / 3.0 + dfs(bitmask&(~(1<<(x+1)))) / 3.0 +
                             dfs(bitmask&(~(1<<(x+2)))) / 3.0);
  }
  assert(false);
}

void compute() {
  int bitmask = 0;
  rep(i,n) bitmask |= (1<<(x[i]+1));
  rep(i,(1<<18)) memo[i] = -1.0;
  printf("%.10f\n",dfs(bitmask));
}

int main() {
  cin >> n;
  rep(i,n) cin >> x[i];
  compute();
  return 0;
}