Google Code Jam 2012 Round1A 問題B

問題

あるゲームで全レベルクリアを目指す。
各レベルには1starと2starのステージがあり、このレベルのクリア条件は2starの方をクリアすることである。
ただし、各レベルの1starステージ、2starステージをやるためには所持スター数が指定されている。

スターは、各ステージをやることで得ることができる。

• まだそのレベルをクリアしてなければ、1starステージをやれば1つスターをもらえる。
• 2starステージをやれば2つスターをもらえる。
• ただし、すでに1starステージをクリア済みの場合、2starステージをクリアしても追加の1つしかもらえない。

やるステージ数が最小になるようにプレイした場合、最小何ステージで全レベルクリアできるかを返す。もし不可能な場合は「Too Bad」を返す。

考え方

greedy。

最初DPかなと思ったけど、各状態(クリア状況、所持スター数)で一意にステージ選択できる。
2starステージをクリアしたいので、もし今の所持スターでやれるステージがあるならばそれをやる。
もしなければ1starステージをやるしかない。
しかし、やれるどのステージを選んでもいいかというと、3つ目の条件の「1starステージがクリア済みなら2starステージクリア済みでも1スターしかもらえない」があるので、できるだけ2starが多い(＝最後のほうでやるステージ)1starステージをやったほうがもらえるスター数が増える。
みんな出してた例だと

	1star	2star
レベル1	0	1
レベル2	0	3

がレベル2の1starステージを選んだ方が、次にレベル1の2starステージを選んだ時もらえるスター数が多い。

反省

問題文をちゃんと読む。
「1starステージは2starステージクリア済みだとプレイできない」はちゃんと読んでなかった。
「1starステージクリア済みだと2starステージクリアしても1スターしかもらえない」は、「1star+2star+ボーナス1star」みたいに各レベルで最大4スターもらえるものだと思ってしたので死。
でもこれはちゃんと問題文を読んでも先入観バリバリだったから気づけたかどうか、、、(例をちゃんと追っていれば、、、)