TopCoder SRM 520 Div1 Medium

SRM

問題

３つの問題の得点の上限と、n人の人がどの問題を解いたかの情報が、総得点が高い順に与えられる。
ある問題を解いた時、その問題の得点として1からその問題の得点の上限までを取る可能性がある。
与えられた通りの順位になる時、各人の各問題の得点を示すスコアボードは何通り考えられるか。
ただし、複数の人が同じ点数を取ることはない。また、総得点は一緒でも各問題の点数が違ったら異なるものとして数える事に注意する。

解法

解法はRespect2Dさんのブログの解法を参考にしました。ありがとうございます。
http://topcoder.g.hatena.ne.jp/Respect2D/20111004#1317752232


３つの問題を解いたか解いてないかの情報は2^3通りある。
それぞれのパターンで0〜200000点を取るとき、各問題の得点の取り方は何通りあるかを計算する。


これには、
DP[S][j] = 解いた問題の集合がSで、総得点がj点のとき、各問題の取り方の場合の数
というような配列を用いてDPをすれば出来そう。


これの更新の仕方を考える。
① 解いた問題が無いとき、
0点しか取れないので、DP[0][0] のみ 1 となる。
② 解いた問題があるとき、
解いた問題のうち１つを選び、iとすると、
DP[S][j] = 解いた問題の集合が「Sからiを抜いたもの」で、得点が「j - その問題の得点」から「j - 1」となる場合の数の和
となる。
なぜなら、解いた問題の集合が「Sからiを抜いたもの」で、得点が「j - その問題の得点」から「j - 1」となるときかつそのときに限り、総得点がjとなるような問題iの点の取り方が１通り存在するからである。


ここで、区間の和が必要となってしまった。単純にやるとこの計算にはO(その問題の得点)かかってしまい更新が間に合わなくなる。そこでBITを使うことになる。
BITの実装には初めてSpaghetti Sourceのもの（Fenwick木）を使った。
後でS,jの値に応じたDPの値をO(1)で取りたいので配列にも入れておく必要がある。この配列をtableとする。

※前準備のDPでも0~jの部分和をsum[j]なんかで別に持てばBITを使わずに出来そうです。


ここまでで前準備が終了した。
次に、スコアボードが何通りあるかを計算する。


これには、
DP[i][j] = i人目(0-indexed)までで総得点の最低点がj点以上の場合の数
という配列を用いてDPする。
ここで、最初に思いつくDPは、
DP[i][j] = i人目(0-indexed)までで総得点の最低点がj点の場合の数
という配列を用いるものである。しかしこれでは1回の更新でO(200000)かかってしまい間に合わない。1個目の配列を用いるとこれに対処する事が出来る。
（ここでもBITを使う事が出来るが、それでもTLEになるっぽい。）



更新の仕方を考える。

① i=0のとき、
2個目の配列の場合では、単純に
DP[0][j] = table[0人目が解いた問題の集合][j]
でいいが、
1個目の配列はj点以上なので、
DP[0][j] = table[0人目が解いた問題の集合][j] + DP[0][j+1]
とし、上からjのループを回す。
② i>0のとき、
i-1人目までで、最低点がj+1点以上ならi人目で最低点をj点とすることができるので、
DP[i][j] = DP[i-1][j+1] * table[i人目が解いた問題の集合][j] + DP[i][j+1]
とすれば良い。


答えはDP[n-1][0]となる。

ソース

typedef long long ll;
ll M = 1000000007;
int table[8][200002];
ll dp[20][200002];
template <class T>
struct fenwick_tree {
  vector<T> x;
  fenwick_tree()  {
    x.assign(400004, 0);
  }
  T sum(int i, int j) {
    if (i == 0) {
      T S = 0;
      for (j; j >= 0; j = (j & (j + 1)) - 1) S = (S + x[j])%M;
      return S;
    } else return (sum(0, j) - sum(0, i-1) + M) % M;
  }
  void add(int k, T a) {
    for (; k < x.size(); k |= k+1) x[k] = (x[k] + a) % M;
  }
};

class SRMIntermissionPhase {
public:
  int countWays(vector <int> points, vector <string> description) {
    memset(table, 0, sizeof(table));
    fenwick_tree<int> fenwick[8];
    fenwick[0].add(0, 1);
    table[0][0] = 1;
    REP(S, 8) {
      REP(i, 3) if (S>>i&1) {
        REP(j, 200002) {
          int hoge = fenwick[S^(1<<i)].sum(j-points[i], j-1);
          fenwick[S].add(j, hoge);
          table[S][j] = hoge;
        }
        break;
      }
    }
    memset(dp, 0, sizeof(dp));
    int n = description.size();
    REP(i, n) {
      int bit = 0;
      REP(j,3) {
        if (description[i][j]=='Y') {
          bit |= 1<<j;
        }
      }
      for (int j=200000; j>=0; --j) {
        dp[i][j] = ((i?dp[i-1][j+1]:1) * table[bit][j] + dp[i][j+1]) % M;
      }
    }
    
    return dp[n-1][0];
  }
};