2012年5月2日水曜日

GCJ2012 Round 1A Problem B. 問題紹介

Google Code Jam 2012 Round 1A
Problem B. Kingdom Rush 問題紹介

Kingdom Rush というタワーディフェンスゲームをモチーフにしたということですが、、、あまりそんな感じはしません。もちろんゲームのことを何も知らなくても問題は解けます。

この問題に出てくる Kingdom Rush では、ステージ(level)をクリアして星(★)を集めていきます。各ステージでは最大2つまで星を獲得できます。
  • 1つ星条件(星いくつ持っていること)を達成していれば星を1つ獲得します。
  • 2つ星条件(星いくつ持っていること)を達成していれば星を2つ獲得します。
  • 既に1つ星を獲得したステージでも2つ星条件を達成していればもう1つ星を獲得できます。(各ステージで2つまで星を獲得できます)
全ての星(ステージ数×2)を集めるのにかかる最短手数(ゲーム数)を求める問題です。
※ステージの星条件によっては解がないケースもあります。

例:
  • ステージ1: 1つ星条件=星0個  2つ星条件=星1個
  • ステージ2: 1つ星条件=星0個  2つ星条件=星2個
このとき、次の手順で進めると最短手数で全ての星をコンプリートすることができます。
  1. ステージ1の1つ星条件(星0個)を達成しているので星1つ獲得
  2. ステージ1の2つ星条件(星1個)を達成しているのでもう1つ獲得
  3. ステージ2の2つ星条件(星2個)を達成しているので星2つ獲得

入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの1行目はステージ数 N
その後N行、各ステージの1つ星条件 ai と2つ星条件 bi がスペース区切りで続きます。

データ制限:
  • 1 ≤ T ≤ 100 (問題数は100問)
  • Small input の場合:1 ≤ N ≤ 10 (最大10ステージ)
    Large input の場合:1 ≤ N ≤ 1000 (最大1000ステージ)
  • 0 ≤ ai ≤ bi ≤ 2001 (1つ星条件、2つ星条件)

解き方はこちら

0 件のコメント:

コメントを投稿