ABC236 D問題

言語はC++である。
後で自分が復習できるように、解けなかったABC236のD問題の記録をしてみる。
この問題の肝は結局、”ペアの分け方”をいかに効率よく探索するかにある。
ここでは再帰を用いて書く。（初心者なのでわからないがこれをdfsとは呼ばないと思う。）

順を追って説明していく。その前に必要最低限

# include <iostream>
# include <vector>
using namespace std;
using ll = long long;

を書く。

まず、main関数の外側にグローバル変数として

int n;
vector<vector<ll>> a(20,vector<ll>(20,0));

を取る。nは問題文のN、配列aは『相性』を格納するものである。
面倒なので最初からaはnに寄らず、20*20で取っておく。

ここからmain関数の中。
aの代入。( 今後参照する上三角部分にだけ代入を行う。 )

for (int i = 0;i<2*n-1;i++){
        for (int j = i+1;j<2*n;j++){
            cin>>a[i][j];
        }
}

さて、ここからが本題。
今 0 ~ 2*n-1 人、人がいて、２組ずつに分ける組み合わせを全通り探索したい。
探索の仕方はいたって単純で、
まず、0とペアになる人iを取る。

次に0,i以外の2*(n-1)人に関して、最小の人vを取る。
vとペアになる人 j をとる。

ということをひたすらやっていけばいい。
ここで誰を取ったのかを記録する配列が必要になる。

vector<int> list(2*n,0);

取られていない場合は0に取った後は1と記録する。
まず最初に人0を取る。
よって

list[0] = 1;

また、最大値を求めたいので常に変数maxを
後ほど定義する再帰関数に参照渡ししていく。

ll max = 0;

比較しながら最終的に最大値を格納するので最初は0に初期化しておく。

人0とペアになる候補は人1~2*n-1がいる。これらをそれぞれ0のペアとして採用して
次のペアの探索に移る。

for (int i=1;i<2*n;i++){
        search(max,i,list,a[0][i]);
    }

search関数がペアを探索していく再帰関数である。
引数は上で定義したmax
0のペアとなった人 i
取った人を記録していく配列 list
0とiの相性
である。ここでmax以外は値渡しである。

それではsearch関数の中身を見ていこう。

void search (ll &max,int u,vector<int> list,ll sub){
    list[u] = 1;

    int v;
    if (check(list)) {
        if (max < sub) max = sub;
    }else{
        for (int i=1;i<2*n;i++){
            if (list[i] != 0) continue;
            v = i;
            list[i] = 1;
            break;
        }

        for (int i=1;i<2*n;i++){
            if (list[i]!=0)continue;
            search (max,i,list,sub^a[v][i]);
        }
    }


}

0のペアがiからuに置き換わることに注意して、
まず、0のペアとしてuを取ったのでlistにuを取ったことを記録する。

if文は再帰の終点だけれどひとまず無視しよう。
次にやることは0,u以外の2*(n-1)人の中からまたペアを作る子である。
そこで、2*(n-1)人の中から最小の人vを見つけてくる。
それでまた、人0でやったのと同じように、vのペア候補を見つけてくる。
ペア候補は、listにチェックしていない2*(n-1)-1人の人である。

こうやってひたすらペアを作っていき
listが全て１になった時点でペアが組み終わる。
これが再帰関数searchの終点である。
この時listの全ての要素が1となっている。
listが全て１になっているかどうかは次の関数checkで行う。

bool check(vector<int> &list){
    bool flag=true;
    for (auto& x:list){
        if (x != 1){
            flag = false;
            break;
        }
    }
    return flag;
}

この段階で、このペアの組み合わせにおける排他的論理和が求まっているので
maxとの大小比較を行い、より大きければmaxを置き換える。

最後にコードの全文をのせる。

# include <iostream>
# include <vector>


using namespace std;
using ll = long long;

 int n; 
vector<vector<ll>> a(20,vector<ll>(20,0));

bool check(vector<int> &list){
    bool flag=true;
    for (auto& x:list){
        if (x != 1){
            flag = false;
            break;
        }
    }
    return flag;
}

void search (ll &max,int u,vector<int> list,ll sub){
    list[u] = 1;

    int v;
    if (check(list)) {
        if (max < sub) max = sub;
    }else{
        for (int i=1;i<2*n;i++){
            if (list[i] != 0) continue;
            v = i;
            list[i] = 1;
            break;
        }

        for (int i=1;i<2*n;i++){
            if (list[i]!=0)continue;
            search(max,i,list,sub^a[v][i]);
        }
    }
}

int main(){
    cin>> n;

    for (int i = 0;i<2*n-1;i++){
        for (int j = i+1;j<2*n;j++){
            cin>>a[i][j];
        }
    }


    vector<int> list(2*n,0);
    list[0] = 1; 
    ll max  = 0;
    for (int i=1;i<2*n;i++){
        search(max,i,list,a[0][i]);
    }

    cout<<max<<endl;



    return 0;
}