読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

SRM 680 Div2 Hard - BearFair2

programming SRM

問題

TopCoder Statistics - Problem Statement

問題概要

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

  • 集合の要素数nであり、各要素は互いに異なる正の値である。
  • n3で割り切れる数である。
  • すべての要素は1以上b以下である。
  • 集合の要素に関して、ちょうど\displaystyle \frac{n}{3}個は3で割り切れ、別の\displaystyle \frac{n}{3}個は3で割ると1余り、また別の\displaystyle \frac{n}{3}個は3で割ると2余る数である。

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

イデア

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

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

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

再帰関数を進めていく時にどの数を選ぶことが出来るかということについてはヒントを使ってその範囲を指定する。まず、今何個目の要素を選ぼうとしているのかがp+q+rによって分かる。すると、これとquantityの値の比較により上限・下限を決定できる。quantityp+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;
    }
};