Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-28

[][] Google Code Jam Round 1A Problem C 18:20 はてなブックマーク -  Google Code Jam Round 1A Problem C - 練習帳

要約

 カードを用いたゲームを行う.それぞれのカードには3つの数字が書かれており,それぞれs(score), c(card), t(turn)と表す.手札に何枚かカードを持ち,残りは山札としてゲームを始める.残りターン数1から初めて,1ターンに次の行動を行う.

  • 手札から好きなカードを1枚切る
  • 捨てたカードに書かれた
    • sの数だけ得点を獲得する
    • cの数だけ山札の上からカードを引く
    • tの数だけターン数を増やす
  • 残りターン数を1消費する
  • 最初に戻る

 手札が0になるか,残りターン数が0になったらゲームは終了する.最初の手札と山札にあるカードが予めすべて分かっているとき,得られる点数の最大値を求めよ.テストケースは100個以下.最初の手札の枚数は1枚以上,山札の枚数は0枚以上で,手札と山札の合計は80枚未満.カードに書かれている数は

small:0 <= c <= 1, 0 <= s <= 20, 0 <= t <= 20

large:0 <= c <= 2, 0 <= s <= 50, 0 <= t <= 50

分析

 まず,手札の中でターン数を増やすもの(つまり t > 0)があればそれを切っても損はしないので,無条件に選ぶ.問題は手札が全てt = 0の時何を切るか.sあるいはcの多いカードから貪欲に切る方法は,例えば次のような反例がある(|の左3枚が手札,右2枚が山札で(s, c) = (9, 0)の方が上).

(残りターン数:2)
s 2 1 0 | 9 0
c 0 1 2 | 0 0

この時は(1, 1), (9, 0)と切ると最高得点10点が得られる.また,同じ手札でも,

(残りターン数:2)
s 2 1 0 | 0 9
c 0 1 2 | 0 0

ならば,(0, 2), (9, 0)と切らないと最高得点とならない.つまり,何を切るかはいまある手札だけではわからない.

という事は,「cの値で手札を分類した時,それぞれのグループで得点が最大のものが次に切るカードの候補である,それらのどれを切るかで動的計画法を行う」のか等と考える.しかし山札の中では後にくるカードを先に切る可能性があるので,それぞれのカードを切った/切っていないで状態を持たなければならず,従って組み合わせ爆発を起こしてしまう.

 この辺りで何をすればよいかが分からなくなったので,解説を読む.自分が気づかなかったのはobservationの2つ目.これがあれば,cの値が同じ2枚のカードがあり,両方とも最終的に切る事になる場合,2枚のうち山札の中で上にある方を先に切ったと仮定してよい.すると,山札を上から順番に走査して切る/切らないを決めていけば良く,後戻りする必要はない.c = 0, 1, 2で分類したとき,どのカードまで切る/切らないかが決まっているかを動的計画法で用いる状態で持てばよい.

コード例

下のコードはkrijgertjeさんのコードを写経したものです.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>

using namespace std;

vector<int> cs, ss, ts;
int n;

int best[81][81];
int memo[81][81][81][81];

// c1 : the position of cards whose bonus of turn is 1 and which is not determined if it is discarded or trumped.
// c2 : bonus of turn is 2. 
// drawn : the largest index of the card drawn. 
// turn : residual turn
// todraw : the number of cards to draw in next turn whose bonus of turn are zero.

int solve(int c1, int c2, int drawn, int turn, int todraw){
  if(turn == 0) return 0;

  // Trump cards at hand whose bonus of turn are more than 0.
  int extra = 0;
  while(todraw > 0 && drawn < n){
    if(ts[drawn] > 0){
      todraw += cs[drawn];
      extra += ss[drawn];
      turn += ts[drawn] - 1;
    }
    todraw--;
    drawn++;
  }
  turn = min(turn, n);
  
  // search for next cards to be considered.
  while(c1 < drawn && (ts[c1] > 0 || cs[c1] != 1)) c1++;
  while(c2 < drawn && (ts[c2] > 0 || cs[c2] != 2)) c2++;

  int ret = memo[c1][c2][drawn][turn];
  if(ret == -1){
    // Points from cards from C0-cards
    ret = best[drawn][min(drawn,turn)];

    if(c1 < drawn){
      // trump C1-card
      ret = max(ret, ss[c1] + solve(c1 + 1, c2, drawn, turn + ts[c1] - 1, cs[c1]));
      // discard C1-card
      ret = max(ret, solve(c1 + 1, c2, drawn, turn, 0));
    }
    if(c2 < drawn){
      // trump C2-card
      ret = max(ret, ss[c2] + solve(c1, c2 + 1, drawn, turn + ts[c2] - 1, cs[c2]));
      // discard C2-card
      ret = max(ret, solve(c1, c2 + 1, drawn, turn, 0));
    }
  }
  
  memo[c1][c2][drawn][turn] = ret ;
  return ret + extra;
}


int main(){
  int t;cin >> t;
  for(int i = 1;i<=t;i++){
    int N;cin >> N;
    cs.clear();cs.resize(N);
    ss.clear();ss.resize(N);
    ts.clear();ts.resize(N);

    for(int j = 0;j <N;j++){
      cin >> cs[j] >> ss[j] >> ts[j];
    }
    int M;cin >> M;
    for(int j = 0;j < M;j++){
      int c,s,t;
      cin >> c >> s >> t;
      cs.push_back(c);
      ss.push_back(s);
      ts.push_back(t);
    }

    n = N + M;

    for(int j = 0 ;j <= n;j++) {
      vector<int> have;
      for(int k = 0; k < j ;k++){
	if(ts[k] == 0 && cs[k]==0)
	  have.push_back(ss[k]);
      }
      sort(have.rbegin(),have.rend());
      best[j][0]=0;
      for(int k =1; k <= j; k++){
	best[j][k] = best[j][k-1] + (k-1 < have.size() ? have[k-1] : 0);
      }
    }

    memset(memo, -1, sizeof(memo));
    int ans = solve(0,0,0,1,N);
    
    cout << "Case #" << i << ": " << ans <<endl;
  }
  return 0;

}

}

||<