問題
9枚のカードがある。そのうち3枚が、同じ色で、かつ同じ数字または連番のとき、3枚を1セットとみなす。3セット揃っているかどうか調べよ。数字は1〜9までの値で、連番とは3,4,5のようなものを指す。9,1,2は連番ではないことに注意せよ。
解答
9個あるカードを3分割する全探索をする。3^9で解が求まる。
解法選びが問題の肝。
bool check(vector<deque<pair<int, char>>> const& cards) { rep(i, 3) { assert(cards[i].size() == 3); char col = cards[i][0].second; vector<int> is; for(auto p: cards[i]) { if(col != p.second) return false; is.push_back(p.first); } sort(is.begin(), is.end()); if(!((is[0] + 1 == is[1] && is[1] + 1 == is[2]) || (is[0] == is[2]))) return false; } return true; } bool dfs(vector<pair<int, char>> const& vs, vector<deque<pair<int, char>>>& cards, int idx) { if(idx == vs.size()) { if(check(cards)) return true; return false; } rep(i, 3) { if(cards[i].size() < 3) { cards[i].push_back(vs[idx]); if(dfs(vs, cards, idx + 1)) return true; cards[i].pop_back(); } } return false; } int main() { int Tc; cin >> Tc; while(Tc--) { vector<pair<int, char>> vs; vector<int> a(9); vector<char> b(9); rep(i, 9) cin >> a[i]; rep(i, 9) cin >> b[i]; rep(i, 9) vs.emplace_back(a[i], b[i]); vector<deque<pair<int, char>>> cards(3); cout << dfs(vs, cards, 0) << endl; } return 0; }