Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

April 2011 Cook-Off 1問目 - The Grand Cook Off (この記事を編集する[管理者用])

Source

codechef April 2011 Cook-Off 1問目
Problem Statement
codechef April 2011 Cook-Offの参加記録

問題概要

N人のシェフがそれぞれ持っているコインの数 a[k] が与えられる.
毎ターン,コインを持ってるシェフをランダムに2人選んで戦わせる.
勝った方が,負けた方のコインを総取りできる.
最終決戦時の2人の所持コインの差の期待値を求める問題.
コインの数の和は100以下.

解法

結局2つのグループに分けて,それぞれのグループのコインの総和の差の期待値を求めれば良い.
片方のグループが1人~N-2人になる確率は等確率であることが確かめられる.
後は,今まで着目した人数と,片方のグループの人数と,現在のグループ間のコインの和の差,を状態にして,その状態に遷移するパターンが難パターンあるかをDPで数え上げれば良い.
O(N^2*C)程度.Cはコイン総和.

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)

#define UP 115

double ab(double x){if(x>0) return x; return -x;}

int main(){
  int i,j,k,l,m,n,a,b;
  int in[120];
  double dp[130][230], next[130][230];
  int size;
  double res, per, pp, rr;
  
  scanf("%d",&size);
  while(size--){
    scanf("%d",&n);
    rep(i,n) scanf("%d",in+i);

    rep(i,130) rep(j,230) dp[i][j] = 0;
    dp[0][UP] = 1;

    rep(k,n){
      rep(i,130) rep(j,230) next[i][j]=0;

      rep(i,130) rep(j,230) if(dp[i][j] > 0.1){
        next[i+1][j+in[k]] += dp[i][j];
        next[i  ][j-in[k]] += dp[i][j];
      }
      
      rep(i,130) rep(j,230) dp[i][j] = next[i][j];
    }

    res = per = 0;

    REP(i,1,n){
      rr = pp = 0;
      rep(j,230){
        rr += dp[i][j] * ab(j-UP);
        pp += dp[i][j];
      }
      res += rr/pp;
      per += 1;
    }
    res /= per;
    printf("%.6lf\n",res);
  }


  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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