TCO16 Round 1C Medium: ThreeProgrammers
解法
DP + 筋肉
コード
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace std; string dp[51][51][51][7], tmp[51][51][51][7]; const int AA = 0, AB = 1, AC = 2, BA = 3, BC = 4, CA = 5, CB = 6; class ThreeProgrammers { public: string validCodeHistory(string code) { int N = code.size(); vector<int> cnt(3, 0); for (int i = 0; i < N; ++i) cnt[(code[i] - 'A')]++; int reqC = (N + 2) / 3; int reqB = (N + 1) / 2; if (reqC < cnt[2] || reqB < cnt[1]) return "impossible"; for (int j = 0; j < 51; ++j) { for (int k = 0; k < 51; ++k) { for (int l = 0; l < 51; ++l) { for (int m = 0; m < 7; ++m) { dp[j][k][l][m] = "D"; } } } } dp[cnt[0]][cnt[1]][cnt[2]][AA] = ""; for (int i = 0; i < N; ++i) { for (int cntA = 0; cntA <= cnt[0]; ++cntA) { for (int cntB = 0; cntB <= cnt[1]; ++cntB) { for (int cntC = 0; cntC <= cnt[2]; ++cntC) { for (int m = 0; m < 7; ++m) { tmp[cntA][cntB][cntC][m] = "D"; } } } } for (int cntA = 0; cntA <= cnt[0]; ++cntA) { for (int cntB = 0; cntB <= cnt[1]; ++cntB) { for (int cntC = 0; cntC <= cnt[2]; ++cntC) { for (int suffix = 0; suffix < 7; ++suffix) { if (dp[cntA][cntB][cntC][suffix] == "D") continue; string &s = dp[cntA][cntB][cntC][suffix]; if (cntA > 0) { if (suffix == AA || suffix == BA || suffix == CA) { tmp[cntA - 1][cntB][cntC][AA] = s + "A"; } else if (suffix == AB || suffix == CB) { tmp[cntA - 1][cntB][cntC][BA] = s + "A"; } else { tmp[cntA - 1][cntB][cntC][CA] = s + "A"; } } if (cntB > 0) { if (suffix == AA || suffix == BA || suffix == CA) { tmp[cntA][cntB - 1][cntC][AB] = s + "B"; } else if (suffix == AB || suffix == CB) { } else { tmp[cntA][cntB - 1][cntC][CB] = s + "B"; } } if (cntC > 0) { if (suffix == AA || suffix == BA) { tmp[cntA][cntB][cntC - 1][AC] = s + "C"; } else if (suffix == AB) { tmp[cntA][cntB][cntC - 1][BC] = s + "C"; } } } } } } for (int cntA = 0; cntA <= cnt[0]; ++cntA) { for (int cntB = 0; cntB <= cnt[1]; ++cntB) { for (int cntC = 0; cntC <= cnt[2]; ++cntC) { for (int m = 0; m < 7; ++m) { dp[cntA][cntB][cntC][m] = tmp[cntA][cntB][cntC][m]; } } } } } for (int suffix = 0; suffix < 7; ++suffix) { if (dp[0][0][0][suffix] != "D") return dp[0][0][0][suffix]; } return "impossible"; } };