#341176 (C++11) No.437 cwwゲーム

提出ソース

結果

問題	No.437 cwwゲーム
ユーザー	@abcde
提出日時	2019-04-20 18:15:43
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	112 ms / 2,000 ms
コード長	6,198 bytes
コンパイル時間	1,703 ms
コンパイル使用メモリ	170,732 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-10-12 08:52:04
合計ジャッジ時間	6,953 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	86 ms 6,820 KB
testcase_01	AC	87 ms 6,820 KB
testcase_02	AC	97 ms 6,820 KB
testcase_03	AC	88 ms 6,820 KB
testcase_04	AC	87 ms 6,816 KB
testcase_05	AC	104 ms 6,820 KB
testcase_06	AC	107 ms 6,820 KB
testcase_07	AC	112 ms 6,816 KB
testcase_08	AC	99 ms 6,816 KB
testcase_09	AC	112 ms 6,816 KB
testcase_10	AC	106 ms 6,820 KB
testcase_11	AC	86 ms 6,820 KB
testcase_12	AC	89 ms 6,820 KB
testcase_13	AC	90 ms 6,820 KB
testcase_14	AC	90 ms 6,816 KB
testcase_15	AC	108 ms 6,820 KB
testcase_16	AC	91 ms 6,816 KB
testcase_17	AC	94 ms 6,820 KB
testcase_18	AC	93 ms 6,816 KB
testcase_19	AC	89 ms 6,816 KB
testcase_20	AC	87 ms 6,816 KB
testcase_21	AC	86 ms 6,816 KB
testcase_22	AC	86 ms 6,816 KB
testcase_23	AC	88 ms 6,820 KB
testcase_24	AC	86 ms 6,816 KB
testcase_25	AC	90 ms 6,816 KB
testcase_26	AC	91 ms 6,816 KB
testcase_27	AC	85 ms 6,820 KB
testcase_28	AC	87 ms 6,820 KB
testcase_29	AC	86 ms 6,820 KB
testcase_30	AC	85 ms 6,816 KB
testcase_31	AC	86 ms 6,816 KB
testcase_32	AC	85 ms 6,820 KB
testcase_33	AC	90 ms 6,816 KB
testcase_34	AC	88 ms 6,820 KB
testcase_35	AC	88 ms 6,820 KB
testcase_36	AC	86 ms 6,816 KB
testcase_37	AC	87 ms 6,820 KB
testcase_38	AC	87 ms 6,820 KB
testcase_39	AC	84 ms 6,816 KB
testcase_40	AC	85 ms 6,816 KB
testcase_41	AC	87 ms 6,816 KB
testcase_42	AC	90 ms 6,820 KB
testcase_43	AC	90 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
    
}

yukicoder

結果

テストケース

ソースコード