TopCoder SRM345 Div2 250Pts

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

山の一部を小旅行することを計画している。旅行では歩くのに何日か費やし、夜はテントで過ごすことになる。山はあまり友好的ではない（山は急であり、岩はごつごつしている箇所がある）ため、キャンプをするのに適さない場所が多く存在する。問題ではtrailという歩く場所を順に表した文字列が与えられる。trail[i]が"."であればi番目は泊まるのに適切な場所であるし、"^"であれば適切でないということになる。また、plansという文字列型配列も与えられる。plans[i][j]は"w"であればi番目の計画の位置jでは歩くということを意味し、"C"であればその場所jでキャンプを行うということになる。計画が不適切というのは、キャンプを行うのに不適切な場所でキャンプをするということである。trailとplansに対し、山で過ごすのが最初の日数となる妥当な計画のうち、計画の番号が最小となるものを返せ。すべての計画が不適切であれば、-1を返すようにせよ。

私の解答はこちら。

public class Trekking {

 public int findCamps(String trail, String[] plans) {
  int minNights = trail.length()+1; // 最小値の初期値は取りえない大きめの値に設定
  for( int i=0 ; i<plans.length ; i++ ){
   boolean isValidPlan = true;
   int nNights = 0;
   for( int j=0 ; j<plans[i].length() ; j++ ){
    if( trail.charAt(j) == '^' && plans[i].charAt(j) == 'C' ){
     isValidPlan = false; // 不適切な計画と判明、breakを入れた方が処理が速い
    }
    if( plans[i].charAt(j) == 'C' ){
     nNights++; // 日数をカウント
    }
   }
   if( isValidPlan ){
    minNights = Math.min(minNights, nNights);
   }
  }
  return minNights == trail.length()+1 ? -1 : minNights;
 }

}

得点は231.71/250、中央値は約196点。1回でシステムテストクリア。不適切な計画が明示的にどういう条件か理解すればすぐに解ける。