srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.361 門松ゲーム2

問題

問題概要

省略

解法

grundy数をメモ化再帰で求めることにした。 この問題は竹が分裂していくが、竹が一個の時のgrundy数をxorとるだけで、複数のゲームが合わさった状態のgrundy数を考えることができる。蟻本p284に書いてある。
grundy数の求め方だが、
grundy数は
-負けの状態で0
-遷移先のGrundy数に含まれない最小の整数
なので、状態遷移先を列挙していき、最小のgrundy数を求めに行けばいい。

ミス

dp2次元にしてるけど、何の意味もないやんww

コード

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int dp[510][510];

int grundy(int L, int D){
    if(dp[L][D] != -1)return dp[L][D];

    set<int> s;
    for (int i = 1; i <= L; ++i){
        for (int j = i + 1; j <= L; ++j){
            int k = L - (i + j);
            if(k - i <= D && i < j && j < k){
                //状態遷移先
                s.insert(grundy(i, D) ^ grundy(j, D) ^ grundy(k, D));
            }

        }
    }

    int res = 0;
    while(s.count(res)) res++;
    return dp[L][D] = res;
}

int main(void){
    rep(i, 510)rep(j, 510) dp[i][j] = -1;
    int l, d; cin >> l >> d;
    if(grundy(l, d) == 0){
        printf("matsu\n");
    }else{
        printf("kado\n");
    }
    return 0;
}

これでいいよね。

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int dp[510];

int grundy(int L, int D){
    if(dp[L] != -1)return dp[L];

    set<int> s;
    for (int i = 1; i <= L; ++i){
        for (int j = i + 1; j <= L; ++j){
            int k = L - (i + j);
            if(k - i <= D && i < j && j < k){
                s.insert(grundy(i, D) ^ grundy(j, D) ^ grundy(k, D));
            }

        }
    }

    int res = 0;
    while(s.count(res)) res++;
    return dp[L] = res;
}

int main(void){
    rep(i, 510) dp[i] = -1;
    int l, d; cin >> l >> d;
    if(grundy(l, d) == 0){
        printf("matsu\n");
    }else{
        printf("kado\n");
    }
    return 0;
}