SRM 469 Div2 Hard TheMoviesLevelThreeDivTwo

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10903&rd=14152

JohnとBrusはN本の映画をレビューする。JohnとBrusが映画iを視聴するのにかかる時間はそれぞれtimeJ[i]、timeB[i]とする。まずN本の映画をJohnとBrusに配り、Johnが映画を見終えたら、Brusの視聴キューに入れ、Brusが映画を見終えたらその映画をJohnの視聴キューに入れる。二人は自分のキューに映画がなくなった場合は以降の視聴を中止する。二人とも視聴を中止した時点で二人共すべての映画を見終わっているような、最初の映画の配り方の総数を求めよ。

やりかた

Practice Room を参考にしました。
すべての配り方を全列挙する。
問題は無事にその初期状態から見終えることができるかである。これはその初期状態から
1)Johnが無事にすべて見終えることができるか
2)Brusが無事にすべて見終えることができるか
を調べ、両方okなら良い配り方であることがわかる。言い換えると
1)Brusが初期キューの映画をすべて見きって、Johnに渡せるか
2)Johnが初期キューの映画をすべて見きって、Brusに渡せるか
ということになる。つまり両者がお互いの初期キューを問題なく相手に渡せればいい。

1)の確かめ方
Brusが自身の初期キューの①「1つ目の映画」を見きって、次の映画も見るためには①がJohnの初期キューの総視聴時間より早く終わる必要がある。無事見終わればこれをJohnに渡してJohnの総視聴時間は＋①になる。
続いて、Brusが自身の初期キューの②「2つ目の映画」を見きって、次の映画も見るためには①＋②がJohnの総視聴時間より早く終わる必要がある。無事見終わればこれをJohnに渡してJohnの総視聴時間は＋②になる。
続いて、Brusが自身の初期キューの③「3つ目の映画」を見きって、次の映画も見るためには①＋②＋③がJohnの総視聴時間より早く終わる必要がある。無事見終わればこれをJohnに渡してJohnの総視聴時間は＋③になる。
このようにしてBrusが初期キューの映画を見終えることができるかどうか判定できる。

2)についてもJohnとBrusの立場を逆にして同じ事を確かめればいい。

このようにしてある配り方が良い配り方かどうか判定できる。

以下ソース。

class TheMoviesLevelThreeDivTwo {
public:
  int find(vector <int> timeJ, vector <int> timeB) {
    int result = 0;
    int N = timeJ.size();
    for(int J = 0; J < 1 << N; J++){
      int B = (1 << N) - 1 - J;
      int jsum = 0, bsum = 0;
      for(int i = 0; i < N; i++) if(J >> i & 1) jsum += timeJ[i];
      for(int i = 0; i < N; i++) if(B >> i & 1) bsum += timeB[i];

      //Johnがすべての映画を受け取るためにBrusは無事初期キューの映画を見切るのか
      int p = jsum, q = 0; 
      for(int i = 0; i < N; i++){
	if(B >> i & 1){
	  q += timeB[i];
	  if(p < q) goto failed;
	  p += timeJ[i];
	}
      }

      //Brusがすべての映画を受け取るためにJohnは無事初期キューの映画を見切るのか
      p = 0, q = bsum; 
      for(int i = 0; i < N; i++){
	if(J >> i & 1){
	  p += timeJ[i];
	  if(q < p) goto failed;
	  q += timeB[i];
	}
      }
      result++;
    failed:;
    }
    return result;
  }
};

以下以前に書いた記事。一応残しておく。

Editorialを参考にした。
すべての配り方を全列挙する。
まず二人共映画視聴を止めた後にBrusが全部の映画を見終えているかどうかを判定する。
判定のこまかいことはソースを参照。
Johnの判定についてはビットを反転させ、視聴時間に関する引数をひっくり返せば同じ。

class TheMoviesLevelThreeDivTwo {
public:
  bool good(int mask, vector<int> q1, vector<int> q2){
    int N = q1.size();
    //q1の人が最初に配られた映画を見るのにかかる時間
    int t1 = 0;
    for(int i = 0; i < N; i++) if(mask >> i & 1) t1 += q1[i];
    int t2 = 0;
    for(int i = 0; i < N; i++){
      if(!(mask >> i & 1)){ 
        //t2はq2の人が映画iを見終えた時の時間
	t2 += q2[i];
        //q1の人はq2の人より早く初期キュー映画を見終えてしまうとこの映画iは視聴できない
        //それと同じか遅ければ視聴できる
	if(t2 <= t1) t1 += q1[i];
	else return false;
      }
    }
    return true;
  }
  int find(vector <int> timeJ, vector <int> timeB) {
    int result = 0;
    int N = timeJ.size();
    for(int S = 1; S < (1 << N) - 1; S++)
      if(good(S, timeJ, timeB) && good(~S, timeB, timeJ))
	result++;
    return result;
  }
};

誤読をやっておかしなことをしていた。きちんと読んでいても出来なかっただろうなあ。まだよく理解できてないし。Editorialの答えもクッソいけててガチしょんぼり沈殿丸。はあ。