問題

D – Dance

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

atcoder.jp

記録

• 2021/1/22 リアルタイム参加。解法わからず。

解法

• 2人組のリストを全パターン作る。
• 各パターンの \(XOR\) を計算し、最大値を求める。

コード例

#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;
}