#include #include #include #include #include using namespace std; // claude sonet4.5 解法を伝えてコード生成 // 2つの順列を比較して、位置が一致する個数を返す int countMatches(const vector& a, const vector& b) { int count = 0; for (int i = 0; i < 5; i++) { if (a[i] == b[i]) { count++; } } return count; } // 2つの順列で数字が含まれているが位置が違う個数を返す int countWrongPosition(const vector& a, const vector& b) { vector usedA(5, false); vector 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 chooseBestGuess(const vector>& candidates) { if (candidates.size() == 1) { return candidates[0]; } vector bestGuess = candidates[0]; int bestScore = 1e9; for (const auto& guess : candidates) { map, 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> filterCandidates( const vector>& candidates, const vector& guess, const map, int>& responseMap ) { vector> 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> generateAllPermutations(const vector& digits) { vector> allPerms; vector 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> generateAllCombinations() { vector> 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> allCombs = generateAllCombinations(); // 各組み合わせに対する全順列を保持 map, vector>> combToCandidates; for (const auto& comb : allCombs) { combToCandidates[comb] = generateAllPermutations(comb); } while (true) { // まだ確定していない組み合わせから1つ選ぶ vector chosenComb; for (auto& [comb, candidates] : combToCandidates) { if (!candidates.empty()) { chosenComb = comb; break; } } if (chosenComb.empty()) { break; // 全て確定 } vector>& candidates = combToCandidates[chosenComb]; vector guess = chooseBestGuess(candidates); // 出力 for (int num : guess) { cout << num; } cout << endl; cout.flush(); // 30個の応答を受け取る(辞書順ソート済み) map, 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, int> expectedMap; for (const auto& candidate : cand) { int x = countMatches(guess, candidate); int y = countWrongPosition(guess, candidate); expectedMap[{x, y}]++; } // responseMapと一致する候補だけ残す vector> 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; }