TopCoder SRM284 Div2 250Pts

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

山積みされた荷物を倉庫からトラックに載せたいと思っている。計画では荷物は2つの荷物に分けるということをトラックに載せられる量になるまで繰り返す(もちろん奇数の荷物を半分に分けるというのは、片方が他方より1つだけ荷物が多い状態にすることである)。問題は荷物を載せるのにトラックがいくつ必要になるかということである。numCreatesという荷物の数と、loadSizeというトラックに積み込める荷物の最大個数が与えられたときに、必要となるトラックの数を返すメソッドを作成せよ。

私の解答はこちら。

public class Truckloads {

 public int numTrucks(int numCrates, int loadSize) {
  if( numCrates <= loadSize ) return 1;
  if( numCrates % 2 == 0 ){
   return 2* numTrucks(numCrates/2, loadSize);
  }else{
   return numTrucks(numCrates/2, loadSize) + numTrucks(numCrates/2 + 1 , loadSize);
  }
  // ああそうか的な解答(こちらではif文の分岐が不要になる)
  // return numTrucks(numCrates/2, loadSize) + numTrucks(numCrates/2+ numCrates%2, loadSize);
 }

}

得点は244.77、中央値は約222点。1つ撃墜したので+50点にはなりますが。あまり使う機会はないですが、全員同じように再帰で書くので、再帰も全員必須の共通技術になっているのだなと思いました。