ZONeエナジープログラミングコンテスト C - MAD TEAM

問題

解法

チームの総合力値を二分探索することで解ける問題。

まず総合力は、可能な値=0、不可能な値=1e9+1(取りうる最大値の値+1) とおくことができる。この範囲で二分探索を行う。

ある値xが成立するかどうかは次のように求めることができる

N人の能力値を5種の能力毎に x 以上かどうかでbitフラグとして持つ
このときsetを使うなどして重複する値は除去する。(3人の各能力値のそれぞれの最大値 が分かればよいので重複する値は除去できる)
3重ループで全探索し、3人(論理和を取るため同じ人を選んでも問題ない)の能力値の論理和がすべてフラグが立っているならばその値xは成立する

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)

int n;
vector<int> a,b,c,d,e;

// 総合値xが成立するならばtrueを返す
bool check(int x) {
  set<int> s;
  REP(i,n) {
    int bit = 0;
    // メンバーの能力値をbitで表す
    // 能力値がx以上であればフラグを立てる
    if (x <= a[i]) bit += 1<<4;
    if (x <= b[i]) bit += 1<<3;
    if (x <= c[i]) bit += 1<<2;
    if (x <= d[i]) bit += 1<<1;
    if (x <= e[i]) bit += 1<<0;
    s.insert(bit);
  }

  for(int i: s) for(int j: s) for(int k: s) {
    // i,j,k の論理和を取りすべてのフラグが立っている状態であればtrue
    // 最小値なのでi,j,kが重複しても構わない
    if ((i|j|k) == (1<<5)-1) return true;
  }
  return false;
}

int binary_search() {
  // ok: 存在する解 ng: 存在しない解
  int ok = 0, ng = 1e9+1;

  while (abs(ok-ng)>1) {
    int mid = (ok+ng)/2;
    check(mid) ? ok = mid : ng = mid;
  }
  return ok;
}

int main() {
  cin >> n;
  a.resize(n); b.resize(n); c.resize(n); d.resize(n); e.resize(n);
  REP(i,n) cin >> a[i] >> b[i] >> c[i] >> d[i] >> e[i];

  cout << binary_search() << endl;
  return 0;
}

雑感

難しいポイント - 二分探索するという発想にたどり着けるかどうか。 - 二分探索で総合値を決め打ったとき、その値が成立するかどうかをどう確かめるか