TopCoder SRM192 Div2 250Pts

今日のTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

問題を簡単に和訳する。

機械的に箱に物を詰めることを考える。箱も物も直方体の形をしている。箱に対して、物を最大でいくつ詰めることができるかを返すメソッドを作成する。ただし、以下の点に注意する必要がある。

• 物は箱のすべての辺に対して平行になるよう置かなければならない
• すべての物は同じ向きになっている(空いた隙間に物の向きを変えて詰めるのはダメ)

例えば、100*98*81の箱に3*5*7の物を詰めると、5*7*3に物の向きを変えてつめれば、最大で20*14*27=7560個の物を詰めることができる。

私の解答はこちら。箱に対して、6通りの物の置き方があるということなので、それをfor文で表現する方法を思いつくのに時間がかかった。

public class BoxLoader {
 public int mostItems(int boxX, int boxY, int boxZ, int itemX, int itemY, int itemZ) {
  # 物のある辺が大きすぎる場合(実はこの下の行は不要)
  if( max3(boxX,boxY,boxZ) < max3(itemX,itemY,itemZ) ) return 0;
  int items[] ={itemX,itemY,itemZ};
  int ratio[] = new int [3];
  int inbox = 0;
  for( int i=0 ; i<3 ; i++ ){
   for( int j=0 ; j<3 ; j++ ){
    for( int k=0 ; k<3 ; k++ ){
     if( i!=j && j!=k && k!= i){ # i,j,kに重複がない
      ratio[0] = boxX / items[i]; # 何個分X,Y,Z方向は箱を置けるか
      ratio[1] = boxY / items[j];
      ratio[2] = boxZ / items[k];
      int mul = ratio[0]*ratio[1]*ratio[2]; # 箱を置ける数
      if( inbox < mul ) inbox = mul; # 最大値を更新
     }
    }
   }
  }
  return inbox;
 }
 private int max3(int a,int b,int c){
  int tmp = Math.max(a, b);
  return Math.max(tmp,c);
 }
}

得点は214.97/250。正解率は約84%。全体の傾向を見ていると、正解率は低くないのですが、解答までに時間のかかる比較的難易度の高い問題でした。コードレビューをしますと、最初のmax3は不要ですね。後半のfor文ですべて計算可能ということに提出後に気付きました。あと、最大を求める数学関数は、できれば可変長引数(一度に全部引数を与えられる)にして計算できないかと思います。