[ABC326] D - ABC Puzzle

[Q] https://atcoder.jp/contests/abc326/tasks/abc326_d

考察
1. 実装重そう。とりあえず全探索を考える。
2. 25マスに4通り"ABC."が入るので4^25通りの探索。これはTLE。
3. 枝刈り条件がたくさんあるので、削っていけばdfsで間に合う気がする
・自分のマスにAをおくとき、行と列にすでにAがあればおかない
・行を置ききったあと、行がABCを網羅していなければダメ
・列を置ききったあと、列がABCを網羅していなければダメ
4. 終了条件は、25マス埋めた後に左文字列と上文字列が指示と同じか評価。

実装

int main() {
  cincout();
  
  ll N;
  string R, C;
  cin >> N >> R >> C;

  vector<ll> h(N), w(N); // h[0]=111: 0列目はABCすべて使用済み
  vector<string> S(N, string(N, '.')); // 答え。backtrackで埋めていく

  // マスpにABCをおけるか
  auto canPut=[&](ll p, ll a)->bool{
    if (is_pop(h[p % N], a)) return false;
    if (is_pop(w[p / N], a)) return false;
    return true;
  };

  // 25マス見終わったあとの盤面評価
  auto bingo=[&]()->bool{
    // ABCが行と列でそろっているか
    rep(i, N) if (__bt(h[i]) != 3) return false;
    rep(i, N) if (__bt(w[i]) != 3) return false;
    string r, c;
    // 最も左のABCを取得
    rep(i, N) rep(j, N){
      if (S[i][j] == '.') continue;
      r += S[i][j];
      break;
    }
    // 最も上のABCを取得
    rep(i, N) rep(j, N){
      if (S[j][i] == '.') continue;
      c += S[j][i];
      break;
    }
    if (r == R && c == C) return true;
    return false;
  };

  // backtrackで、25マス探索
  std::function<bool(ll)> dfs = [&](ll p)->bool{
    // TLEのため枝刈り
    // 0行目を埋め終わった時点で、ABCがそろっていないとダメ
    if (p % N == 0 && p > 0){
      if (__bt(w[(p - 1) / N]) != 3) return false;
    }
    // 0列目を埋め終わった時点で、ABCがそろっていないとダメ
    if ((p - 1) / N == N - 1){
      if (__bt(h[(p - 1) % N]) != 3) return false;
    }
    // 解答を満たすか判定
    if (p == N * N){
      if (bingo()){
        cout << "Yes" << endl;
        rep(i, N) cout << S[i] << endl;
        return true;
      }
      return false;
    }
    rep(i, 3){ // "ABC"[i]
      if (!canPut(p, i)) continue;
      // 設置
      h[p % N] += (1 << i);
      w[p / N] += (1 << i);
      S[p / N][p % N] = "ABC"[i];
      if (dfs(p + 1)) return true;
      // 復元 backtrack
      h[p % N] -= (1 << i);
      w[p / N] -= (1 << i);
    }
    S[p / N][p % N] = '.';
    if (dfs(p + 1)) return true;
    return false;
  };
  if (dfs(0)) return 0;
  cout << "No" << endl;
}

https://atcoder.jp/contests/abc326/submissions/47021832