たくあんポリポリ

勉強したことを載せていきます。( 主に、C#/ Algorithm / AtCoder / Unity / 最近はKaggleとPython )

【AtCoder】【C#】Typical DP Contest - C - トーナメント

f:id:c_taquna:20200115005201p:plain

Typical DP Contest - C - トーナメント を解いたので勉強のメモを残しておこうと思います。

はじめに

本記事のテーマ

Typical DP Contest - C - トーナメントの解説記事ですが、解法については下記リンクを参照していただければと思います。この記事では下記に書かれているbit演算子に関する処理の部分についてもう少し詳細に見ていきたいと思います。

tutuz.hateblo.jp

問題へのリンク

atcoder.jp

本題

実装

まずはC#で実装しなおしたので全体を載せておきます。

static void Main(string[] args)
{
    int K = int.Parse(Console.ReadLine());
    int X = (int)Math.Pow(2, K);
    double[] R = new double[(int)Math.Pow(2, K)];
    for (int i = 0; i < X; i++)
    {
        R[i] = double.Parse(Console.ReadLine());
    }
    double[,] P = new double[X, X];
    for (int i = 0; i < X; i++)
    {
        for (int j = 0; j < X; j++)
        {
            P[i, j] = 1.0 / (1.0 + Math.Pow(10, (R[i] - R[j]) / 400.0));
        }
    }
    double[,] DP = new double[X + 10, K + 10];
    for (int i = 0; i < X; i++)
    {
        DP[i, 0] = 1.0;
    }
    for (int k = 0; k <= K; k++)
    {
        for (int x = 0; x < X; x++)
        {
            int b = (x >> k) << k;
            for (int j = b; j < b + (1 << k); j++)
            {
                if ((x >> (k - 1) & 1) == (j >> (k - 1) & 1)) continue;
                DP[x, k] += DP[x, k - 1] * DP[j, k - 1] * P[j, x];
            }
        }
    }
    for (int i = 0; i < X; i++)
    {
        Console.WriteLine(DP[i, K]);
    }
}

実装リンク github.com

bit演算の処理部分について

全体の実装から抜き出してみてみます。

for (int k = 0; k <= K; k++)
{
    for (int x = 0; x < X; x++)
    {
        int b = (x >> k) << k;
        for (int j = b; j < b + (1 << k); j++)
        {
            if ((x >> (k - 1) & 1) == (j >> (k - 1) & 1)) continue;
            DP[x, k] += DP[x, k - 1] * DP[j, k - 1] * P[j, x];
        }
    }
}

考え方

下記トーナメント表にて、5が2(k = 2)回戦で戦う相手は、先頭から(bitの桁数 - k)bitが同じ値となっている相手です。この場合、bitの桁数=4k=2なので先頭から2bit同じものが対象なので、下の図から 4,6,7が該当することがわかります。

ですが、4は2回戦で戦うことはないので除外します。これをまとめると、先頭から2bitが同じであるかつ、下2(k=2)bitが異なる相手と戦うとなります。

一旦、まずは先頭の2bitを変えずに下2bitを0にするような処理をしましょう。ここで求めた値をbaseと呼ぶことにします。(実装だと int b で定義)

f:id:c_taquna:20200204233221j:plain:w400

下2(k=2)bitが異なるということなので、今回は、i >> k してから、また i << k しています。

int b = (x >> k) << k;

これが何をしているかというと、下記の様に2bit右シフトさせてから2bit左シフトすることで先頭の2bitをそのままに下2bitを0にしています。この値がbase(コード上は int b)です。 f:id:c_taquna:20200204233815j:plain:w400

トーナメントの性質上、1回戦ごとにプレイヤーが2人増えていくので、このbaseからbase + (1 << k) の範囲で処理をまわします。ただ、同じブロックの相手との戦いは計算する必要がないのでk-1までのbitが同じ相手の時は処理を飛ばしています。

for (int j = b; j < b + (1 << k); j++)
{
    if ((x >> (k - 1) & 1) == (j >> (k - 1) & 1)) continue;
    DP[x, k] += DP[x, k - 1] * DP[j, k - 1] * P[j, x];
}

感想

最後はすっとばしましたが、これでACできます。ただでさえややこしいDPにbit演算を含めるとさらにややこしくなりますが、緑に上がってキープしてさらには水色を目指すのであれば両方とも必須だと思うので、こういったところでなれておくのも良いかなと思います