D - Dance

問題

大事なところだけ抜粋すると、 を個の2つの組に分ける通り数答えよ。

atcoder.jp

解法

2つの組というところがミソで、うまく数え上げることができなかった。
例えば、{ (1,2), (3,4) } と{ (2,1), (3,4)} は同じになる。
これを回避するには、各要素の右端の数字が小さいように並べれば良い。
以下プロコン部のプロの引用

最も小さい値aと任意の数字b(a≠b)とでペアを作っていくことで遷移の途中で同じ結果の集合が生成されるのを回避できる
みたいなのはよくあるかもしれないです

確かに、各要素に何らかの順序関係を注入するとうまくいきそうな気がする。

実装は最近良く見る形の再帰。これぐらいの制約だと、再帰関数にvectorを値渡しでコピーしてもなんとかなりそうな気がするけど、再帰呼び出し前に条件を更新、呼び出し終了後にその条件を解く方針で実装した。正直まだこの形は苦手。

#include <iostream>
#include <vector>
#include <utility>
#include <numeric>
#include <algorithm>
#include <set>

using namespace std;
using Int = long long;
vector<vector<Int>>g;
vector<bool>used;

Int ans = -1;

void solve(Int tans = -1)
{
    if(find_if(used.begin(),used.end(),[](bool res) { return !res;}) == used.end())
    {
        ans = max(ans,tans); return;
    }
    
    for(int i = 0; i < used.size(); ++i)
    {
        // 未使用で最も小さい値を探す
        if(not used[i])
        {   
            //ペアの数字は適当に選ぶ
            for(int j = i + 1; j < used.size(); ++j)
            {
                if(not used[j])
                {
                    used[i] = used[j] = true;
                    solve((tans == -1 ? g[i][j]  : (tans xor g[i][j])));
                    used[i] = used[j] = false;
                }
            }
            break;
        }
    }
}
int main()
{
    Int N; cin >> N;
    g = vector<vector<Int>>(2 * N,vector<Int>(2* N,-1));
    
    used = vector<bool>(2 * N, false);
  
    for(int i = 0; i < 2 * N - 1; ++i)
    {
        for(int j = 0; j <= 2 * N - 1; ++j)
        {
            if(j <= i)
                g[i][j] = -1;
            else
                cin >> g[i][j];
        }
    }
    
    solve();
    
    cout << ans << endl;
}