AtCoder-Typical DP Contest C問題をやりました

プログラミング 備忘録

C問題もやりました。
以下問題文
C: トーナメント - Typical DP Contest | AtCoder

Problem Statement
2K 人が参加するトーナメントがある。このトーナメントでは以下の形式で試合を行う。

第 1 ラウンドでは、1 と 2、3 と 4、…　が試合を行う。
第 2 ラウンドでは、(1 と 2 の勝者) と (3 と 4 の勝者), (5 と 6 の勝者) と (7 と 8 の勝者), …　が試合を行う。
第 3 ラウンドでは、((1 と 2 の勝者) と (3 と 4 の勝者) の勝者) と ((5 と 6 の勝者) と (7 と 8 の勝者) の勝者), ((9 と 10 の勝者) と (11 と 12 の勝者) の勝者) と ((13 と 14 の勝者) と (15 と 16 の勝者) の勝者), …　が試合を行う。
以下同様に第 K ラウンドまで行う。

第 K ラウンドの終了後に優勝者が決定する。人 i の Elo Rating が Ri であるとき、人 i の優勝確率を求めよ。

ただし、Elo Rating RP の人 P と Elo Rating RQ の人 Q が対戦した場合、人 P が勝つ確率は 1⁄(1+10(RQ−RP)⁄400) であり、異なる試合の勝敗は独立であるとする。
Constraints

1≤K≤10
0≤Ri≤4000

Input Format
入力は以下の形式で標準入力から与えられる。

K
R1
…
R2K

Output Format
答えを 2K 行出力せよ。i 行目は人 i が優勝する確率であり、絶対誤差が 10−6 以下のとき正当と判定される。

書いたソースは続きから↓

#include<stdio.h>
#include<math.h>
double dp[11][1025];
int K;
int R[1025];

//p,qが対戦してpが勝つ確率
double Elocalc(int P,int Q)
{
  return 1.0000/(1.0000 + pow(10,(double)(Q-P)/400.0000));
}
//nは1人目から0からはじめる
double DP(int k,int n)
{
  if(dp[k][n] >= 0)
    return dp[k][n];
  int digit=1,i,num;
  for(i=0;i<k-1;i++)
    digit <<= 1;
  num = digit ^ n;
  for(i=0;i<k-1;i++)
    num = (~(1 << i))&num;
  dp[k][n] = 0;
  for(i=0;i<digit;i++,num++)
    dp[k][n] += DP(k-1,n)*DP(k-1,num)*Elocalc(R[n],R[num]);
  return dp[k][n];
}

int main()
{
  int i,j,k;
  for(k=0;k<11;k++)
    for(i=0;i<1025;i++)
      if(k==0)
        dp[k][i] = 1;
      else
        dp[k][i] = -1;
  scanf("%d",&K);
  for(i=0;i<(int)(pow(2,K) + 0.5);i++)
    scanf("%d",&R[i]);
  for(i=0;i<(int)(pow(2,K) + 0.5);i++)
    printf("%.9lf\n",DP(K,i));
  return 0;
}

今回は確率の問題となっており、若干の数学の知識が求められます。
その知識があれば漸化式を立てるのはさほど困難ではありません。まずDPを定義します。
DP[k][n] = (n番目の参加者がk番目の試合に勝つ確率)
としておきます。ただし、このnには0を含めることとし、0番目にも参加者がいます。こうしておくと都合がいいです。
漸化式は、

DP[k][n] = Σ(s∈S) (DP[k-1][n] * DP[k-1][s] * EloRate(n,s))
(S は k回戦目にnが戦う可能性のある全ての相手。EloRate(n,s)はnがsに勝つ確率を表し、標準入力により与えられた定数によって計算できる。)
また
DP[0][n] = 1 (1回戦目には必ず出場できるので、0回戦目の勝率は1。定義しなくてもいいが、こうしておくと都合がよく、実装にあたっての場合分けの必要がない。)

DPの定義から、上のような漸化式が導かれます。この漸化式は難しい発想ではないのですが、実装にあたって、上の集合S={k回戦目にnが戦う可能性のある全ての相手}をどのようにして選ぶか（計算するか）がなかなか難しいです。k回戦目に戦う可能性のある相手の数が2^(k-1)人いると考えると、ループを回す回数は2^(k-1)回で良さそうです。また、k回戦目に戦う可能性のある集合と、その集合と戦う集合はトーナメント表上で隣接しています。自分の番号から相手の集合の番号を指すには、番号を足す場合と、引く場合があり、その操作は対になっていると考えられます。ここで思い浮かぶのが、2進数表記でのビット反転です。例えば7の2進数表記は0111で、１回戦で戦う相手は6(0110)です((0,1),(2,3),(4,5),(6,7)....となるので)。2回戦目で戦う相手は2人いることになりますが、2ビット目を反転して1ビット目を0と1に変化させると、5(0101)と4(0100)となります。同じようにして
3ビット目を反転して1ビット目から2ビット目までを変化...としていくと、同じように4人までの対戦相手を指すことができます(2*2の4通り)。このようにしてk回戦目のときにnのkビット目を反転させ、k-1ビット以下に0を敷き詰め、2^(k-1)回1を足しながらループを回すとすべての対戦相手を指すことができます。k-1ビット以下に0を敷き詰めるいい方法が思いつかなかったので、1をi回ビットシフトさせてから全ビットを反転させ、それをnと論理和したものをnに代入、というのをk-1ビットまでやっています。

DPはいったん切り上げて
カメラを買ったので画像処理のプログラムでも書きたいと思います