TopCoder SRM253 Div2 250Pts

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

長方形の物体といくつかのサイズが異なる箱が与えられる(この問題では箱の高さは考慮しない)。あたなは、物体を詰めるのに十分なもっとも小さい面積の箱を知りたい。箱に物体を詰めるとき、辺は箱と平行にしなければならない。つまり、物体は0度、90度、180度、270度にしか回転させられない(実際には0度と90度だけ考えればよいのは明らかだが)。

物体の縦横のサイズを表す整数値objWidth、objLengthと箱の縦横のサイズを表すboxWidth[]、boxLength[]が与えられる。2つの配列のi番目の要素がi番目の箱のサイズを表している。物体が収まるもっとも面積が小さい箱の、その面積を返せ。どの箱にも収まらないなら-1を返せ。

私の解答はこちら。

public class ObjectPacking {

 public int smallBox(int objWidth, int objLength, int[] boxWidth, int[] boxLength) {
  int s = Math.min(objWidth, objLength); // 物体の短い辺
  int l = Math.max(objWidth, objLength); // 物体の長い辺
  int minVolume = Integer.MAX_VALUE;
  for( int i=0 ; i<boxWidth.length ; i++ ){
   int si = Math.min(boxWidth[i], boxLength[i]); // i番目の箱の短い辺
   int li = Math.max(boxWidth[i], boxLength[i]); // i番目の箱の長い辺
   if( s <= si && l <= li ){ // 箱に収まる条件
    int vol = si * li;
    if( vol < minVolume) minVolume = si*li;
   }
  }
  return minVolume == Integer.MAX_VALUE ? -1 : minVolume; // 箱に収まるものがあればminVolumeになる。
 }

}

結局、箱を回転させて収められるという制約は、物体の縦横の小さい辺と大きい辺がそれぞれ、i番目の箱の小さい辺と大きい辺に収まるという"置き換え"ができるか否かに尽きるような問題でした。