zkx06111's Blog

博弈论杂题

| Comments

整理一下博弈论的题目...另外Logdown的翻译实在大赞...博弈论杂题翻译成game theory ad hoc problems有点强啊。

T-Shirts (RCC2016 2nd Qualification Round)

比赛的名字是不是有一种“阿CC”的感觉呢...有n件T恤,有3个人,每个人对于n件T恤的喜好都不同。用一个1 .. n的排列表示,越靠前表示越喜欢。

从第一个人开始,3人轮流在1..n中删去数字,每个人都会采取最优策略,使得最后剩下的T恤是自己最喜欢的。

数据范围:数据组数T <= 50, n <= 13。

比较小,使用状压dp。表示剩下的T恤集合为,轮到第个人删去T恤时得到的T恤。

依照题意转移,即

t-shirts.cc
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
#define REP(i, a, b) for (int i = a; i <= b; ++i)
using namespace std;

typedef long long LL;
LL read(){
    LL x = 0; int f = 1, ch = getchar();
    while (ch < '0' || ch > '9'){if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

int T, A[4][15], B[4][15], f[15][1 << 15], n;

int bc(int x){
    int res = 0;
    for (int i = 0; i < 15; ++i)
        if (x & (1 << i)) ++res;
    return res;
}

int solve(int p, int state){
    if (bc(state) == 1){
        for (int i = 0; i < 15; ++i)
            if (state & (1 << i)) return i + 1;
    }
    if (f[p][state] != -1) return f[p][state];
    int t = p + 1;
    if (t > 3) t = 1;
    for (int i = 0; i < 15; ++i)
        if ((state & (1 << i)) && (f[p][state] == -1 || A[p][solve(t, state ^ (1 << i))] > A[p][f[p][state]]))
            f[p][state] = solve(t, state ^ (1 << i));
    return f[p][state];
}

int main(){
    T = read();
    while (T--){
        memset(f, -1, sizeof f);
        n = read();
        REP(j, 1, 3) REP(i, 1, n) B[j][i] = read();
        REP(j, 1, 3) REP(i, 1, n) A[j][B[j][i]] = n - i;
        printf("%d\n", solve(1, (1 << n) - 1));
    }
    return 0;
}

Landlords (XJOI NOI模拟题 559)

有一副牌,每张不同。一人n张,一人m张。在桌上还有一张。

游戏轮流操作,操作有两种:

  • 猜测 猜测桌上有什么牌,猜对获胜,猜错失败。游戏立即结束。
  • 指定 指定一张牌,问对方有没有,若有,对方弃掉该牌,若无,对方回复“无”。

现在给出n, m (n, m <= 1000),求双方都使用最优策略,先手获胜的概率。

令答案为,其中有张牌的先手,暂时叫他小明。此时有3种决策。

  1. 直接猜测,在不在小明手上的张牌中随机选择一张猜测,获胜概率为
  2. 指定一张不在小明手上的牌。这时有两种情况,分别求概率相加:
    • 那张牌在桌上,那么只要对方不猜测这张牌,下一次轮到小明时,他只要猜测这张牌即可。设对方把这张牌不当作桌上牌的概率为,那么获胜的概率即为
    • 那张牌不在桌上,在对方手上,那么就转化为了一个子问题,获胜的概率为
  3. 指定一张在小明手上的牌。一定不在对方手上,对方的反应有两种情况,分别求概率相加:
    • 对方不猜测这张牌。注意到:不管那张牌是在桌上还是在小明手里,对于对方来说都是不在他手里,所以对方不把这张牌当作桌上牌的概率和前面提到的一样,是,那么获胜的概率转化为子问题,为
    • 对方猜测这张牌。那么小明就赢了,获胜概率为

下面最妙的来了,把不在对方手里的牌不当做桌上的牌的概率,是对方决定的。为了获胜,自然要选择使小明的获胜概率最小。假设已经有了最优策略,那么因为小明很聪明,他是可以知道而根据它来选择胜率最大的决策的。所以,对方决定的,要使得小明无论怎样决策,产生的最大胜率最小!

小明的三个决策,获胜概率和的关系分别是常函数,递增的一次函数和递减的一次函数,所以在两个一次函数交点和常函数比较较低处取最大值最小。

于是乎求出这个值即可计算。复杂度

landlords.cc
#include <bits/stdc++.h>
using namespace std;
 
int n, m;
double f[1005][1005];
 
double solve(int n, int m){
    if (f[n][m] > -0.5) return f[n][m];
    if (n == 0) return f[n][m] = 1.0 / (m + 1);
    if (m == 0) return f[n][m] = 1.0;
    double k1 = 1.0 / (m + 1), b1 = 1.0 * m / (m + 1) * (1 - solve(m - 1, n));
    double k2 = -solve(m, n - 1), b2 = 1;
    return f[n][m] = max(1.0 / (m + 1), (b1 * k2 - b2 * k1) / (k2 - k1));
}
 
int main(){
    memset(f, -1, sizeof(f));
    scanf("%d%d", &n, &m);
    printf("%.10f %.10f\n", solve(n, m), 1 - solve(n, m));
    return 0;
}

Fibonacci Again and Again (HDOJ 1848)

有三堆石子,每次可以从任意一堆中取走斐波那契数个石子,求先手必胜还是必败。

这类问题可以归约到:对于一个有向无环图,一枚棋子在上面移动,如果移到不能移算输,求先手必胜还是必败。

一个状态的SG函数,其中mex指的是minimal excludant。意思就是对于所有x的后继状态的sg函数组成的集合,不在集合中的最小数字。

这有个什么好呢?

  1. 终点的函数值为0 - 移到不能移算输。
  2. 如果一个节点的函数值为0,那么它的所有后继函数值都非0 - 必败态的所有后继都必胜。
  3. 如果一个节点的函数值非0,那么它的某个后继函数值为0 - 只要有一个后继是必败,那么当前状态为必胜。

那么SG函数是否为0就与必胜必败对应起来了。

更妙的是,多个这样的游戏状态的SG函数的值是各自函数值异或起来。那么一个较为复杂的游戏就可以拆分成几个游戏的和的形式。

这道题可以拆分成3个取1堆石子的游戏,求出有x个石子的SG函数,对于给出的3堆的石子个数,把SG值异或起来看是否为0即可。

fibo.cc
#include <cstdio>
#include <cstring>
#define REP(i, a, b) for (int i = a; i <= b; ++i)
using namespace std;

int m, n, p, f[25], sg[1005], bo[1005];

void getSG(){
    memset(sg, 0, sizeof sg);
    REP(i, 1, 1000){
        memset(bo, 0, sizeof bo);
        for (int j = 1; f[j] <= i; ++j)
            bo[sg[i - f[j]]] = 1;
        for (int j = 0; ;  ++j) if (bo[j] == 0){
            sg[i] = j; break;
        }
    }
}

int main(){
    f[1] = 1, f[2] = 2;
    REP(i, 3, 20) f[i] = f[i - 1] + f[i - 2]; 
    getSG();

    scanf("%d%d%d", &m, &n, &p);
    while (m != 0){
        if ((sg[m] ^ sg[n] ^ sg[p]) == 0) printf("Nacci\n");
        else printf("Fibo\n");
        scanf("%d%d%d", &m, &n, &p);
    }
    return 0;
}

Comments

comments powered by Disqus