結果

問題 No.3586 Divide and Be Conquered
コンテスト
ユーザー marc2825
提出日時 2026-05-30 09:21:19
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 68 ms / 2,000 ms
コード長 2,862 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,546 ms
コンパイル使用メモリ 231,516 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2026-07-10 20:57:43
合計ジャッジ時間 2,966 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int value(ll x) {
    if (x == 3) return 2;
    ll r = x % 5;
    if (r == 2 || r == 3) return 1;
    return 0;
}

bool solve_main(vector<ll> A) {
    int xr = 0;
    for (ll x : A) {
        xr ^= value(x);
    }
    return xr != 0;
}

vector<int> normalize(vector<int> v) {
    sort(v.begin(), v.end());
    return v;
}

map<vector<int>, bool> memo;

bool solve_bruteforce(vector<int> state) {
    state = normalize(state);

    if (memo.count(state)) return memo[state];

    int N = (int)state.size();

    bool has_move = false;
    for (int x : state) {
        if (x >= 2) has_move = true;
    }
    if (!has_move) return memo[state] = false;

    // 手番プレイヤーが山を1つ選ぶ
    for (int i = 0; i < N; i++) {
        int x = state[i];
        if (x < 2) continue;

        vector<int> rest = state;
        rest.erase(rest.begin() + i);

        bool this_heap_is_good = true;

        // 相手が分割を選ぶ
        for (int a = 1; a <= x - 1; a++) {
            int b = x - a;

            vector<int> next_a = rest;
            next_a.push_back(a);
            next_a = normalize(next_a);

            vector<int> next_b = rest;
            next_b.push_back(b);
            next_b = normalize(next_b);

            bool wa = solve_bruteforce(next_a);
            bool wb = solve_bruteforce(next_b);

            // 自分は a, b のどちらかを残せる。
            // どちらを残しても相手勝ちなら、この分割を相手に選ばれてダメ。
            if (wa && wb) {
                this_heap_is_good = false;
                break;
            }
        }

        if (this_heap_is_good) {
            return memo[state] = true;
        }
    }

    return memo[state] = false;
}

bool is_small_case(const vector<ll>& A) {
    if ((int)A.size() > 6) return false;
    for (ll x : A) {
        if (x > 10) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    assert(T >= 1);

    long long total_N = 0;

    while (T--) {
        int N;
        cin >> N;

        assert(N >= 1);

        vector<ll> A(N);
        for (int i = 0; i < N; i++) {
            cin >> A[i];
            assert(1 <= A[i] && A[i] <= (ll)1e18);
        }

        total_N += N;
        assert(total_N <= 200000);

        bool ans_main = solve_main(A);
        bool ans = ans_main;

        if (is_small_case(A)) {
            vector<int> B(N);
            for (int i = 0; i < N; i++) {
                B[i] = (int)A[i];
            }

            memo.clear();
            bool ans_brute = solve_bruteforce(B);

            assert(ans_brute == ans_main);

            ans = ans_brute;
        }

        cout << (ans ? "First" : "Second") << '\n';
    }

    return 0;
}
0