#1141650 (C++23) No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！

• 問題: No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
• ユーザー: harel
• 提出日時: 2025-12-25 01:08:06
• 言語: C++23 (gcc 13.3.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,232 bytes
• コンパイル時間: 2,504 ms
• コンパイル使用メモリ: 139,036 KB
• 実行使用メモリ: 42,136 KB
• スコア: 0
• 最終ジャッジ日時: 2025-12-25 01:15:08
• 合計ジャッジ時間: 14,315 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
other	TLE * 1 -- * 99

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

int countMatches(const vector<int>& a, const vector<int>& b) {
    int count = 0;
    for (int i = 0; i < 5; i++) {
        if (a[i] == b[i]) {
            count++;
        }
    }
    return count;
}

int countWrongPosition(const vector<int>& a, const vector<int>& b) {
    vector<bool> usedA(5, false);
    vector<bool> usedB(5, false);
    
    for (int i = 0; i < 5; i++) {
        if (a[i] == b[i]) {
            usedA[i] = true;
            usedB[i] = true;
        }
    }
    
    int count = 0;
    for (int i = 0; i < 5; i++) {
        if (usedA[i]) continue;
        for (int j = 0; j < 5; j++) {
            if (usedB[j]) continue;
            if (a[i] == b[j]) {
                usedB[j] = true;
                count++;
                break;
            }
        }
    }
    
    return count;
}

// 2つの組み合わせ（ソート済み）で共通している数字の個数
int countCommonDigits(const vector<int>& a, const vector<int>& b) {
    set<int> setA(a.begin(), a.end());
    int count = 0;
    for (int digit : b) {
        if (setA.count(digit)) {
            count++;
        }
    }
    return count;
}

vector<int> chooseBestGuess(const vector<vector<int>>& candidates) {
    if (candidates.empty()) return {};
    return candidates[0];
}

vector<vector<int>> generateAllPermutations(const vector<int>& digits) {
    vector<vector<int>> allPerms;
    vector<int> perm = digits;
    sort(perm.begin(), perm.end());
    
    do {
        allPerms.push_back(perm);
    } while (next_permutation(perm.begin(), perm.end()));
    
    return allPerms;
}

vector<vector<int>> generateAllCombinations() {
    vector<vector<int>> allCombs;
    
    for (int a = 0; a <= 9; a++) {
        for (int b = a + 1; b <= 9; b++) {
            for (int c = b + 1; c <= 9; c++) {
                for (int d = c + 1; d <= 9; d++) {
                    for (int e = d + 1; e <= 9; e++) {
                        allCombs.push_back({a, b, c, d, e});
                    }
                }
            }
        }
    }
    
    return allCombs;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 組み合わせの候補リスト
    vector<vector<int>> combCandidates = generateAllCombinations();
    
    // 各組み合わせに対する順列候補
    map<vector<int>, vector<vector<int>>> combToPermCandidates;
    for (const auto& comb : combCandidates) {
        combToPermCandidates[comb] = generateAllPermutations(comb);
    }
    
    while (true) {
        // まだ順列が複数ある組み合わせを探す
        vector<int> chosenComb;
        for (const auto& comb : combCandidates) {
            if (combToPermCandidates[comb].size() > 1) {
                chosenComb = comb;
                break;
            }
        }
        
        // なければ適当に1つ選ぶ
        if (chosenComb.empty() && !combCandidates.empty()) {
            chosenComb = combCandidates[0];
        }
        
        if (chosenComb.empty()) break;
        
        vector<vector<int>>& permCandidates = combToPermCandidates[chosenComb];
        if (permCandidates.empty()) break;
        
        vector<int> guess = chooseBestGuess(permCandidates);
        
        // 出力
        for (int num : guess) {
            cout << num;
        }
        cout << endl;
        
        // 30個の応答を受け取る
        multiset<pair<int,int>> responses;
        int count_5_0 = 0;
        
        for (int i = 0; i < 30; i++) {
            int x, y;
            cin >> x >> y;
            responses.insert({x, y});
            if (x == 5 && y == 0) {
                count_5_0++;
            }
        }
        
        // 全て5 0なら終了
        if (count_5_0 == 30) {
            break;
        }
        
        // *** 重要：x+yの値を使って組み合わせ候補を絞る ***
        vector<vector<int>> newCombCandidates;
        
        for (const auto& comb : combCandidates) {
            // この組み合わせに対して期待されるx+yの値のセットを計算
            multiset<int> expectedSums;
            
            for (const auto& perm : combToPermCandidates[comb]) {
                int x = countMatches(guess, perm);
                int y = countWrongPosition(guess, perm);
                expectedSums.insert(x + y);
            }
            
            // 実際のx+yのセット
            multiset<int> actualSums;
            for (auto [x, y] : responses) {
                actualSums.insert(x + y);
            }
            
            // または、共通数字で直接チェック
            multiset<int> expectedCommon;
            int common = countCommonDigits(guess, comb);
            
            // この組み合わせの全順列は同じ共通数字数を持つ
            for (int i = 0; i < combToPermCandidates[comb].size(); i++) {
                expectedCommon.insert(common);
            }
            
            // actualSumsにこのcommonが含まれているか
            bool valid = false;
            for (int sum : actualSums) {
                if (sum == common) {
                    valid = true;
                    break;
                }
            }
            
            if (valid) {
                newCombCandidates.push_back(comb);
            }
        }
        
        combCandidates = newCombCandidates;
        
        // 現在の組み合わせの順列候補を絞る
        vector<vector<int>> newPermCandidates;
        
        for (const auto& perm : permCandidates) {
            int x = countMatches(guess, perm);
            int y = countWrongPosition(guess, perm);
            
            // この(x,y)が実際の応答に含まれているか
            if (responses.count({x, y}) > 0) {
                newPermCandidates.push_back(perm);
            }
        }
        
        permCandidates = newPermCandidates;
        
        // 候補が1つになったら次の組み合わせへ
        if (permCandidates.size() <= 1) {
            // 次の組み合わせを探す
        }
    }
    
    return 0;
}