yukicoder No.361 門松ゲーム2

問題

No.361 門松ゲーム2 - yukicoder

解法

grundy 数やるだけです。
pekempey さんの記事がわかりやすいのでそれを参考にしましょう。今回使ったのは「山が分裂する場合の Grundy 数」です。
pekempey.hatenablog.com

const int MAXL = 555;
int g[MAXL], D;

int grundy(int L) {
    int& ret = g[L];
    if (ret >= 0) return ret;
    set<int> S;
    for (int l1 = 1; l1 < L/3; l1++) for (int l2 = l1+1; l2+l1 < L; l2++) {
        int l3 = L-l1-l2;
        if (l3 <= l2) break;
        if (l3-l1 > D) continue;
        int g1 = grundy(l1), g2 = grundy(l2), g3 = grundy(l3);
        S.insert(g1^g2^g3);
    }
    ret = 0;
    while (1) {
        if (S.find(ret) == S.end()) return ret;
        ret++;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int L;
    cin >> L >> D;
    memset(g, -1, sizeof(g));
    if (grundy(L) == 0) cout << "matsu" << endl;
    else cout << "kado" << endl;
    return 0;
}