#1089437 (C++17) No.698 ペアでチームを作ろう

提出ソース
結果

問題	No.698 ペアでチームを作ろう
ユーザー	チョコウサギ
提出日時	2025-05-31 11:04:05
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	5 ms / 1,000 ms
コード長	7,596 bytes
コンパイル時間	8,730 ms
コンパイル使用メモリ	411,692 KB
実行使用メモリ	7,848 KB
最終ジャッジ日時	2025-05-31 11:04:15
合計ジャッジ時間	6,179 ms
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 12
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
#include <atcoder/all> 
using namespace atcoder; 
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
#include <unordered_set>

using namespace std; // std:: を省略

using ll = long long;
using ld = long double;
using i128 = __int128_t;
using ull = unsigned long long;
using P = pair<ll,ll>;

#define rep(i,n) for (ll i = 0; i < ll(n); ++i)
#define REP(i,x,n) for (ll i = x; i < ll(n); ++i)
#define DREP(i, r, l) for (ll i = (ll)(r)-1; i >= (ll)(l); --i)
#define drep(i,n) DREP(i, n, 0)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define MAX *max_element
#define MIN *min_element
#define pb push_back
#define pf push_front
#define ppb pop_back
#define eb emplace_back
#define fi first
#define se second
#define p_queue priority_queue

template<class T, class = void> struct is_iterable : false_type {};
template<class T>
struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>())), decltype(std::end(std::declval<T>()))>> : true_type {};
template<class T> constexpr bool is_iterable_v = is_iterable<T>::value;

// 前方宣言 (debug_pr が debug_tuple の中で使われ、debug_tuple が debug_pr の中で使われる可能性があるため)
template<class T>
std::enable_if_t<!is_iterable_v<T> && !std::is_pointer_v<T> && !std::is_same_v<T, std::string>, void>
debug_pr(const T& x);
void debug_pr(const string& s);
void debug_pr(const char* s);
template<class A,class B> void debug_pr(const pair<A,B>& p);
template<class... Ts> void debug_pr(const tuple<Ts...>& t); // debug_tupleより先に宣言が必要
template<class T>
std::enable_if_t<is_iterable_v<T> && !std::is_same_v<T,string>, void>
debug_pr(const T& v);
void debug_pr(std::nullptr_t);
template<class T>
std::enable_if_t<std::is_pointer_v<T>, void>
debug_pr(const T& p);

// template<size_t I=0,class... Ts>
// std::enable_if_t<I==sizeof...(Ts)> debug_tuple(const tuple<Ts...>&) {}
// template<size_t I=0,class... Ts>
// std::enable_if_t<I<sizeof...(Ts)> debug_tuple(const tuple<Ts...>& t){
//   if(I) cerr << ", "; // 最初の要素でなければコンマを出力
//   debug_pr(std::get<I>(t)); // 現在の要素を出力
//   debug_tuple<I+1>(t);    // 次の要素を処理
// }

// SFINAE を使った enable_if_t の引数の修正
template<size_t I = 0, class... Ts>
typename std::enable_if_t<I == sizeof...(Ts)>
debug_tuple(const tuple<Ts...>&) {
  // ベースケース: タプルの全ての要素を表示し終わったら何もしない
}

template<size_t I = 0, class... Ts>
typename std::enable_if_t<I < sizeof...(Ts)> // 戻り値の型として enable_if_t を使用
debug_tuple(const tuple<Ts...>& t) {
  if (I > 0) { // Iが0より大きい場合（つまり2番目以降の要素の場合）にコンマを出力
    cerr << ", ";
  }
  debug_pr(std::get<I>(t)); // 現在の要素をデバッグ出力
  debug_tuple<I + 1>(t);    // 次の要素を再帰的にデバッグ出力
}

// debug_pr の定義 (ユーザー提供のものをベースに)
template<class T>
std::enable_if_t<!is_iterable_v<T> && !std::is_pointer_v<T> && !std::is_same_v<T, std::string>, void>
debug_pr(const T& x){ cerr << x; }
inline void debug_pr(const string& s){ cerr << '"' << s << '"'; }
inline void debug_pr(const char* s) { cerr << '"' << s << '"'; } // const char* を追加
template<class A,class B> void debug_pr(const pair<A,B>& p){ cerr << '('; debug_pr(p.first); cerr << ", "; debug_pr(p.second); cerr << ')'; }

