TopCoder SRM370 Div2 250Pts

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

いくつかのコンテナが1列に並んでおり、パッケージをそれらに入れたいと思っている。最初のコンテナに最初のパッケージを入れることから始める。すべてのパッケージがコンテナに入るまで、以下のことを行う。

1. もしパッケージがコンテナに収まらないなら、ステップ3へ行く、そうでなければ次のステップへ行く。
   
2. パッケージをコンテナにつめる。次のパッケージを手に取り、ステップ1へいく。
   
3. コンテナにこれ以上パッケージを詰められなければ現在のコンテナを追いやる。ラインから次のコンテナを取り、ステップ1へ戻る。
   

containers[]というi番目の要素がi番目のコンテナの容量を示した整数型の配列と、packages[]というi番目の要素がi番目のパッケージの大きさを意味する整数型の配列が与えられる。制約により、すべてのパッケージは上の手続きにより、コンテナに入れることが可能である。全コンテナの無駄な領域の合計を返せ。コンテナ中の無駄な領域とは、総容量から内容量の合計を引いたものになる。

私の解答はこちら。

public class Containers {

 public int wastedSpace(int[] containers, int[] packages) {
  int cPos = 0; // 注目するcontainer
  int pPos = 0; // 注目するpackage
  while( true ){
   int capacity = containers[cPos];
   int total = 0;
   boolean isFinish = false; // packageの終わりに辿りついたらtrueになる
   while( true ){
    if( pPos == packages.length ){
     isFinish = true;
     break;
    }
    if( total + packages[pPos] > capacity ){
     break;
    }else{
     total += packages[pPos++];
    }
   }
   if( isFinish ) break;
   cPos++;
  }
  int sumContainer = 0;
  for( int i=0 ; i<containers.length ; i++ ) sumContainer += containers[i];
  int sumPackage = 0;
  for( int i=0 ; i<packages.length ; i++ ) sumPackage += packages[i];
  return sumContainer - sumPackage;
 }

}

得点は187.11/250、中央値は約216点。1回のsubmitでシステムテストクリア。実はうすうす気づいていたが、単純にコンテナの合計-パッケージの合計でよいのである。制約には「必ず収まる」という条件がついているので、何番目に入れるとか考えなくてもよい。まさかと思いつつも、面倒な実装に走ってしまったのでした。