TopCoder SRM418 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文についておおまかに説明する。

あなたは真剣に戦略ゲームをするプレーヤーなので、敵の防御塔を攻撃するという、もっとも一般的な問題を解くことにした。攻撃をする前にはmyUnitsという数の兵士を得る。各兵士は1回のラウンドにおいて、1つの塔に1のダメージを与えることができる。敵は兵士を持たない。しかしながら、体力がhpTの塔をnumT所持している。各塔は1回のラウンドにおいて、attackTだけの兵士を殺すことができる。1つのラウンドは次の順で行われる。

1. 自軍の各兵士は塔を1つ選び、塔に1のダメージを与える。塔がすべての体力を失うと、塔は破壊される。各兵士ごとに独立して攻撃する塔を選べるものとする。
2. 敵の攻撃になる。敵はk*attackTだけの自軍の兵士を殺すことになる。ここで、kは残っている塔の数である。

あなたの課題はすべての塔を破壊することである。もしそれが可能であれば、それを実行するのに必要な最小限のラウンド数を返せ。もし不可能ならば-1を返すようなメソッドを作成せよ。

私の解答はこちら。

public class Towers {

 public int attack(int myUnits, int hpT, int attackT, int numT) {
  int nTurn = 1; // 攻防を行った回数
  int totalHP = numT * hpT; // 塔の合計体力
  int remainT = numT; // 残っている塔の数
  int remainU = myUnits; // 残っている自軍の兵士数
  while( true ){
   totalHP -= remainU; // 塔の体力を減らす
   if( totalHP <= 0 ) return nTurn; // 塔の体力の合計が0以下なら全部破壊されたことになる
   remainT = (int)Math.ceil(totalHP*1.0/hpT); // 残っている塔の数を計算
   remainU -= remainT * attackT; // 自軍の兵士の数を減らす
   if( remainU <= 0 ) return -1; // もし自軍の兵士が全滅したら-1を返す
   nTurn++;
  }
 }

}

得点は196.74/250、1回のsubmitでシステムテストクリア。中央値は約135点。すべての塔を破壊するにはできるだけ塔を集中的に攻撃するというのが最善になることを利用します。タワーの残り体力を計算する際に、totalHPに1.0を掛けていなかったことに気付くのに少し時間がかかりました。