next_permutationの動きを確認

    VI V;
    rep(i, 4){
      V.push_back(i);
    }
    do{
      debug(V);
    }while(next_permutation(ALL(V)));

出力

[V]: {0, 1, 2, 3}
[V]: {0, 1, 3, 2}
[V]: {0, 2, 1, 3}
[V]: {0, 2, 3, 1}
[V]: {0, 3, 1, 2}
[V]: {0, 3, 2, 1}
[V]: {1, 0, 2, 3}
[V]: {1, 0, 3, 2}
[V]: {1, 2, 0, 3}
[V]: {1, 2, 3, 0}
[V]: {1, 3, 0, 2}
[V]: {1, 3, 2, 0}
[V]: {2, 0, 1, 3}
[V]: {2, 0, 3, 1}
[V]: {2, 1, 0, 3}
[V]: {2, 1, 3, 0}
[V]: {2, 3, 0, 1}
[V]: {2, 3, 1, 0}
[V]: {3, 0, 1, 2}
[V]: {3, 0, 2, 1}
[V]: {3, 1, 0, 2}
[V]: {3, 1, 2, 0}
[V]: {3, 2, 0, 1}
[V]: {3, 2, 1, 0}

next_partial_permutationというテク

http://cielavenir.github.io/blog/2018/06/10/pair-team/

    ll N = 4;
    VI V;
    rep(i, 4){
      V.push_back(i);
    }
    do{
      debug(V);
      reverse(V.begin()+N/2,V.end()); // 後半半分をリバースする
    }while(next_permutation(ALL(V)));

出力

[V]: {0, 1, 2, 3}
[V]: {0, 2, 1, 3}
[V]: {0, 3, 1, 2}
[V]: {1, 0, 2, 3}
[V]: {1, 2, 0, 3}
[V]: {1, 3, 0, 2}
[V]: {2, 0, 1, 3}
[V]: {2, 1, 0, 3}
[V]: {2, 3, 0, 1}
[V]: {3, 0, 1, 2}
[V]: {3, 1, 0, 2}
[V]: {3, 2, 0, 1}

数は、4!=24だったものが12に減っている (1/2になっている)
消えたものを✕でチェックすると、

[V]: {0, 1, 2, 3}
[V]: {0, 1, 3, 2} ✕
[V]: {0, 2, 1, 3}
[V]: {0, 2, 3, 1} ✕
[V]: {0, 3, 1, 2}
[V]: {0, 3, 2, 1} ✕
[V]: {1, 0, 2, 3}
[V]: {1, 0, 3, 2} ✕
[V]: {1, 2, 0, 3}
[V]: {1, 2, 3, 0} ✕
[V]: {1, 3, 0, 2}
[V]: {1, 3, 2, 0} ✕
[V]: {2, 0, 1, 3}
[V]: {2, 0, 3, 1} ✕
[V]: {2, 1, 0, 3}
[V]: {2, 1, 3, 0} ✕
[V]: {2, 3, 0, 1}
[V]: {2, 3, 1, 0} ✕
[V]: {3, 0, 1, 2}
[V]: {3, 0, 2, 1} ✕
[V]: {3, 1, 0, 2}
[V]: {3, 1, 2, 0} ✕
[V]: {3, 2, 0, 1}
[V]: {3, 2, 1, 0} ✕

N=6の場合はどうか

    ll N = 6;
    VI V;
    ll cnt=0;
    rep(i, 6){
      V.push_back(i);
    }
    do{
      debug(V);
      cnt++;
      //reverse(V.begin()+N/2,V.end()); // 後半半分をリバースする
    }while(next_permutation(ALL(V)));
    debug(cnt);

720回
reverseを入れると、120回 (1/6になっている)

N=8の場合

reverseなし40320
reverseあり1680
1/24になっている

N=4, 6, 8を一般化する

N=4の場合、[4, 3, 2, 1]を考えた時の後半部分 2x1
N=6の場合、[6, 5, 4, 3, 2, 1]を考えた時の後半部分 3x2x1
N=8の場合、[8, 7, 6, 5, 4, 3, 2, 1]を考えた時の後半部分 4x3x2x1
これだけ減る
next_permutaion N!
next_partial_permutation nPr

実践

No.699 ペアでチームを作ろう２ https://yukicoder.me/problems/no/699
N=14
14! = 87178291200 TLE
reverseを入れると、14! / 7! = 17297280 間に合う
なぜnext_partial_permutationでいいのかの説明
- http://cielavenir.github.io/blog/2018/06/10/pair-team/

通るコード例

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    ll ans = 0;
    do {
        ll s = 0;
        for (int i = 0; i < n / 2; i++) s ^= (a[i] + a[i + n / 2]);
        ans = max(ans, s);
        reverse(a.begin() + n / 2, a.end());
    } while (next_permutation(a.begin(), a.end()));
    cout << ans << endl;
    return 0;
}