結果

問題 No.437 cwwゲーム
ユーザー @abcde@abcde
提出日時 2019-04-20 18:15:43
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 103 ms / 2,000 ms
コード長 6,198 bytes
コンパイル時間 1,717 ms
コンパイル使用メモリ 170,228 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-20 13:23:59
合計ジャッジ時間 6,039 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
5,248 KB
testcase_01 AC 77 ms
5,376 KB
testcase_02 AC 86 ms
5,376 KB
testcase_03 AC 78 ms
5,376 KB
testcase_04 AC 79 ms
5,376 KB
testcase_05 AC 94 ms
5,376 KB
testcase_06 AC 97 ms
5,376 KB
testcase_07 AC 103 ms
5,376 KB
testcase_08 AC 88 ms
5,376 KB
testcase_09 AC 101 ms
5,376 KB
testcase_10 AC 99 ms
5,376 KB
testcase_11 AC 76 ms
5,376 KB
testcase_12 AC 77 ms
5,376 KB
testcase_13 AC 84 ms
5,376 KB
testcase_14 AC 83 ms
5,376 KB
testcase_15 AC 97 ms
5,376 KB
testcase_16 AC 81 ms
5,376 KB
testcase_17 AC 84 ms
5,376 KB
testcase_18 AC 83 ms
5,376 KB
testcase_19 AC 79 ms
5,376 KB
testcase_20 AC 79 ms
5,376 KB
testcase_21 AC 78 ms
5,376 KB
testcase_22 AC 77 ms
5,376 KB
testcase_23 AC 79 ms
5,376 KB
testcase_24 AC 78 ms
5,376 KB
testcase_25 AC 82 ms
5,376 KB
testcase_26 AC 82 ms
5,376 KB
testcase_27 AC 77 ms
5,376 KB
testcase_28 AC 79 ms
5,376 KB
testcase_29 AC 77 ms
5,376 KB
testcase_30 AC 80 ms
5,376 KB
testcase_31 AC 77 ms
5,376 KB
testcase_32 AC 75 ms
5,376 KB
testcase_33 AC 79 ms
5,376 KB
testcase_34 AC 79 ms
5,376 KB
testcase_35 AC 81 ms
5,376 KB
testcase_36 AC 77 ms
5,376 KB
testcase_37 AC 77 ms
5,376 KB
testcase_38 AC 78 ms
5,376 KB
testcase_39 AC 76 ms
5,376 KB
testcase_40 AC 81 ms
5,376 KB
testcase_41 AC 82 ms
5,376 KB
testcase_42 AC 90 ms
5,376 KB
testcase_43 AC 81 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// Use of dynamic bitset to convert decimal numbers.
// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers
// 10進数 → 2進数.
// @param n: 2進数へ変換したい10進数.
// @param d: 2進数表記する桁数.
// @return: 2進数.
string decimalToBinary(int n, int d) {

    // 1. ゼロの場合.
    string ret = "";
    if(n == 0){
        while(ret.size() < d) ret = "0" + ret;
        return ret;
    }
    
    // 2. ゼロでない場合.
    int ln = abs(n);
    do{
        ret = string((ln & 1) ? "1" : "0") + ret;
    }while((ln /= 2) > 0);
    while(ret.size() < d) ret = "0" + ret;
    
    // 3. 負数の場合.
    if(n < 0) ret = "-" + ret;
    return ret;

}

// 組み合わせnC3に対応する文字列を作成.
// ※ n が, 小さい時しか使えないので要注意.
// @param n: nC3 の n.
// @param l: 文字列長.
// @return: nC3 に対応する文字列.
set<string> makeCombinationBox(int n, int l){
    set<string> ret;
    for(int i = 0; i < l; i++){
        for(int j = i + 1; j < l; j++){
            for(int k = j + 1; k < l; k++){
                string a(l, '0');
                a[i] = a[j] = a[k] = '1';
                ret.insert(a);
            }
        }
    }
    return ret;
}

// CWW文字であるか判定.
// @param a0: 1文字目.
// @param a1: 2文字目.
// @param a2: 3文字目.
// @return: true … CWW文字である, false … CWW文字では無い.
bool checkCWW(char a0, char a1, char a2){
    if(a0 != '0' && a1 == a2 && a0 != a1) return true;
    else                                  return false;
}