// tuple 用の debug_pr は debug_tuple を呼び出す
template<class... Ts> void debug_pr(const tuple<Ts...>& t){
  cerr << '(';
  debug_tuple<0>(t); // 常にインデックス0から開始
  cerr << ')';
}

template<class T>
std::enable_if_t<is_iterable_v<T> && !std::is_same_v<T,string>, void>
debug_pr(const T& v){
  cerr << '[';
  bool f = false; // 最初はfalse
  for(const auto& x : v){
    if (f) {
      cerr << ", "; // 2番目以降の要素の前にコンマとスペース
    }
    debug_pr(x);
    f = true;
  }
  cerr << ']';
}
inline void debug_pr(std::nullptr_t) { cerr << "nullptr"; }
template<class T>
std::enable_if_t<std::is_pointer_v<T>, void>
debug_pr(const T& p) {
  if (p == nullptr) {
    cerr << "nullptr";
  } else {
    cerr << '*'; // ポインタであることを示す
    debug_pr(*p); // ポインタの指す先の値を表示
  }
}

void debug_out(){ } // ベースケース
template<class Head, class... Tail>
void debug_out(const Head& h, const Tail&... tl){
  debug_pr(h);
  if constexpr(sizeof...(tl) > 0) { // パラメータパックが空でなければ
    cerr << ", ";
    debug_out(tl...);
  }
}

#ifdef LOCAL
#define dbg(...) cerr << "\e[33m[ " << #__VA_ARGS__ << " ] = ", debug_out(__VA_ARGS__), cerr << " (" << __LINE__ << ")\e[0m" << endl
#else
#define dbg(...) (void)0
#endif

template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) { // pairの出力
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}

inline void println(const long double& x) { cout << fixed << setprecision(30) << x << '\n';}
template<class T> inline bool chmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chmin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template<class... T> inline void input(T&... a) { ((cin >> a), ...); } // 可変長引数入力
template <class T> inline void input(vector<T> &v) { for (T &x : v) cin >> x; } // vector入力
template<class T, class... U> inline void print(const T& a, const U&... b) { cout << a; ((cout << ' ' << b), ...); } // 可変長引数出力 (スペース区切り)
template<class T, class... U> inline void println(const T& a, const U&... b) { print(a, b...); cout << '\n'; } // 可変長引数出力 (スペース区切り + 改行)
inline void println() { cout << '\n'; } // 改行のみ
template<class T> inline void print(vector<T>& A) { rep(i, A.size()) { if (i) cout << ' '; cout << A[i]; } } // vector出力
template<class T> inline void println(vector<T>& A) { print(A); cout << '\n'; } // vector出力 + 改行
inline void yn(bool ok) { cout << (ok ? "Yes\n" : "No\n"); } // Yes/No出力

const ll INF = (1LL << 62) - (1LL << 31) - 1;
const ll mod = 1e9 + 7; 
using mint = modint998244353;

const ll dx[] = {-1,1,0,0,1,1,-1,-1};
const ll dy[] = {0,0,-1,1,1,-1,1,-1};

// 2^nの数え上げはDPで解けるかも?
// 全探索の高速化といえばDP
// DPは配る遷移ともらう遷移の両方を考察する
// 問題の振り返り書け
// めんどくさい計算とかは関数にしたら楽
// 誤差などが怖いときは移項などをして整数で考えるようにする 
// 式変形をしたら見通しが良くなる
// 問題を分解する
// すべての問題を解けると思って考える
// ゲームをしているならDPを考える

// alias xx='g++ -D_GLIBCXX_DEBUG -fsanitize=undefined,address -fno-sanitize-recover=all -Wall -Wextra -Wshadow'


void solve() {
  ll n;
  input(n);
  vector<ll> a(n);
  input(a);
  
  vector<ll> dp((1LL<<n),-1);

  // 1 = 使用済み
  auto f = [&](auto self,ll v) -> ll {

    if(dp[v] != -1) return dp[v];

    if(v == (1LL<<n)-1) {
      return dp[v] = 0;
    }
    ll res = 0;
    rep(i,n) {
      REP(j,i+1,n) {
        if(!(v & (1LL<<i)) && !(v & (1LL<<j))) {
          // 遷移する
          ll bit = v | (1LL<<i);
          bit |= (1LL<<j);
          chmax(res,self(self,bit)+(a[i]^a[j]));
        }
      }
    }
    return dp[v] = res;
  };

  println(f(f,0));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}
yukicoder

結果

ソースコード
