Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

October 2012 Cook-Off 4問目 - Tennis Tournament (この記事を編集する[管理者用])

Source

codechef October 2012 Cook-Off 4問目
Problem Statement

問題概要

N = 2^K人の人でトーナメント戦をする.Kは30以下.
M人(10000以下)特殊能力者な人がいる.
特殊能力者の位置と,特殊能力者がそうじゃない人に勝つ確率(一律)が与えられる.
特殊能力者同士,そうじゃない者同士は勝率0.5.
特殊能力者が優勝する確率を求める問題.

解法

再帰.
各対戦について,左のツリーから特殊能力者が勝ち上がってくる確率,右のツリーから特殊能力者が勝ち上がってくる確率を求めていく.
範囲に特殊能力者がいない場所は,即座に0とすれば,O(K*M)ぐらいで解ける.

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

void intSort(int d[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}intSort(d,i);intSort(d+j+1,s-j-1);}

double solve(int M, int A[], int N, double P){
  int i, j, k;
  int M1, M2;
  double res = 0;
  double left, right;

  if(M==0) return 0;
  if(N==1) return 1;

  rep(i,M) if(A[i] >= N/2) break;
  M1 = i;
  M2 = M-i;
  REP(i,M1,M) A[i] -= N/2;

  left = solve(M1, A, N/2, P);
  right = solve(M2, A+M1, N/2, P);

  res += left * right + left * (1-right) * P + (1-left) * right * P;

  return res;
}

int main(){
  int N, M, P, A[12000];
  int T;

  int i, j;
  double res;

  scanf("%d",&T);
  while(T--){
    scanf("%d%d%d",&N,&M,&P);
    rep(i,M) scanf("%d",A+i), A[i]--;
    intSort(A, M);

    res = solve(M, A, N, P/100.0);

    printf("%.15f\n",100*res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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