int main() {
    
    // 1. 入力情報取得.
    string N;
    cin >> N;
    while(N.size() < 13) N = "0" + N;
    // cout << "N=" << N << endl;
    
    // 2. scoreの最大値を計算.
    // 13C3 * 10C3 * 7C3 * 4C3 = 286 * 120 * 35 * 4 = 4804800通り の 計算？
    // 2-1. 13C3, 10C3, 7C3, 4C3 の 情報を保存する箱の作成.
    set<string> c13_3 = makeCombinationBox(13, 13);
    set<string> c10_3 = makeCombinationBox(10, 10);
    set<string> c7_3 = makeCombinationBox(7, 7);
    set<string> c4_3 = makeCombinationBox(4, 4);
    // for(auto &p : c13_3) cout << p << endl;
    // for(auto &p : c10_3) cout << p << endl;
    // for(auto &p : c7_3) cout << p << endl;
    // for(auto &p : c4_3) cout << p << endl;

    // 2-2. 13C3, 10C3, 7C3, 4C3 の 情報を配列に変換.
    int a13_3[286][3];
    int a10_3[120][3];
    int a7_3[35][3];
    int a4_3[4][3];
    int r = 0;
    for(auto &p : c13_3){
        int c = 0;
        for(int i = 0; i < 13; i++) if(p[i] == '1') a13_3[r][c] = i, c++;
        r++;
    }
    r = 0;
    for(auto &p : c10_3){
        int c = 0;
        for(int i = 0; i < 10; i++) if(p[i] == '1') a10_3[r][c] = i, c++;
        r++;
    }
    r = 0;
    for(auto &p : c7_3){
        int c = 0;
        for(int i = 0; i < 7; i++) if(p[i] == '1') a7_3[r][c] = i, c++;
        r++;
    }
    r = 0;
    for(auto &p : c4_3){
        int c = 0;
        for(int i = 0; i < 4; i++) if(p[i] == '1') a4_3[r][c] = i, c++;
        r++;
    }    
    // for(int i = 0; i < 286; i++) cout << a13_3[i][0] << " " << a13_3[i][1] << " " << a13_3[i][2] << endl;
    
    
    // 2-3. CWW に 関する情報を取得し, 計算.
    int ans = 0;
    // 13C3通りの確認.
    for(int i = 0; i < 286; i++){
        int stock = 0;
        int cww13_3 = 0;
        string cwwI = N;
        if(checkCWW(cwwI[a13_3[i][0]], cwwI[a13_3[i][1]], cwwI[a13_3[i][2]])){
            cww13_3 = 100 * (cwwI[a13_3[i][0]] - '0') + 10 * (cwwI[a13_3[i][1]] - '0') + (cwwI[a13_3[i][2]] - '0');
            stock = cww13_3;
            // 最大値更新.
            ans = max(ans, stock);
        }
        // 文字列 cwwI を編集.
        cwwI.erase(a13_3[i][2], 1);
        cwwI.erase(a13_3[i][1], 1);
        cwwI.erase(a13_3[i][0], 1);
        
        // 10C3通りの確認.
        for(int j = 0; j < 120; j++){
            string cwwJ = cwwI;
            int cww10_3 = 0;
            if(checkCWW(cwwJ[a10_3[j][0]], cwwJ[a10_3[j][1]], cwwJ[a10_3[j][2]])){
                cww10_3 = 100 * (cwwJ[a10_3[j][0]] - '0') + 10 * (cwwJ[a10_3[j][1]] - '0') + (cwwJ[a10_3[j][2]] - '0');
                stock = cww13_3 + cww10_3;
                // 最大値更新.
                ans = max(ans, stock);
            }else{
                stock = cww13_3;
            }
            // 文字列 cwwJ を編集.
            cwwJ.erase(a10_3[j][2], 1);
            cwwJ.erase(a10_3[j][1], 1);
            cwwJ.erase(a10_3[j][0], 1);
            // 7C3通りの確認.
            for(int k = 0; k < 35; k++){
                string cwwK = cwwJ;
                int cww7_3 = 0;
                if(checkCWW(cwwK[a7_3[k][0]], cwwK[a7_3[k][1]], cwwK[a7_3[k][2]])){
                    cww7_3 = 100 * (cwwK[a7_3[k][0]] - '0') + 10 * (cwwK[a7_3[k][1]] - '0') + (cwwK[a7_3[k][2]] - '0');
                    stock = cww13_3 + cww10_3 + cww7_3;
                    // 最大値更新.
                    ans = max(ans, stock);
                }else{
                    stock = cww13_3 + cww10_3;
                }
                // 文字列 cwwK を編集.
                cwwK.erase(a7_3[k][2], 1);
                cwwK.erase(a7_3[k][1], 1);
                cwwK.erase(a7_3[k][0], 1);

                // 4C3通りの確認.
                for(int l = 0; l < 4; l++){
                    string cwwL = cwwK;
                    if(checkCWW(cwwK[a4_3[l][0]], cwwK[a4_3[l][1]], cwwK[a4_3[l][2]])){
                        int cww4_3 = 100 * (cwwL[a4_3[l][0]] - '0') + 10 * (cwwL[a4_3[l][1]] - '0') + (cwwL[a4_3[l][2]] - '0');
                        stock = cww13_3 + cww10_3 + cww7_3 + cww4_3;
                        // 最大値更新.
                        ans = max(ans, stock);
                    }else{
                        stock = cww13_3 + cww10_3 + cww7_3;
                    }
                }
            }
        }
    }
    
    // 4. 出力.
    // ex.
    // 253432030884 (344) -> 253203088 (588) -> 232030 (233) -> 200 (200) -> なし で, 合計 1365.
    cout << ans << endl;
    return 0;
    
}
0