結果

問題 No.102 トランプを奪え
コンテスト
ユーザー ふーらくたる
提出日時 2016-07-18 03:47:07
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 600 ms / 5,000 ms
コード長 2,539 bytes
コンパイル時間 493 ms
コンパイル使用メモリ 57,376 KB
実行使用メモリ 27,136 KB
最終ジャッジ日時 2024-10-15 15:30:21
合計ジャッジ時間 2,433 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstring>
using namespace std;

const int kINF = 1 << 28;
const int kMAX_N = 15;
int N1, N2, N3, N4;

int dp[2][kMAX_N][kMAX_N][kMAX_N][kMAX_N][kMAX_N * 4];

int JudgeGame(int turn, int card1_num, int card2_num, int card3_num, int card4_num, int enemy_cards) {
    int& result = dp[turn][card1_num][card2_num][card3_num][card4_num][enemy_cards],
        used_cards = (N1 - card1_num) + (N2 - card2_num) + (N3 - card3_num) + (N4 - card4_num);

    if (result >= 0) {
        return result;
    }
    if (card1_num == 0 && card2_num == 0 && card3_num == 0 && card4_num == 0) {
        if (used_cards % 2 == 0 && enemy_cards == used_cards / 2) return result = 1;
        if (enemy_cards <= used_cards / 2) return result = 2;
        else return result = 0;
    }

    for (int c1_num = 0; c1_num <= min(3, card1_num); c1_num++) {
        for (int c2_num = 0; c2_num <= min(3, card2_num); c2_num++) {
            for (int c3_num = 0; c3_num <= min(3, card3_num); c3_num++) {
                for (int c4_num = 0; c4_num <= min(3, card4_num); c4_num++) {
                    bool can_rob = false;
                    int use_decks_num = (bool)c1_num + (bool)c2_num + (bool)c3_num + (bool)c4_num;
                    if (use_decks_num != 1) continue;
                    if (c1_num && card1_num - c1_num == 0) can_rob = true;
                    if (c2_num && card2_num - c2_num == 0) can_rob = true;
                    if (c3_num && card3_num - c3_num == 0) can_rob = true;
                    if (c4_num && card4_num - c4_num == 0) can_rob = true;

                    int draw_cards = c1_num + c2_num + c3_num + c4_num;
                    result = max(result, 2 - JudgeGame((turn + 1) % 2,
                                                       card1_num - c1_num,
                                                       card2_num - c2_num,
                                                       card3_num - c3_num,
                                                       card4_num - c4_num,
                                                       (used_cards - enemy_cards) + draw_cards + (can_rob ? (enemy_cards + 1) / 2 : 0)));
                }
            }
        }
    }
    return result;
}

int main() {
    cin >> N1 >> N2 >> N3 >> N4;

    memset(dp, -1, sizeof(dp));
    int result = JudgeGame(0, N1, N2, N3, N4, 0);
    if (result == 2) {
        cout << "Taro" << endl;
    } else if (result == 1) {
        cout << "Draw" << endl;
    } else {
        cout << "Jiro" << endl;
    }

    return 0;
}
0