結果

問題 No.3418 【絶望】30個並列ごちゃ混ぜHit&Blowで遊ぼう！
コンテスト
ユーザー harel
提出日時 2025-12-25 01:03:22
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 6,728 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,135 ms
コンパイル使用メモリ 136,520 KB
実行使用メモリ 33,392 KB
スコア 0
最終ジャッジ日時 2025-12-25 01:04:49
合計ジャッジ時間 14,406 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 99
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using namespace std;

// claude sonet4.5 解法を伝えてコード生成

// 2つの順列を比較して、位置が一致する個数を返す
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;
}

// 2つの順列で数字が含まれているが位置が違う個数を返す
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;
}

// 推測を与えると、候補を最も均等に分割できるものを選ぶ
vector<int> chooseBestGuess(const vector<vector<int>>& candidates) {
    if (candidates.size() == 1) {
        return candidates[0];
    }
    
    vector<int> bestGuess = candidates[0];
    int bestScore = 1e9;
    
    for (const auto& guess : candidates) {
        map<pair<int,int>, int> responseCounts;
        
        for (const auto& candidate : candidates) {
            int x = countMatches(guess, candidate);
            int y = countWrongPosition(guess, candidate);
            responseCounts[{x, y}]++;
        }
        
        int maxGroup = 0;
        for (auto& [key, count] : responseCounts) {
            maxGroup = max(maxGroup, count);
        }
        
        if (maxGroup < bestScore) {
            bestScore = maxGroup;
            bestGuess = guess;
        }
    }
    
    return bestGuess;
}

// 推測と応答を元に候補をフィルタリング
vector<vector<int>> filterCandidates(
    const vector<vector<int>>& candidates,
    const vector<int>& guess,
    const map<pair<int,int>, int>& responseMap
) {
    vector<vector<int>> filtered;
    
    for (const auto& candidate : candidates) {
        int x = countMatches(guess, candidate);
        int y = countWrongPosition(guess, candidate);
        
        // この候補がresponseMapと整合性があるかチェック
        auto it = responseMap.find({x, y});
        if (it != responseMap.end() && it->second > 0) {
            filtered.push_back(candidate);
        }
    }
    
    return filtered;
}

// 0~9から5つ選ぶ全ての順列を生成
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;
}

// 0~9から5つを選ぶ全ての組み合わせ
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() {
    // 全候補の組み合わせと順列を生成
    vector<vector<int>> allCombs = generateAllCombinations();
    
    // 各組み合わせに対する全順列を保持
    map<vector<int>, vector<vector<int>>> combToCandidates;
    for (const auto& comb : allCombs) {
        combToCandidates[comb] = generateAllPermutations(comb);
    }
    
    while (true) {
        // まだ確定していない組み合わせから1つ選ぶ
        vector<int> chosenComb;
        for (auto& [comb, candidates] : combToCandidates) {
            if (!candidates.empty()) {
                chosenComb = comb;
                break;
            }
        }
        
        if (chosenComb.empty()) {
            break; // 全て確定
        }
        
        vector<vector<int>>& candidates = combToCandidates[chosenComb];
        vector<int> guess = chooseBestGuess(candidates);
        
        // 出力
        for (int num : guess) {
            cout << num;
        }
        cout << endl;
        cout.flush();
        
        // 30個の応答を受け取る（辞書順ソート済み）
        map<pair<int,int>, int> responseMap;
        int count_5_0 = 0;
        
        for (int i = 0; i < 30; i++) {
            int x, y;
            cin >> x >> y;
            responseMap[{x, y}]++;
            if (x == 5 && y == 0) {
                count_5_0++;
            }
        }
        
        // 全て5 0なら終了
        if (count_5_0 == 30) {
            break;
        }
        
        // 各組み合わせの候補を更新
        for (auto& [comb, cand] : combToCandidates) {
            if (cand.empty()) continue; // すでに確定済み
            
            // この組み合わせに対する期待される応答を計算
            map<pair<int,int>, int> expectedMap;
            for (const auto& candidate : cand) {
                int x = countMatches(guess, candidate);
                int y = countWrongPosition(guess, candidate);
                expectedMap[{x, y}]++;
            }
            
            // responseMapと一致する候補だけ残す
            vector<vector<int>> newCand;
            for (const auto& candidate : cand) {
                int x = countMatches(guess, candidate);
                int y = countWrongPosition(guess, candidate);
                
                // この(x,y)がresponseMapに存在し、まだ割り当て可能か
                if (responseMap[{x, y}] > 0) {
                    newCand.push_back(candidate);
                }
            }
            
            // 候補が1つに絞られたら確定
            if (newCand.size() == 1) {
                cand.clear(); // 確定したのでクリア
            } else {
                cand = newCand;
            }
        }
        
        // 今回の推測の組み合わせの候補を更新
        candidates = filterCandidates(candidates, guess, responseMap);
        if (candidates.size() == 1) {
            candidates.clear(); // 確定
        }
    }
    
    return 0;
}
0