suzu-log/g86

LiosK問題

21:48 |

この問題はどう解けばいいんだ？ / LiosK-free Blog

この実験に割り当てる問題で、最大で人数を11人、実験の数を20、一つの実験の容量を10と仮定する。

次のrecurという関数が表す状態を考える。状態の数は最大で(2の10乗*20*10)存在する。

recurは次の引数をとり、この状態のときに条件を満たす実験の数が最大でいくつできるかを返す。

• 1. 誰が既に実験に割り当てられたかのビットmask
• 2. 現在の実験番号expNum
• 3. 現在の実験に割り当てられる残り人数curCap

実験番号はそれぞれの実験に割り当てられた番号で0からはじまる。

誰が既に実験に割り当てられたかというmaskという引数は人数の数分の幅を持つビットで、例えば4人のとき(0, 1, 2, 3番目の人がいるとして)

• maskの値が1だったら2進数で0001なので0番目の人はもう実験に割り当てられないということ。
• maskの値が6だったら2進数で0110なので2番目の人と1番目の人は実験に割り当てられないということ。

以上の引数を持つrecurは自分自身を再帰的に呼び出して、さまざまな状態に移ったときの最大値を使って自分が返す値を求める。

• 1. 現在の実験にさらに人を割り当てる
• 2. 現在の実験に人を割り当てるのをやめ、次の実験に人を割り当てはじめる

ちなみに

• 求めたい値はrecur(0<既に割り当てられた人を表すビット>, 0<最初の実験の実験番号>, ?<0番目の実験の最大人数>)である。
• dpという配列は一度しらべた関数の値を記憶しておくために使っている。
• 条件を満たす最大の実験数しか教えてくれない(そのときにどんな割当になっているかを教えてくれない)ので役に立たない。

また、テストケースも1つしかやってないので間違っている可能性が高い。つまりは上のような手法があるよ、ということを伝えたかっただけ。

#include <vector>
#include <queue>
#include <iostream>

using namespace std;

#define Fill(a, b) memset(a, b, sizeof(a))


typedef vector<int> vi;
typedef vector<string> vs;

class MatchExperiments {
public:
  vector <vector <bool> > mc;
  vi ec;
  vi em;
  int memN;
  int expN;
  int dp[1<<10][20][10];
  int recur(int mask, int expNum, int curCap) {
    int tmpmax = 0;
    if (dp[mask][expNum][curCap] != -1) {
      return dp[mask][expNum][curCap];
    }
    if (expNum >= expN) {
      return 0;
    }
    if (curCap < 1) {
      // 実験[expNum]が人でいっぱいになったとき. 最小限の人数は確保されている
      return 1 + recur(mask, expNum+1, ec[expNum+1]);
    }

    // 現在の実験に人をさらに割り当てるとき
    for (int i=0; i<memN; i++) {
      if ((mask&(1<<i)) == 0 && mc[i][expNum]) {
	// 実験に割り当てられていないi番目の人を実験[expNum]に割り当ててみる
	tmpmax = max(tmpmax, recur(mask|(1<<i), expNum, curCap-1));
      }
    }

    // 現在の実験に人を割り当てるのをやめて、次の実験に進んだ場合
    if (em[expNum] <= ec[expNum] - curCap) {
      // 次の実験に移る際に、実験[expNum]が最小限の人数を確保しているとき
      tmpmax = max(tmpmax, 1 + recur(mask, expNum+1, ec[expNum+1]));
    } else {
      // 次の実験に移るけど、最小限の人数を確保しいていないとき
      tmpmax = max(tmpmax, recur(mask, expNum+1, ec[expNum+1]));
    }
    dp[mask][expNum][curCap] = tmpmax;
    return tmpmax;
  }  
  int mostExperiments(vector <vector <bool> > memberConditions,
		      vector <int> expCapacities,
		      vector <int> expMinCapacities){
    mc = memberConditions;
    ec = expCapacities;
    em = expMinCapacities;
    memN = mc.size();
    expN = ec.size();
    Fill(dp, -1);
    return recur(0, 0, ec[0]);
  }

private:
  void verify_case(int Case, const int &Expected, const int &Received) {
    cerr << "Test Case #" << Case << "...";
    if (Expected == Received) cerr << "PASSED" << endl;
    else {
      cerr << "FAILED" << endl;
      cerr << "\tExpected: \"" << Expected << '\"' << endl;
      cerr << "\tReceived: \"" << Received << '\"' << endl;
    }
  }
  void test_case_0() {
    // Boolean of who accept which experiment
    vector<vector <bool> > Arg0(4);
    vector <bool> t0(4);
    t0[0] = true; t0[1] = false; t0[2] = true; t0[3] = true;
    Arg0[0] = t0;

    vector <bool> t1(4);
    t1[0] = true; t1[1] = true; t1[2] = true; t1[3] = true;
    Arg0[1] = t1;

    vector <bool> t2(4);
    t2[0] = false; t2[1] = false; t2[2] = true; t2[3] = true;
    Arg0[2] = t2;

    vector <bool> t3(4);
    t3[0] = true; t3[1] = true; t3[2] = true; t3[3] = false;
    Arg0[3] = t3;

    // Capacities
    vector<int> Arg1(4);
    Arg1[0] = 1; Arg1[1] = 2; Arg1[2] = 4; Arg1[3] = 2;

    // Minimum Capacities
    vector<int> Arg2(4); // Minimam capacities
    Arg2[0] = 1; Arg2[1] = 1; Arg2[2] = 3; Arg2[3] = 2;
    int Arg3 = 3;
    verify_case(0, Arg3, mostExperiments(Arg0, Arg1, Arg2)); 
  }

public:
  void run_test(int Case) {
    if ((Case == -1) || (Case == 0)) test_case_0();
  }
};

int main() {
  MatchExperiments ___test;

  ___test.run_test(0);
  
}

テストvector <vector <bool> >の定義、もっといい方法ないのかなぁ。

vector <vector <bool> > Arg0 = {{false, false, true}, {true, false, true}, {false, true, false}};

みたいにやりたい。

ちなみにこの解放はTopCoder SRM397Div.2 1000の問題の解法を参考にしてみました。

また、「参加できる実験が少ない人を、割当人数下限の一番少ない実験に割り当てていく」というid:Mishoのシンプルな解法があるので、id:MIshoがそれを書いてくれると思います。