TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

Dance

問題

D – Dance
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

/**
 * createPairs()
 * 1 から n までで、
 * 2人組になる組み合わせを全部作る。
 * [v1,v2] としたとき v1 < v2 になる。
 */
int n;
vector<bool> used;
vector<P> pairs;
vector<vector<P>> result;

void createPairs() {
  if((int)pairs.size() == n / 2) {
    result.push_back(pairs);
    return;
  }
  int l = 0;
  for(int i = 1; i <= n; ++i) {
    if(!used[i]) {
      l = i;
      break;
    }
  }
  used[l] = true;
  for(int i = 1; i <= n; ++i) {
    if(!used[i]) {
      pairs.push_back(make_pair(l, i));
      used[i] = true;
      createPairs();
      used[i] = false;
      pairs.pop_back();
    }
  }
  used[l] = false;
  return;
}

int main() {
  int N;
  cin >> N;

  vector<vector<ll>> A(2 * N, vector<ll>(2 * N));
  rep(i, 2 * N - 1) {
    for(int j = i + 1; j < 2 * N; ++j) {
      cin >> A[i][j];
    }
  }

  n = 2 * N;
  used.resize(2 * N + 1);
  createPairs();

  ll ans = 0;
  int v = result.size();
  rep(i, v) {
    ll res = 0;
    rep(j, (int)result[i].size()) {
      int v1 = result[i][j].first;
      int v2 = result[i][j].second;
      if(j == 0) {
        res = A[v1 - 1][v2 - 1];
      } else {
        res = res ^ A[v1 - 1][v2 - 1];
      }
    }
    ans = max(ans, res);
  }

  cout << ans << endl;
  return 0;
}