解説 | Tournament Cards

解説

2つのDPを更新して求めます。

dp_byBattle[試合ID]：その試合終了時に、試合の勝者が持っている可能性のあるカードの数の集合
dp_byWinner[試合ID][その試合の勝者]：試合で(その試合の勝者)が勝ったとき、持っている可能性のあるカードの数の集合

計算量はO( $2^NNM^2$ )ですが、持っている数の集合をbitsetで持ち、いわゆる64倍高速化を行うことで、時間制限に間に合います。

数の集合を2進数に変換する方法

数の集合を以下のように2進数に変換します。

集合 $\{B_1, B_2, \cdots, B_k\}$ を、 $2^{B_1}+2^{B_2}+2^{B_k}$ に変換する。
例えば、{0, 2, 5}は $100101_{(2)}$ に変換する。

試合後に持っている可能性のあるカードの数の集合の更新方法

集合 $\{B_1, B_2, \cdots B_k\}$ と集合 $\{C_1, C_2, \cdots C_l\}$ を持っており、前者が勝利した場合、前者は集合 $\{2B_1+C_1, 2B_1+C_2,\cdots, 2B_1+C_N, 2B_2+C_1 + 2B_2 + C_2, \cdots, 2B_k + C_l\}$ の重複を除いたものを持ちます。

貪欲に行ってもこの更新の計算量はO( $M^2$ )ですが、bitsetを用いた高速化を行います。

簡単にするため、勝者のもつ集合の各要素をあらかじめ2倍に変換しておく。
集合Bを2進数に変換したものを $B_{bit}$ 、集合Cを2進数に変換したものを $C_{bit}$ とする。
変換結果を表す変数 $result$ を用意し、0で初期化する。
$0 \leq i < M$ について、 $C_{bit}$ の $i$ bit目が1であれば、 $result$ を $result$ | ( $B_{bit}$ を $i$ 回左シフトした値、B桁目以降は0桁目へローテートする)で更新する。

実装例（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87#include <iostream>
#include <bitset>
#include <vector>
using namespace std;
using ll = long long;
using BIT = bitset<109>;

ll N, M;

void bitShift(BIT& b){
    b <<= 1;
    if(b.test(M)){
        b.reset(M);
        b.set(0);
    }
}

BIT times2(BIT x){
    BIT result = 0;
    for(int i = 0; i < M; ++i){
        if(x.test(i)){
            result.set((2 * i) % M);
        }
    }
    return result;
}

BIT prod(BIT x, BIT y){
    BIT result = 0;
    for(int i = 0; i < M; ++i){
        if(y.test(i)){
            result |= x;
        }
        bitShift(x);
    }
    return result;
}

int main() {
    cin >> N >> M;
    ll cntPlayer = 1 << N;
    vector<ll> A(cntPlayer);
    for(int i = 0; i < cntPlayer; ++i){
        cin >> A.at(i);
    }
    vector<BIT> dp_byBattle(2 * cntPlayer, 0);
    vector<vector<BIT>> dp_byWinner(N + 1, vector<BIT>(cntPlayer, 0));
    
    for(int i = 0; i < cntPlayer; ++i){
        dp_byWinner.at(N).at(i).set(A.at(i));
        dp_byBattle.at(cntPlayer + i).set(A.at(i));
    }

    for(int i = cntPlayer - 1; i >= 1; --i){
        dp_byBattle.at(i) |= prod(times2(dp_byBattle.at(2 * i)), dp_byBattle.at(2 * i + 1));
        dp_byBattle.at(i) |= prod(dp_byBattle.at(2 * i), times2(dp_byBattle.at(2 * i + 1)));
    }

    for(int i = N - 1; i >= 0; --i){//ステージ数(逆から)
        int cntBattle = 1 << i;
        for(int j = 0; j < cntBattle; ++j){//対戦
            for(int k = 0; k < cntPlayer / cntBattle; ++k){//対戦での勝利者
                int id = j * (cntPlayer / cntBattle) + k;
                if(k < cntPlayer / cntBattle / 2){//対戦で左側
                    dp_byWinner.at(i).at(id) |= prod(times2(dp_byWinner.at(i + 1).at(id)), dp_byBattle.at(2 * ((1 << i) + j) + 1));
                }else{//対戦で右側
                    dp_byWinner.at(i).at(id) |= prod(times2(dp_byWinner.at(i + 1).at(id)), dp_byBattle.at(2 * ((1 << i) + j)));
                }
            }
        }
    }

    for(int i = 0; i < cntPlayer; ++i){
        vector<int> ans;
        for(int j = 0; j < M; ++j){
            if(dp_byWinner.at(0).at(i).test(j)){
                ans.push_back(j);
            }
        }
        cout << (int)ans.size();
        for(int e : ans){
            cout << " " << e;
        }
        cout << endl;
    }
    return 0;
}

難易度評価

外部サイトへ移動します

Tournament Cards

解説

ユーザー解説