SRM 520 Div2 Hard SRMSystemTestPhase

問題

SRMというオンラインプログラミングコンテストがあり、コンテストでは3問出題される。複数人のコンテスタントの結果が与えられる。この結果は成績上位から順に並べられたものであるものの、その表記が曖昧で、各人がどの問題を提出したかの情報しか与えられていない。string[i][j]が'Y'であるとき出場者iが問題jを提出したことを示す。'N'であれば提出していないことを示す。
成績は上位から降順に与えられるため出場者iよりi+1が低い成績であるが、ここでの成績の優劣については'passed'した問題数が多いほうが優秀で、同じ数なら'challenged'された問題数が少ないほうが優秀である。これも同じなら優劣に差はなくどちらが前に来ていてもよいとする。
この取組についての取りうるパターンの総数を求め、1000000007で割った余りを返せ。

やりかた

ある取組について、i番目の出場者以降の総パターン数が求まっているならこれは、i番目より上位のパターンがどうあれ、それに影響をうけない。そのためi番目の出場者の結果についての動的計画法で求めていくことができる。

dp[i][j] :=（成績i番目の結果がjであるときの以降の総パターン数）

でDP。回答状況が'Y'のものについて'passed'か'challenged'か'failed'を当てはめてみて探査をかけ、メモ化再帰で無駄な探索を避ければいい。

今回は出場者の成績をintで表すのに100の位を1問目の結果、10の位を2問目の結果、1の位を3問目の結果で表した。

以下ソース。

const ll MOD = 1000000007;

ll dp[60][444];

class SRMSystemTestPhase {
public:
  int N;
  vector<string> desc;
  // 2:passed  1:chellenged  0:failed
  bool valid(int a, int b){
    int ap = (a / 100 == 2) + ((a % 100) / 10 == 2) + (a % 10 == 2);
    int bp = (b / 100 == 2) + ((b % 100) / 10 == 2) + (b % 10 == 2);
    int ac = (a / 100 == 1) + ((a % 100) / 10 == 1) + (a % 10 == 1);
    int bc = (b / 100 == 1) + ((b % 100) / 10 == 1) + (b % 10 == 1);
    if(ap > bp) return true;
    if(ap < bp) return false;
    return ac <= bc;
  }
  
  ll rec(int idx, int s){
    if(idx == N) return 1;
    if(dp[idx][s] > 0) return dp[idx][s];

    ll ret = 0;
    set<int> pattern;
    for(int i = 0; i < 3; i++){
      for(int j = 0; j < 3; j++){
	for(int k = 0; k < 3; k++){
	  int perm  = 0;
	  if(desc[idx][0] == 'Y') perm += 100 * i;	  
	  if(desc[idx][1] == 'Y') perm += 10 * j;
	  if(desc[idx][2] == 'Y') perm += k;

	  if(pattern.insert(perm).second && valid(s, perm))
	    ret = (ret + rec(idx + 1, perm)) % MOD;	  
	}
      }
    }

    return dp[idx][s] = ret;
  }

  int countWays(vector <string> description) {
    int result;
    N = description.size();
    memset(dp, 0, sizeof(dp));
    desc = description;
    return rec(0, 222);
  }
};

できた。よかった。