AtCoderの Typical DP Contestを解いてみた (C トーナメント) - プログラミング初心者の勉強日記

C トーナメント
- 問題の概要
解法
ソース

今回もTypical DP Contestのアウトプットに関する記事です.

今回解いた問題はC トーナメントです

前回までの記事は以下の通りです.

C トーナメント

今回は「C トーナメント」という問題を解きました.

問題の概要

(問題自体はAtCoderで確認してください.)

$2^{K}$ 人が参加するトーナメントがあり、以下の形式で試合を行う.

1回目は1と2, 3と4, ... が試合を行う.
2回目は (1と2の勝者) と (3と4の勝者), ... が試合を行う.
以下同様にK回行う.

K回後に優勝者が決定する. $i$ が優勝する確率を求めよ.

ただし、各人には強さが定義されていて $i$ の強さは $R_{i}$ である.

$i$ と $j$ が戦ったときに、 $i$ が勝つ確率は

$$ F(i, j) = \frac{1}{(1 + \frac{10^{R_j - R_i}}{400})} $$

と定義される.

解法

$dp[i][j]$ : $i$ が $j$ 試合連続で勝ち続ける確率

最終的な出力は $dp[i][K]$ です. ( $i = 0 \cdots 2^{K} - 1$ )

(全プレイヤーの優勝 (K連勝) する確率を出力することを求められているので)

DPの漸化式は以下の通りです.

$$ dp[i][j] = dp[i][j - 1] * \sum_{k \in S} F(i, k) $$

ただし、 $j$ 試合目に $i$ と戦うことができる相手の集合を $S$ とします.

例えば、1試合目に1と戦うことができる相手の集合は $S = \{2\}$ です.

また、2試合目に1と戦うことができる相手の集合は $S = \{3, 4\}$ です.

さらに、 $F(i, k)$ は上で定義された $i$ が $k$ に勝つ確率です.

ここまでは、普通のDPと同じです.

しかし、今回はトーナメントなので、戦う相手に制限があります. (誰とでも戦えるわけではありません.)

要は集合 $S$ をどうするかが少し工夫がいるところです.

今回はビット演算を用いた方法で $i$ が $j$ 試合目に戦う相手であるかどうかを判別する方法を紹介します.

(ビット演算の使い方についてはQiitaのページが非常に参考になります.

(DPの記事も書いてくださった人っぽくてほんとお世話になりっぱなしです...)) qiita.com

具体例として、参加者が8人とします.

各参加者に割り当てられた番号を2進数に変換します. (便宜上0番目から数えることにします)

$0 : 000\\ 1 : 001\\ 2 : 010\\ 3 : 011\\ 4 : 100\\ 5 : 101\\ 6 : 110\\ 7 : 111$

1試合目は(0, 1), (2, 3), (4, 5), (6, 7)が戦います.

これらは1bit目が異なり2bit目以降は一致しています.

したがって、右に1bitシフトすると1試合目に戦うプレイヤー同士のbit列は一致します. (例えば、2と3はそれぞれ右に1bitシフトすると001となる)

2試合目についても考えてみます.

2試合目は(0, 2 or 3), (1, 2 or 3), (2, 0, or 1), (3, 0 or 1), (4, 6 or 7), (5, 6 or 7), (6, 4 or 5), (7, 4 or 5)が戦います.

これらは2bit目が異なり3bit目以降が一致します. (1bit目は無視)

例えば、(0, 2 or 3)をみてみると、

$000\\ 010 \, or \, 011$

です.

0と2, 0と3のどちらをみても2bit目が異なり3bit目以降が一致しています.

したがって、右に2bitシフトすると2試合目に戦うプレイヤー同士のbit列は一致します.

ただし、一個前の試合で戦った相手とは戦うことができないので、右に1bitシフトしたときに一致したプレイヤー同士は無視します. (0と1も2bit右シフトすると000で一致するが、1試合目で戦っているので無視する)

一般化すると、

$i\mbox{と}k\mbox{が}j\mbox{試合目で戦う} = \\ \{ i\mbox{と}k\mbox{を}j\,bit\mbox{右シフトしたものが一致する}\} \cap \{i\mbox{と}k\mbox{を} \,j-1 \, bit\mbox{右シフトしたものが一致しない}\}$

で表すことができます. (多分)

C++でこれを実装すると

(i >> j) == (k >> j)

が $j$ bitシフトしたときに一致しているかを判別していて、

(i >> (j - 1) != (k >> (j - 1))

が一つ前の試合で戦った相手は無視していることに相当します.

これらをまとめると

if((i >> j) == (k >> j) && (i >> (j - 1)) != (k >> (j - 1))) 勝率の計算

となります.

ソース

使用言語はC++です.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

double returnProbability(int rp, int rq) {
    return (double)(1.0 / (1.0 + pow(10.0, (rq - rp) / 400.0)));
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K;
    cin >> K;
    int p = pow(2, K);
    int R[p];
    rep(i, 0, p) cin >> R[i];

    double dp[p + 1][K + 1];
    rep(i, 0, p + 1) rep(j, 0, K + 1) dp[i][j] = 0;
    rep(i, 0, p + 1) dp[i][0] = 1;

    rep(j, 1, K + 1) {
        rep(i, 0, p + 1) {
            double tmp = 0;
            rep(k, 0, p) {
                if((i >> j) == (k >> j) && (i >> (j - 1)) != (k >> (j - 1))) tmp += returnProbability(R[i], R[k]) * dp[k][j - 1];
            }
            dp[i][j] = dp[i][j - 1] * tmp;
        }
    }

    rep(i, 0, p) cout << dp[i][K] << endl;

}