結果

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

ソースコード

diff #
raw source code 

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

using namespace std;

// claude sonet4.5
// 解法を全て伝えて実装をAIにやらせている

// 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) {
        // 応答パターンごとにカウント (x,y)のペアは最大36通り
        vector<vector<int>> responseCounts(6, vector<int>(6, 0));
        
        for (const auto& candidate : candidates) {
            int x = countMatches(guess, candidate);
            int y = countWrongPosition(guess, candidate);
            responseCounts[x][y]++;
        }
        
        // 最大グループのサイズ
        int maxGroup = 0;
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                maxGroup = max(maxGroup, responseCounts[i][j]);
            }
        }
        
        if (maxGroup < bestScore) {
            bestScore = maxGroup;
            bestGuess = guess;
        }
    }
    
    return bestGuess;
}

// 推測と応答を元に候補をフィルタリング
vector<vector<int>> filterCandidates(
    const vector<vector<int>>& candidates,
    const vector<int>& guess,
    int responseX,
    int responseY
) {
    vector<vector<int>> filtered;
    
    for (const auto& candidate : candidates) {
        int x = countMatches(guess, candidate);
        int y = countWrongPosition(guess, candidate);
        if (x == responseX && y == responseY) {
            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;
}

// 最初の推測: 0~9から5つ選ぶ段階
vector<int> chooseInitialGuess(const vector<vector<int>>& candidateCombs) {
    // とりあえず最初の候補を返す（改善の余地あり）
    return candidateCombs[0];
}

int main() {
    // 0~9から5つ選ぶ全ての組み合わせ
    vector<vector<int>> candidateCombs = generateAllCombinations();
    
    while (true) {
        // Phase 1: 0~9から5つを決定する
        vector<int> chosenDigits = chooseInitialGuess(candidateCombs);
        
        // 出力
        for (int d : chosenDigits) {
            cout << d;
        }
        cout << endl;
        cout.flush();
        
        // 30個の応答を受け取る
        vector<pair<int, int>> responses;
        for (int i = 0; i < 30; i++) {
            int x, y;
            cin >> x >> y;
            responses.push_back({x, y});
        }
        
        // 全て5 0なら終了
        bool allCorrect = true;
        for (auto [x, y] : responses) {
            if (x != 5 || y != 0) {
                allCorrect = false;
                break;
            }
        }
        
        if (allCorrect) {
            break;
        }
        
        // x + y == 5 かつ x != 5 のものを処理
        for (auto [x, y] : responses) {
            if (x + y == 5 && x != 5) {
                // この組み合わせで順列を決定する
                vector<vector<int>> candidates = generateAllPermutations(chosenDigits);
                
                while (candidates.size() > 1) {
                    vector<int> guess = chooseBestGuess(candidates);
                    
                    // 出力
                    for (int num : guess) {
                        cout << num;
                    }
                    cout << endl;
                    cout.flush();
                    
                    // 30個の応答を受け取る
                    vector<pair<int, int>> subResponses;
                    for (int i = 0; i < 30; i++) {
                        int sx, sy;
                        cin >> sx >> sy;
                        subResponses.push_back({sx, sy});
                    }
                    
                    // 該当する応答を探す（同じ数字の組み合わせに対する応答）
                    int targetX = -1, targetY = -1;
                    for (auto [sx, sy] : subResponses) {
                        if (sx + sy == 5) {
                            targetX = sx;
                            targetY = sy;
                            break;
                        }
                    }
                    
                    if (targetX == 5) {
                        break;
                    }
                    
                    // 候補をフィルタリング
                    candidates = filterCandidates(candidates, guess, targetX, targetY);
                }
                
                // この組み合わせの順列が決まったので次へ
                break;
            }
        }
        
        // 候補組み合わせを更新
        vector<vector<int>> newCandidateCombs;
        for (const auto& comb : candidateCombs) {
            bool valid = true;
            
            // 各応答と整合性チェック
            for (auto [x, y] : responses) {
                // combとchosenDigitsの関係をチェック
                set<int> combSet(comb.begin(), comb.end());
                set<int> chosenSet(chosenDigits.begin(), chosenDigits.end());
                
                int common = 0;
                for (int d : combSet) {
                    if (chosenSet.count(d)) {
                        common++;
                    }
                }
                
                // この応答が期待される値かチェック
                if (common != x + y) {
                    valid = false;
                    break;
                }
            }
            
            if (valid) {
                newCandidateCombs.push_back(comb);
            }
        }
        
        candidateCombs = newCandidateCombs;
    }
    
    return 0;
}
0