SRM 680 Div2 Hard - BearFair2

問題

TopCoder Statistics - Problem Statement

問題概要

次のような条件を満たす数字の集合が存在するか判定せよ。

• 集合の要素数はであり、各要素は互いに異なる正の値である。
• はで割り切れる数である。
• すべての要素は以上以下である。
• 集合の要素に関して、ちょうど個はで割り切れ、別の個はで割ると余り、また別の個はで割ると余る数である。

そして、この集合に関してのヒントが個与えられる。そのヒントの内容とは、「からまでの値に限定して注目すれば、集合の要素数は個である」というものである。

アイデア

まず、ヒントを組として扱うためにペアを作成し、の値をキーとしてソートしておく。この時、後の作業を扱いやすくするために、(0,0)と(b,n)というペアを加えておいた状態でソートする。

ヒントの形式から、集合が存在するならばの値が増加する時にの値も単調増加になるはずである。よってこのような条件を満たさない場合を弾いておく。

あとは、再帰的に存在を調べていく。集合の数を選ぶ動作に関して、値を単調増加的に選んでも問題はないのでそうすることにするとdp[p:3kの数][q:3k+1の数][r:3k+2の数][n:1つ前に選んだ数] = true/falseを保存しておいて再帰関数を呼ぶことによってで計算できる。

再帰関数を進めていく時にどの数を選ぶことが出来るかということについてはヒントを使ってその範囲を指定する。まず、今何個目の要素を選ぼうとしているのかがp+q+rによって分かる。すると、これとの値の比較により上限・下限を決定できる。がp+q+r以下なら、その範囲の数字を次の数字として選ぶことは出来ないのでそのような境界の位置をループで探せばよい。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

typedef pair<int,int> pii;

class BearFair2 {
    public:
    vector<pii> v;
    int lim;
    int B;

    //3k,3k+1,3k+2の数、前に選んだ数
    bool dp[18][18][18][1001];

    bool rec(int p, int q, int r, int n){
      int i;

      //すでに見つかっていればそれを返す
      if(dp[p][q][r][n]) return true;

      //この場合ムリなので打ち切る
      if(p>lim/3) return false;
      if(q>lim/3) return false;
      if(r>lim/3) return false;

      bool ret=false;
      if(p+q+r==lim){//終わり
        ret=(p==q && q==r && r==p);
      }
      else{
        int now=p+q+r;
        //上限
        int sup=B;
        //下限
        int inf=n+1;
        rep(i,v.size()-1){
          if(v[i].sc<=now&&now<v[i+1].sc){
            inf=max(inf,v[i].fi+1);
            sup=min(sup,v[i+1].fi);
            break;
          }
        }

        //printf("now %d: n=%d, %d~%d\n",now,n,inf,sup);

        for(i=inf; i<=sup; ++i){
          //printf("call %d\n",i);
          if(i%3==0) ret|=rec(p+1,q,r,i);
          else if(i%3==1) ret|=rec(p,q+1,r,i);
          else ret|=rec(p,q,r+1,i);

          if(ret) break;
        }
      }

      return dp[p][q][r][n]=ret;
    }

    string isFair(int n, int b, vector<int> upTo, vector<int> quantity) {
      int i;

      v.pb(pii(0,0));
      rep(i,upTo.size()) v.pb(pii(upTo[i],quantity[i]));
      v.pb(pii(b,n));
      sort(v.begin(),v.end());

      string ret="unfair";

      bool valid=true;

      rep(i,v.size()-1){
        if(v[i].fi<v[i+1].fi && v[i].sc>v[i+1].sc)
          valid=false;
      }

      if(valid){
        //再帰の前準備
        lim=n;
        B=b;
        memset(dp,0,sizeof(dp));

        if(rec(0,0,0,0)) ret="fair";
      }
      return ret;
    }
};