GCJ2012 Round 1A Problem B. 解き方

Google Code Jam 2012 Round 1A
Problem B. Kingdom Rush 解き方

実践したソースは このあたり にあります。
問題紹介は こちら です。

以下ネタバレ

いかに効率的に星を集めていくか、を考えることになります。

2つ星条件を満たしているステージはどんな順序でクリアしても影響がありません。いつでもあと1回で残っている星（1つ星条件でクリアしていればあと1つ、まだクリアしていなければあと2つ）を全て獲得できるからです。
効率的に（高速に）処理をするためには、2つ星条件が小さい順にソートして星を集めながらループすると、「今クリアできる2つ星条件」を一通り全て処理できるでしょう。

2つ星条件でクリアできるステージがないとき（既にクリアしたステージしかないときも含みます）はやむをえず1つ星条件でクリアして、一旦星1つを獲得します。
このステージを最初から2つ星条件でクリアできていれば1つ星条件でクリアする必要がなかったわけで、いかにこのステップを減らすかが最短手数を求めるためのポイントとなります。

Sampleの4問目を例に見てみます。

• ステージ1: 1つ星条件=星0個  2つ星条件=星5個
• ステージ2: 1つ星条件=星0個  2つ星条件=星1個
• ステージ3: 1つ星条件=星1個  2つ星条件=星1個
• ステージ4: 1つ星条件=星4個  2つ星条件=星7個
• ステージ5: 1つ星条件=星5個  2つ星条件=星6個

最初、持っている星は0個で、2つ星条件を満たすステージはありません。やむをえず1つ星条件の ステージ1 か ステージ2 に挑戦するのですが、どちらを選ぶかでコンプリートまでの手数が変わります。

ステージ1の1つ星条件をクリアする場合:

1.  ステージ1 1つ星条件（星0個） ⇒ 星1個（+1）
2.  ステージ2 2つ星条件（星1個） ⇒ 星3個（+2）
3.  ステージ3 2つ星条件（星1個） ⇒ 星5個（+2）
4.  ステージ1 2つ星条件（星5個） ⇒ 星6個（+1）
5.  ステージ5 2つ星条件（星6個） ⇒ 星8個（+2）
6.  ステージ4 2つ星条件（星7個） ⇒ 星10個（+2）

ステージ2の1つ星条件をクリアする場合:

1.  ステージ2 1つ星条件（星0個） ⇒ 星1個（+1）
2.  ステージ2 2つ星条件（星1個） ⇒ 星2個（+1）
3.  ステージ3 2つ星条件（星1個） ⇒ 星4個（+2）
4.  ステージ4 1つ星条件（星4個） ⇒ 星5個（+1）
5.  ステージ1 2つ星条件（星5個） ⇒ 星7個（+2）
6.  ステージ5 2つ星条件（星6個） ⇒ 星9個（+2）
7.  ステージ4 2つ星条件（星7個） ⇒ 星10個（+1）

後者では手順4.としてステージ1の1つ星条件を選ぶこともできますが、いずれにしても全体で2回1つ星条件を選択する必要があり、前者より手数が増えてしまいます。

1つ星条件でクリアするとき、選択肢が複数ある場合、 「2つ星条件で一気に2つ星クリアしにくい方」を選ぶのが正解です。具体的には2つ星条件が大きいものを選択します。2つ星条件が小さいものの方が一気に2つ星クリアできる可能性が高いので、こちらは残しておきます。

1つ星条件で星を1つ獲得したら、これで他の2つ星条件をクリアできるようになっているかもしれないので、また最初に戻ってクリアできる2つ星条件を探します。
まだクリアしていないステージがあるのに1つ星条件も2つ星条件もクリアできなくなったら “Too Bad” です。