TopCoder SRM323 Div2 250Pts

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

A[]という整数型の配列が与えられる。Kという整数がAに対しirreducible(辞書では約されない、単純化できないという意味)とは、KがAの要素の和で表されないことを表す(各要素は高々1度しか使わない)。Aに対しirreducibleな最小の正の整数を返せ。

私の解答はこちら。この問題はAの要素数が1から3という小さい数なので全部の組合せを作成し、コーディングしています。

import java.util.ArrayList;

public class IrreducibleNumber {

 public int getIrreducible(int[] A) {
  int n = 1;
  ArrayList<Integer> hs = new ArrayList<Integer>();
  // 取り得る値の一覧を作成
  if( A.length == 1){
   hs.add(A[0]);
  }else if( A.length == 2 ){
   int[] list = {A[0], A[1], A[0]+A[1]};
   for( int i=0 ; i<list.length ; i++ ){
    hs.add(list[i]);
   }
  }else{
   int[] list = {A[0], A[1], A[2], A[0]+A[1], A[1]+A[2], A[2]+A[0], A[0]+A[1]+A[2]};
   for( int i=0 ; i<list.length ; i++ ){
    hs.add(list[i]);
   }
  }
  while( true ){ // 1から順番に値を取れるか検索
   boolean isExist = false;
   for( int i=0 ; i<hs.size() ; i++ ){
    if( n == hs.get(i) ) isExist = true;
   }
   if( isExist == false){
    break;
   }
   n++;
  }
  return n;
 }

}

得点は218.78/250、中央値は約215点。Aの最大長が3という制約がないとまともに実装できないコードにしてしまったのが残念、可変長で解けるようにしておきたかった。booleanでどの変数を組み込むかという状態を作成し、2^A.length-1通りためすのが良いのでしょう。ただし、相当重い動作になってしまうのでしょうけれど。