結果

問題 No.2148 ひとりUNO
コンテスト
ユーザー ei1333333
提出日時 2022-12-02 23:33:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 714 ms / 2,000 ms
コード長 3,606 bytes
コンパイル時間 2,444 ms
コンパイル使用メモリ 209,680 KB
最終ジャッジ日時 2025-02-09 04:28:39
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

const string colors = "RGBY";

const string patterns[] = {
    "A",
    "AB",
    "AAB",
    "ABB",
    "ABC",
    "AABB",
    "AABC",
    "ABBC",
    "ABCC",
    "ABCD",
    "AABBC",
    "AABCC",
    "AABCD",
    "ABBBC",
    "ABBCC",
    "ABBCD",
    "ABCCD",
    "ABCDD",
    "AABBBC",
    "AABBCC",
    "AABBCD",
    "AABCCD",
    "AABCDD",
    "ABBBCC",
    "ABBBCD",
    "ABBCCD",
    "ABBCDD",
    "ABCCBD",
    "ABCCCD",
    "ABCCDD",
    "ABCDDB",
    "AABBBCC",
    "AABBBCD",
    "AABBCCD",
    "AABBCDD",
    "AABCCBD",
    "AABCCCD",
    "AABCCDD",
    "AABCDDB",
    "ABBBCCD",
    "ABBBCDD",
    "ABBCCCD",
    "ABBCCDD",
    "ABCCBDD",
    "ABCCCBD",
    "ABCCCDD",
    "ABCCDDB",
    "ABCDDBB",
    "ABCDDDB",
    "AABBBCCD",
    "AABBBCDD",
    "AABBCCCD",
    "AABBCCDD",
    "AABCCBDD",
    "AABCCCBD",
    "AABCCCDD",
    "AABCCDDB",
    "AABCDDBB",
    "AABCDDDB",
    "ABBBCCCD",
    "ABBBCCDD",
    "ABBCCCDD",
    "ABCCBDDB",
    "ABCCCBDD",
    "ABCCCDDB",
    "ABCCDDBB",
    "ABCCDDDB",
    "ABCDDBBD",
    "ABCDDDBB",
    "AABBBCCCD",
    "AABBBCCDD",
    "AABBCCCDD",
    "AABCCBDDB",
    "AABCCCBDD",
    "AABCCCDDB",
    "AABCCDDBB",
    "AABCCDDDB",
    "AABCDDBBD",
    "AABCDDDBB",
    "ABBBCCCDD",
    "ABCCBDDDB",
    "ABCCCBDDB",
    "ABCCCDDBB",
    "ABCCCDDDB",
    "ABCCDDBBD",
    "ABCCDDDBB",
    "AABBBCCCDD",
    "AABCCBDDDB",
    "AABCCCBDDB",
    "AABCCCDDBB",
    "AABCCCDDDB",
    "AABCCDDBBD",
    "AABCCDDDBB",
    "ABCCCBDDDB",
    "ABCCCDDBBD",
    "ABCCCDDDBB",
    "AABCCCBDDDB",
    "AABCCCDDBBD",
    "AABCCCDDDBB",
};

void test() {
  int N;
  cin >> N;
  vector< int > C(N), D(N);
  for (int i = 0; i < N; i++) {
    char c;
    cin >> c >> D[i];
    C[i] = colors.find(c);
  }

  vector< int > perm{0, 1, 2, 3};
  do {
    vector< int > cnt(1 << 4);
    {
      map< int, int > mp;
      for (int i = 0; i < N; i++) {
        mp[D[i]] |= 1 << perm[C[i]];
      }
      for (auto &p: mp) {
        cnt[p.second]++;
      }
    }
    for (auto& pattern: patterns) {
      vector< int > old_parts;
      for (auto &c: pattern) {
        int p = (c - 'A');
        if (old_parts.empty() or ((old_parts.back() >> p) & 1)) {
          old_parts.emplace_back();
        }
        old_parts.back() |= 1 << p;
      }
      int mask = 0;
      for(auto& c : old_parts) {
        if(c == 1 or c == 2 or c == 4 or c == 8) {
          mask |= c;
        }
      }
      vector< int > parts;
      for(auto& c : old_parts) {
        if(c != 1 and c != 2 and c != 4 and c != 8) parts.emplace_back(c);
      }
      auto dfs = [&](auto &dfs, int idx) -> bool {
        if (idx == -1) {
          for (int i = 0; i < 4; i++) {
            if ((~mask >> i) & 1) {
              for (int j = 0; j < cnt.size(); j++) {
                if((j >> i) & 1 and cnt[j] > 0) {
                  return false;
                }
              }
            }
          }
          return true;
        }
        for (int i = 0; i < cnt.size(); i++) {
          if (cnt[i] > 0 and (parts[idx] & i) == parts[idx]) {
            cnt[i]--;
            if (i != parts[idx]) cnt[i ^ parts[idx]]++;
            if (dfs(dfs, idx - 1)) return true;
            if (i != parts[idx]) cnt[i ^ parts[idx]]--;
            cnt[i]++;
          }
        }
        return false;
      };
      if (dfs(dfs, (int) parts.size() - 1)) {
        cout << "YES" << endl;
        return;
      }
    }
  } while (next_permutation(perm.begin(), perm.end()));
  cout << "NO" << endl;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    test();
  }
}
0