Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2120-e795b3b8
この記事にトラックバックする(FC2ブログユーザー)

September 2011 Cook-Off 4問目 - Target Practice (この記事を編集する[管理者用])

Source

codechef September 2011 Cook-Off 4問目
Problem Statement

問題概要

N個の的が一直線上に並んでいる. (Nは18以下)
1回の射撃で,的がある場所,もしくは,もう倒れたけど的があった場所を狙うことができる.
その際に,狙った的の左の的,狙った的,狙った的の右の的,に当たる確率が与えられる.(2つ以上離れた場所に当たる確率は0)
すべての的を倒すための必要な射撃数の最小値の期待値を求める問題.

解法

ビットDP.ただし,O(N*2^N)ではTLEで通らない.
2つ以上連続して的が倒れてる場所があると2つの部分問題に別れることを利用するとO(fib[N])になる.fibはフィボナッチ数.
他にも,対称性なども利用して状態数を減らす.
今ある最も右の的の,さらに右を狙うことが可能かどうか,などを新しく状態に加えた.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int n;
double L, S, R;
double dp[2][2][273333];

int mx[273333];
int per[273333][2];

void init(void){
  int i,j,k;

  rep(i,1<<18){
    k = 0;
    rep(j,18) if(i&1<<j) k = j;
    mx[i] = k;

    per[i][0] = -1;
    REP(j,1,mx[i]) if(!(i&1<<j)) if(!(i&1<<(j-1))){
      per[i][1] = (i>>(j+1));
      per[i][0] = i^(per[i][1]<<(j+1));
      break;
    }
  }
}

double solve(int fgL, int fgR, int mask){
  int i,j,k,ss;
  double res, tmp, dame, tt;

  if(dp[fgL][fgR][mask] >= -1) return dp[fgL][fgR][mask];
  if(mask==0) return dp[fgL][fgR][mask] = 0;

  if(mask%2==0){
    res = solve(1, fgR, mask/2);
    return dp[fgL][fgR][mask] = res;
  }

  if(per[mask][0] >= 0){
    res  = solve(fgL, 1, per[mask][0]);
    res += solve(1, fgR, per[mask][1]);
    return dp[fgL][fgR][mask] = res;
  }
  
  res = 1e100;
  REP(i,-fgL,mx[mask]+1+fgR){
    dame = 0;
    tmp = 0;
    
    if(i-1 <  0 || !(mask&(1<<(i-1))) ){
      dame += L;
    } else {
      if(i-1 == mx[mask]) ss = 1; else ss = fgR;
      tt = solve(fgL,ss,mask^(1<<(i-1)));
      tmp += L * ( 1.0 + tt );
    }
    
    if(            !(mask&(1<<(i  ))) ){
      dame += S;
    } else {
      if(i   == mx[mask]) ss = 1; else ss = fgR;
      tt = solve(fgL,ss,mask^(1<<(i  )));
      tmp += S * (1.0 + tt);
    }

    if(i+1 >=n || !(mask&(1<<(i+1))) ){
      dame += R;
    } else {
      if(i+1 == mx[mask]) ss = 1; else ss = fgR;
      tt = solve(fgL,ss,mask^(1<<(i+1)));
      tmp += R * (1.0 + tt);
    }
    
    if(dame > 1 - 1e-9) continue;
    tmp = (tmp + dame) / (1 - dame);
    if(res > tmp) res = tmp;
  }

  return dp[fgL][fgR][mask] = res;
}

int main(){
  int i,j,k,l,m;
  int size;
  double res;

  init();

  scanf("%d",&size);
  while(size--){
    scanf("%d",&n);
    scanf("%lf%lf%lf",&L,&S,&R);
    L/=100; S/=100; R/=100;

    rep(j,2) rep(k,2) rep(i,(1<<n)) dp[j][k][i] = -100;

    res = solve(0,0,(1<<n)-1);
    printf("%.6lf\n",res);
  }


  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2120-e795b3b8
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。