Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-05-22Google Code Jam 2011 Round 1A

Google Code Jam 2011 Round 1A C Pseudominion

| 23:13 | Google Code Jam 2011 Round 1A C Pseudominion - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 1A C Pseudominion - SRM diary(Sigmar) Google Code Jam 2011 Round 1A C Pseudominion - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

残り30分弱では解けませんでした

以下は終了後の検討内容


まず、turnボーナスは手に入ったと同時に全部使ってしまったほうが良いのは明らか

turnボーナスが0のものはどう考えれば良いかという問題になるが、ここではcardボーナスの最大値が小さいのが重要なポイント

smallはcardボーナスが最大1なので、smallから考える


cardボーナスが1のものをc1、0のものをc0というグループに分ける

ここでc1及びc0を使用枚数を固定すると、各グループの中ではどんな順番で使ってもscore以外の状態が変わらない

従って、各グループの中ではscoreボーナスが大きい順に使ったほうが良いのだろうということになる

また、c1とc0についてはc1を先に使ったほうが選択肢が広がるため、まずc1をスコアが大きい順に使用し、次にc0をスコアが大きい順に使うという順序になる

あとはc1の使用枚数を全探索すれば、答えが出る。


ということで、Largeも同様にできそうであるが、実はこの考え方だとc2が登場するだけで劇的に難しくなる

ストレートフォワードに考えれば、選択肢を広げるため、c2をスコアが大きい順に使用し、c1を使用し、c0を使用し・・・という順番で良さそうに見えるが、これではWAとなる

以下のようなのが反例

(ここでは前からN枚が手札、後ろのM枚がデッキとする)

N=3, M=3

c={0,1,2,2,0,0}

s={0,6,1,5,0,0}

t={2,0,0,0,0,0}

上記の例で最適なパスは以下の通り

  1. card0使用, card:1,2, score:0, turn:2
  2. card1使用, card:2,3, score:6, turn:1
  3. card3使用, card:2,4,5, score:11, turn:0

c1のcard1より先にc2のcard2を使用すると、スコアは7にしかならない。

これは、c1でゲットしたカード内に手札のc2よりスコアの高いc2が入っていたからである。

なので無条件にc2から進めてもダメである。

ということで、c1とc2の使用タイミングを探索しようとすると、計算量が爆発する

そこで、以下のような条件を利用してDPする

  • c1とc2の使用した枚数が同じであれば、結果的にゲットしたカード(使用したものを含む)は常に同じになる
  • c1とc2の使用した枚数が同じであれば、よりスコアボーナスの大きいものを使用したほうが望ましい

ということでc1とc2の使用枚数を状態とすると、そのときのスコアが高いものだけを使用するDPが利用できる

ただし、例外があるので注意が必要である。

以下のような反例を考える。(これは上記の例のcard4のturnボーナスのみを変更したものである)

N=3, M=3

c={0,1,2,2,0,0}

s={0,6,1,5,0,0}

t={2,0,0,0,2,0}

上記の例で最適なパスは以下の通り

  1. card0使用, card:1,2, score:0, turn:2
  2. card2使用, card:1,3,4, score:1, turn:1
  3. card4使用, card:1,3, score:1, turn:2
  4. card1使用, card:3,5, score:7, turn:1
  5. card3使用, card:5, score:12, turn:0

card0,2,4,1の順で使っても、card0,1,3の順で使っても、c1とc2の使用枚数は同じであるが、0,1,3の順で使用すると残りのturn数が0となってしまい0,2,4,1の順より損である

これは、turnボーナスのカードがturn0のときに使えないという制約のためである。

従って、turnが0となる場合は、そうでない場合と区別して扱う必要がある。

これを踏まえてコーディングすると一応通る。

計算量はn=N+Mとすると、O(n^3log n)くらい?

なお公式の解説にはもっとコーナーケースを考えなくてよさそうなO(n^5)のDPが載ってました


ソースコード

Small専用。比較的簡単。

class GCJ {
public:
	int N, M;
	vector <int> c, s, t;

	//turnボーナスを全て使用する
	int get_turn_bonus(int begin, int end, int &score, int &turn) {
		if(turn<=0) return end;
		int nend=end;
		while(begin<end) {
			for(int card=begin; card<end; card++) {
				if(t[card]>0) {
					turn+=t[card]-1;
					score+=s[card];
					nend+=c[card];
				}
			}
			if(nend>N+M) nend=N+M;
			begin=end;
			end=nend;
		}
		return end;
	}

	//指定した範囲のカードをcardボーナスの値に応じてpriority_queueに振り分ける
	void classify_card(int begin, int end, priority_queue <int> &c0, priority_queue <int> &c1) {
		for(int card=begin; card<end; card++) {
			if(t[card]==0) {
				if(c[card]==0) c0.push(s[card]);
				else if(c[card]==1) c1.push(s[card]);
				else exit(1);
			}
		}
	}

	//残りの手札内でcardボーナス0のものを全て使用した場合のscoreを計算する
	int calc_score(priority_queue <int> c0, int turn) {
		int res=0;
		while(turn>0 && !c0.empty()) {
			res+=c0.top(); c0.pop();
			turn--;
		}
		return res;
	}

	//本体
	int solve(int N, int M, vector <int> c, vector <int> s, vector <int> t) {
		int res=0;
		
		this->N=N; this->M=M;
		this->c=c; this->s=s; this->t=t;
		priority_queue <int> c0, c1;
		int scard=N, sscore=0, sturn=1;
		scard=get_turn_bonus(0, scard, sscore, sturn);
		classify_card(0, scard, c0, c1);

		res=sscore+calc_score(c0, sturn);
		while(!c1.empty() && sturn>0) {
			int score=c1.top(); c1.pop();
			sscore+=score;
			sturn--;
			int nscard=min(scard+1, N+M);
			nscard=get_turn_bonus(scard, nscard, sscore, sturn);
			classify_card(scard, nscard, c0, c1);
			scard=nscard;
			res=max(res, sscore+calc_score(c0, sturn));
		}

		return res;
	}
};

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");
	int testcase;
	GCJ gcj;

	ifs >> testcase; ifs.ignore();
	for(int test=1; test<=testcase; test++) {
		int N;
		ifs >> N;
		vector <int> c(N), s(N), t(N);
		for(int i=0; i<N; i++) {
			ifs >> c[i] >> s[i] >> t[i];
		}
		int M;
		ifs >> M;
		c.resize(N+M); s.resize(N+M); t.resize(N+M);
		for(int i=N; i<N+M; i++) {
			ifs >> c[i] >> s[i] >> t[i];
		}
		ofs << "Case #" << test << ": " << gcj.solve(N, M, c, s, t) << endl;
	}
}

Large用。もちろんSmallも通る。

DP部分は幅優先探索で書いている。

main関数はsmallと一緒なので省略

	rem_sbonus[
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110522