TopCoder SRM297 Div2 250Pts

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

箱とパーツの集合が与えられたとき、いくつのパーツが箱に入れられるかということを決められるか尋ねられた。箱には最大で1つのパーツが入れられる。パーツを箱に合わせて入れるには、箱は少なくともパーツ以上のサイズでなければならない。パーツを以下の手続きに従って入れていく。

• まだ箱に入れられてない最小のパーツを選ぶ。
  
• そのパーツが入れられる最小の空箱を見つける。そのような箱がない場合、手続きを終了する。
  
• パーツを箱に入れる。
  
• すべてのパーツが箱に入ったら終了、そうでなければ手順の最初に戻る。
  

partSizes[]というパーツのサイズと、boxSizes[]という箱のサイズを表した整数型の配列がメソッドの引数として与えられる。どちらの配列も昇順で並べられている。以上の手順に従ったとき、箱詰めできるパーツの最大の数を求め、その値を返すメソッドを作成せよ。

私の解答はこちら。

public class PackingParts {

 public int pack(int[] partSizes, int[] boxSizes) {
  int idxPS = partSizes.length-1;
  int idxBS = boxSizes.length-1;
  int nPacked = 0;
  while( true ){
   // 終了条件はすべての箱かパーツをチェックし終えたとき
   if( idxPS < 0 || idxBS < 0 ) break;
   // 箱の方がパーツより大きい
   if( boxSizes[idxBS] >= partSizes[idxPS] ){
    nPacked++;
    idxBS--;
   }
   idxPS--; // 次のパーツを検討する
  }
  return nPacked;
 }

}

得点は227.97/250、中央値は約216点。問題を置き換えると、大きいパーツから順に調べ、残っている箱も大きいほうから見て、入れられるものがあればそれに入れるということになるので、そのような解き方になりました。