[ABC236] D - Dance

[Q] https://atcoder.jp/contests/abc236/tasks/abc236_d

1. ゴリゴリのdfs実装。
2. 16! = 81729648000 なのでTLE。高速化が必要。
3. ペアの最初の要素は、必ず残りの最小indexになるので、
15 * 13 * 11 * ... * 1 = 2027025探索 まで落とせる。

N=3
012345
の6人を考える。

3ペア選べるので、それを全探索したい。
1) 1組目のペアの選び方
0固定で選んで、
01,02,03,04,05 の5通りだけ考えればいい。

Q. 0固定？
A. 
1組目に12, 2組目に03を選ぶ場合の探索と、
1組目に03, 2組目に12を選ぶ場合の探索は同じこと。

ペアの1人目は、空いている人のうち最もindexが若い人を固定で選べばいい。

2) 2組目のペアの選び方
01 -> {23,24,25}
02 -> {13,14,15}
03 -> {12,14,15}
04 -> {12,13,15}
05 -> {12,13,14}
の探索に進む。

3) 3組目のペアの選び方
上記 3*5 = 15通りについて、それぞれ枝が伸びる。

この探索は、5*3*1 = 15通りで全然間に合う。

N=8 のとき、
15*13*11* ... *1 = 2027025 で間に合う。

実装

ll N;
ll A[20][20];
ll ans = 0;
bool used[20];  // バックトラック

void dfs(ll d, ll sum) {
 if (d == N) {
   chmax(ans, sum);
   return;
 }
 // 最小idは確定取得
 ll i = 0;
 while (used[i] == true) ++i;
 if (i >= N * 2) return;

 // バックトラック
 used[i] = true;
 for (ll j = i + 1; j < N * 2; ++j) {  // 15*13*11*9*..*1 だから間に合う
   if (used[j]) continue;
   used[j] = true;
   dfs(d + 1, sum ^ A[i][j]);
   used[j] = false;
 }
 used[i] = false;
}

int main() {
 cincout();

 cin >> N;
 rep(i, N * 2) {
   for (ll j = i + 1; j < N * 2; ++j) {
     cin >> A[i][j];
   }
 }
 dfs(0, 0);  // ペア数, 合計値
 cout << ans << endl;
}

https://atcoder.jp/contests/abc236/submissions/28738671