読者です 読者をやめる 読者になる 読者になる

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";
  }
};