ferinの競プロ帳

競プロについてのメモ

tco2017 Pittsburgh Regional round med

概要

数列のどの要素の3つ組を取っても和が9の倍数とならないような最大の部分集合の大きさを求める。

考えたこと

コンテスト中の誤った思考を書いてるだけ。
与えられる数列の要素は200以下なので3乗くらいまでできそう。試しに9の倍数になる3つ組を全列挙してみる。3つ組のいずれかの要素を部分集合に含まなければその3つ組によって条件を満たさなくなることはない。したがって全ての3つ組でいづれかの要素を答えとなる部分集合の候補から消していくと考えると集合の全ての要素を覆うような集合を選べばよさそうとなりこれを解く方法を永遠と考える。
愚直にやるとO(3n3)で明らかに不可能。フローやDPなど色々考えるが思い浮かばない。典型問題でありそうと思いググっていると集合被覆問題でこれはNP問題であることをコンテスト終了5分前に知り絶望する。
challenge中にコードを読むとmod 9を取って探索しているコードを見つける。
コンテスト終了後に解説tweetを読むとmod9が0~8の要素がそれぞれ0個、1個、2個、3個以上の4パターンに分類し49の全探索をするとあるので強い人のコードを見つつ実装したら通った。

学び

典型そうな問題に帰着できたらとりあえずググる
倍数について考えるときはmodを取る。

// BEGIN CUT HERE
// END CUT HERE
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

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

int cnt[100], take[100];

bool check(int a, int b, int c) {
  int tot_a = 1+(b==a)+(c==a),
      tot_b = 1+(a==b)+(c==b),
      tot_c = 1+(a==c)+(b==c);
  return (take[a] >= tot_a && take[b] >= tot_b && take[c] >= tot_c);
}

class Avoid9 {
  public:
  int maxSizeOf9Free(vector<int> A)
  {
    memset(cnt, 0, sizeof(cnt));
    REP(i, A.size()) cnt[A[i]%9]++;

    // mod9の値の0~8が0個、1個、2個、3個以上の4パターンを全探索4^9
    int ans = -1;
    REP(i, 1LL<<18) {
      // iを4進数みたいに見る
      int tmp = i;
      REP(j, 9) {take[j] = tmp%4; tmp/=4;}
      // 4進数のそれぞれの桁の値からjの個数を決める
      int ret = 0;
      REP(j, 9) {
        if(take[j] == 3) ret += cnt[j];
        else ret += take[j];
        if(take[j] > cnt[j]) ret = -INF;
      }
      if(ret<=ans) continue;

      REP(j, 9) FOR(k, j, 9) {
        // (j, k, q) の組を選ぶと9の倍数になる
        int q = (9-(j+k)%9)%9;
        // 9の倍数となるような3つ組が部分集合に存在するような選び方
        if(check(j, k, q)) {ret = -INF; break;}
      }
      chmax(ans, ret);
    }

    // 答えが存在しない
    if(ans < 3) ans = -1;
    return ans;
  }
};