TopCoder SRM196 Div2 250Pts

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

問題について説明する。

数学嫌いでも、ある成績を得るためには何点とったらよいかという計算は役立つと思っている。ここでは平均が90点以上であればA、Aではないが平均80点以上であればB、Bではないが平均70点以上であればC、Cではないが平均60点以上であればDという評価にしよう。最終試験の最低点は0点、最高点は100点であるとする。欲しい成績desireと、過去の試験の点数tests[]が与えられたときに、最終試験で最低何点取ればよいかを返すメソッドを作成せよ。ただし、満点をとっても届かない場合は-1を返すようにせよ。

私の解答は以下の通り。

public class Education {
 public int minimize(String desire, int[] tests) {
  int minScore = 0;
  int total = 0;
  if( desire.equals("A") ){
   minScore = 90;
  }else if( desire.equals("B") ){
   minScore = 80;
  }else if( desire.equals("C") ){
   minScore = 70;
  }else{
   minScore = 60;
  }
  for( int i=0 ; i<tests.length ; i++ ){
   total += tests[i];
  }
  int neededScore = minScore*(tests.length+1)-total;
  if( neededScore > 100 ) return -1;
  if( neededScore < 0 ) return 0;
  return neededScore;
 }
}

得点は237.46/250。正解率は78.45%。必要なスコアの計算が、tests.length+1をかけるということぐらいしか引っかかりそうな場所が思いつきません。素直な実装で解けたと思います。

TopCoder SRM195 Div2 250Pts

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

問題を簡単に和訳する。数値の丸めについて考える。通常は切り上げ、切り捨てと言えば、10の累乗の何倍かに丸めることを指す(554->550=55*10^1とか)。ただ、必ずしも10にする必要はなく、7や3の倍数に丸めても問題はない。そこで、nという整数が与えられたときに、bの倍数に最も近い値に丸めて返すメソッドを作成せよ。

例えば、n=100、b=3であれば、99が返ってくる。これは99(=3*33)と102(3*34)を比較すると、99の方が100に近い値になるからである。

私の解答はこちら。

public class Rounder {
 public int round(int n, int b) {
  int mod = n % b;
  if( mod >= b/2.0 ) return n-mod+b;
  return n-mod;
 }
}

得点は238.11/250。正解率は約80.7%。n%b(nをbで割った余り)がb/2.0以上か、そうでないかで分岐する。b/2以上か否かで分岐させようとすると、2)のテストケースで失敗する。bが偶数なら問題ないが、奇数の時にバグになる。

TopCoder SRM194 Div2 250Pts

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

問題を簡単に和訳する。

サッカーのリーグ戦では、勝つと3、引分けだと1、負けだと0の勝ち点が得られる。勝利数と引分数の配列wins[]、ties[]が与えられたときに、全チームの勝ち点の最大値を返すメソッドを作成せよ。ただし、2つの配列におけるi番目の要素は、チームiの結果を表すものとする。

私の解答はこちら。

public class Soccer {
 public int maxPoints(int[] wins, int[] ties) {
  int maxP = 0;
  for( int i=0 ; i<wins.length ; i++){
   int tmpP = wins[i]*3 + ties[i];
   if( tmpP > maxP ) maxP = tmpP;
  }
  return maxP;
 }
}

得点は248.74/250と過去最高の点数を記録。特にひねる必要もなく、素直に書けた。正解率は99.45%。平均点も高く、易問のようだ。

TopCoder SRM192 Div2 250Pts

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

問題を簡単に和訳する。

機械的に箱に物を詰めることを考える。箱も物も直方体の形をしている。箱に対して、物を最大でいくつ詰めることができるかを返すメソッドを作成する。ただし、以下の点に注意する必要がある。

• 物は箱のすべての辺に対して平行になるよう置かなければならない
• すべての物は同じ向きになっている(空いた隙間に物の向きを変えて詰めるのはダメ)

例えば、100*98*81の箱に3*5*7の物を詰めると、5*7*3に物の向きを変えてつめれば、最大で20*14*27=7560個の物を詰めることができる。

私の解答はこちら。箱に対して、6通りの物の置き方があるということなので、それをfor文で表現する方法を思いつくのに時間がかかった。

public class BoxLoader {
 public int mostItems(int boxX, int boxY, int boxZ, int itemX, int itemY, int itemZ) {
  # 物のある辺が大きすぎる場合(実はこの下の行は不要)
  if( max3(boxX,boxY,boxZ) < max3(itemX,itemY,itemZ) ) return 0;
  int items[] ={itemX,itemY,itemZ};
  int ratio[] = new int [3];
  int inbox = 0;
  for( int i=0 ; i<3 ; i++ ){
   for( int j=0 ; j<3 ; j++ ){
    for( int k=0 ; k<3 ; k++ ){
     if( i!=j && j!=k && k!= i){ # i,j,kに重複がない
      ratio[0] = boxX / items[i]; # 何個分X,Y,Z方向は箱を置けるか
      ratio[1] = boxY / items[j];
      ratio[2] = boxZ / items[k];
      int mul = ratio[0]*ratio[1]*ratio[2]; # 箱を置ける数
      if( inbox < mul ) inbox = mul; # 最大値を更新
     }
    }
   }
  }
  return inbox;
 }
 private int max3(int a,int b,int c){
  int tmp = Math.max(a, b);
  return Math.max(tmp,c);
 }
}

得点は214.97/250。正解率は約84%。全体の傾向を見ていると、正解率は低くないのですが、解答までに時間のかかる比較的難易度の高い問題でした。コードレビューをしますと、最初のmax3は不要ですね。後半のfor文ですべて計算可能ということに提出後に気付きました。あと、最大を求める数学関数は、できれば可変長引数(一度に全部引数を与えられる)にして計算できないかと思います。

TopCoder SRM191 Div2 250Pts

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

問題について軽く説明する。賭け事について考える。

ある賭け事で、賭ける側は予測される結果「0からamounts.length-1までの整数」に対し、それぞれamounts[]ドルを賭ける。最終的な当たりがfinalResultになったとすると、finalResult以外に賭けたお金は運営者の収益になる。一方、当たりに対しては、運営者が1ドルにつきcentePerDollar[]セント払うように設定してある。この賭けが終わった後に、運営者が儲けるのは何セントになるか求めるメソッドを作成せよ。

この問題を読んだときに、トトが真っ先に思い浮かんだ、私の最初の解答はこちら。

public class BettingMoney {
 public int moneyMade(int[] amounts, int[] centsPerDollar, int finalResult) {
  int comp = 0; // 運営の収益
  int people = 0; // 賭けた人が当たりにした額
  for( int i=0 ; i<amounts.length ; i++ ){
   if( i != finalResult ){
    comp += amounts[i];
   }else{
    people += amounts[i];
   }
  }
  return comp*100-people*centsPerDollar[finalResult];
 }
}

得点は226.20/250。正解率は約97%!変数名を運営会社と賭ける人々という意味にしたけど、あまり良い変数名ではないですね。また、peopleは次のように変形すれば不要ということに気付きました。

public class BettingMoney {
 public int moneyMade(int[] amounts, int[] centsPerDollar, int finalResult) {
  int comp = 0;
  for( int i=0 ; i<amounts.length ; i++ ){
   if( i != finalResult ){
    comp += amounts[i];
   }
  return comp*100-amounts[finalResult]*centsPerDollar[finalResult];
 }
}

TopCoder SRM190 Div2 250Pts

英語の速読とJavaのトレーニングも約20回に到達。今日の問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

今日の問題では、バスケットボールの試合における得点効率を求める。得点効率を求める式は、次のように表される。

得点効率 = (合計点数) / (フィールドショット+0.5*フリースロー数 )

フィールドショットは2点、3点のシュートを指す。フリースローは1点のシュートを指す。今、gameLogという、シュートの成功、失敗に関する文字列型の配列が入力されたときに、得点効率を返すメソッドを作成せよ。文字列の内容は、以下のコードを見れば明らかであるが、n点のシュートを成功/失敗という形式になっている。

私の解答は以下の通りである。

public class ScoringEfficiency {
 public double getPointsPerShot(String[] gameLog) {
  int totalPoints = 0;
  int fieldGoalsAttempted = 0;
  int freeThrowsAttempted = 0;
  for( int i=0 ; i<gameLog.length ; i++ ){
   if( gameLog[i].equals("Made 2 point field goal") ){
    totalPoints += 2;
    fieldGoalsAttempted++;
   }else if( gameLog[i].equals("Missed 2 point field goal") ){
    fieldGoalsAttempted++;
   }else if( gameLog[i].equals("Made 3 point field goal") ){
    totalPoints += 3;
    fieldGoalsAttempted++;
   }else if( gameLog[i].equals("Missed 3 point field goal") ){
    fieldGoalsAttempted++;
   }else if( gameLog[i].equals("Made free throw") ){
    totalPoints++;
    freeThrowsAttempted++;
   }else if( gameLog[i].equals("Missed free throw") ){
    freeThrowsAttempted++;
   }
  }
  return (double)(totalPoints/(fieldGoalsAttempted+0.5*freeThrowsAttempted));
 }

}

得点は231.32/250。全体の正解率は約95%。以前の問題で、無理に凝った分岐させない方が分かりやすかったので、愚直にif文を並べて書いてみた。この方がメンテナンスはしやすいと思われる。他の解答を見ると、文字列が特定の文字列を持っているか判定するcontainsというメソッドを利用する方法もあるようだ。

メモを用いたプログラムの高速化

メモを用いることで、プログラムの実行を高速化することができる。メモというのは、その名の通り計算の途中経過を残しておくことである。一般に、プログラム実行時のメモリ消費量と実行スピードはトレードオフの関係にあると言われている。そのことをJavaでメモを利用する場合としない場合のそれぞれに分け、フィボナッチ数列を計算させることで確認した。

フィボナッチ数列は、a(1)=1、a(2)=1、a(n) = a(n-1)+a(n-2) (ただしn>=3)という関係を持った数列である。a(n)を計算する際に、過去に計算したa(n-1)、a(n-2)をメモとして残しておけば、オーバーフローするまでは高速に計算することが可能である。計算のオーダーはO(n)(n番目を計算するのにnに比例するという意味)になる。一方、再帰的に計算しようとすると、O(2^n)になる。これは、a(1)がおよそ2^n回に比例して現れることに由来する。オーダー表記では定数倍は考慮しないため、O(10*n)のような表記はしない。

public class fib_test{
 static int MAX_SIZE = 30; // 数列で何項目まで計算するか
 static int memo[] = new int [MAX_SIZE];

 private static int fib_memo(int n){
  if( n<0 ) return n;
  if( memo[n] != 0 ) return memo[n]; // メモの有無は値が0かそうでないかで判断
  memo[n] = fib_memo(n-1) + fib_memo(n-2);
  return memo[n];
 }

 private static int fib_recursive(int n){ // 再帰による計算
  if( n<=1 ) return 1;
  return fib_recursive(n-1) + fib_recursive(n-2);
 }

 public static void main(String args[]){
  memo[0] = 1;
  memo[1] = 1;

  // メモ利用時
  long start = System.currentTimeMillis();
  for( int i=0 ; i<MAX_SIZE ; i++){
   System.out.println("fib_memo[" + (i+1) + "] = " + fib_memo(i));
  }
  long end = System.currentTimeMillis();
  System.out.println("実行にかかった時間は " + (end - start) + " ミリ秒です。");

  // 再帰利用時
  start = System.currentTimeMillis();
  for( int i=0 ; i<MAX_SIZE ; i++){
   System.out.println("fib_recursive[" + (i+1) + "] = " + fib_recursive(i));
  }
  end = System.currentTimeMillis();
  System.out.println("実行にかかった時間は " + (end - start) + " ミリ秒です。");

 }
}

実行時間を比較すると、私の実行環境(Eclipse3.6、Core2Quad 3GHz、メモリ4GB)でも、明らかに差があった。上のプログラムを実行させてみると、メモを用いた場合は、実行にかかった時間が0ミリ秒となったのに対し、再帰で解いた場合は、実行時間は平均して15ミリ秒となった。

実行時間の計測にはSystem.currentTimeMillis()メソッドを用いた。実行の前後にメソッドを入れて時刻の差分をとり、差分を実行時刻とみなしている。

TopCoder SRM189 Div2 300Pts

引き続き英語の速読とJavaのトレーニング。今日の問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

問題を説明する。切り上げ、切り捨てについての問題である。二つの数値num、cutoffが文字列で与えられる。cutoffについては、0\.[0-9]{4}(正規表現)という形で与えられる。単純に言えば、cutoffは0より大きく1より小さい値で、小数点以下は4桁で表されている。numの小数点以下がcutoff以上であれば小数点以下を切り上げて、そうでなければ小数点以下を切り捨てるメソッドを作成せよ。なお、cutoffが0.5000が通常の四捨五入に相当する。

私の解答はこちら。

public class CutoffRounder {
 public int round(String num, String cutoff) {
  double numD = Double.parseDouble(num);
  double numCO = Double.parseDouble(cutoff);
  double dec = 0.0;
  dec = numD - (int)numD;
  if( dec > numCO ) return (int)(numD+1);
  else return (int)numD;
 }
}

得点は287.40/300。numの小数部分だけを取り出して比較するという方針で回答した。最後に、one-linerの綺麗な回答を見つけたので紹介する。

public class CutoffRounder {
 public int round(String num, String cutoff) {
  return (int)(Double.parseDouble(num)-Double.parseDouble(cutoff)+1);
 }
}

TopCoder SRM188 Div2 250Pts

英語の速読とJavaのトレーニングも習慣になってきたかな?今日の問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

問題を大まかに説明する。入力に3*3の魔方陣が与える（実際の引数としては、要素が9の1次元配列で、魔方陣の左から右、上から下の順でデータを格納している）。魔方陣は縦横斜めで和をとった時に、値が同じになる性質を持つ。いま、魔方陣の1箇所だけ-1が入っている。-1のある場所に本来入るべき値は何かを返すメソッドを作成せよ。ただし、-1以外の値は1から100の正の整数が魔方陣に入っているものとする。

私の解答はこちら。

public class MagicSquare {
 public int missing(int[] square) {
  int rowSum[] = new int[3];
  int negCol = 0;
  int negRow = 0;
  for( int i=0 ; i<3 ; i++ ){
   for( int j=0 ; j<3 ; j++ ){
    rowSum[i] += square[i*3+j];
    if( square[i*3+j]<0 ){
     negRow = i;
     negCol = j;
    }
   }
  }
  int max = Math.max(rowSum[0],rowSum[1]);
  max = Math.max(max,rowSum[2]);
  int exceptNeg = 0;
  for( int j=0 ; j<3 ; j++ ){
   if( j==negCol )continue;
   exceptNeg += square[negRow*3+j];
  }
  return max-exceptNeg;
 }
}

得点は196.97/250。全体の正解率は約90%。他の解答を眺めていると、3行のうち1行だけ値が小さいので、1行目の総和<2行目の総和なら1行目に-1があり、2行目の総和<3行目の総和であれば、2行目に-1、それ以外は3行目に-1が含まれているということになるという性質を利用しているものがあった。返す値は、総和が大きい方-総和が小さい方+1とすればより解答が綺麗になると思われる。私の解答を改良するのであれば、maxに対応して3行の最小値を格納する変数minを用意して、max-(min+1)を返せばよいだろう。つまり、以下のようなコードが良さそうということである。

public class MagicSquare {
 public int missing(int[] square) {
  int rowSum[] = new int[3];
  for( int i=0 ; i<3 ; i++ ){
   for( int j=0 ; j<3 ; j++ ){
    rowSum[i] += square[i*3+j];
   }
  }
  int max = Math.max(rowSum[0],rowSum[1]);
  max = Math.max(max,rowSum[2]);
  int min = Math.min(rowSum[0],rowSum[1]);
  min = Math.min(min,rowSum[2]);
  return max-(min+1);
 }
}

最初の解答と比較して、随分とすっきりとしたコードになった。不明であることを示す値は常に-1であるなどの性質の活用は重要である。

TopCoder SRM187 Div2 300Pts

今日も英語の速読とJavaのトレーニング。問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

問題をおおまかに訳す。オフィスに来る人は効率を上げたいので、できるだけオフィスに近い位置から駐車場に止めようとする。駐車位置に応じてオフィスに近いところから1,2,...とラベルがついている。今、eventsで"人名 出入"という文字列型の配列が入力されたときに、最大で何人が駐車していたか返すメソッドを作成せよ。ただし、初期状態では、駐車場に車は無いものとする。また、ある人が出発の前には必ず事前に駐車場に止める操作が含まれているものとする。 例えば、{"A arrives","B arrives","B departs"}という配列が入力された場合は、AとBが駐車した状態がもっとも駐車場が埋まった状態なので、2という値が返される。

私の解答は以下の通り。問題文中の駐車位置に応じて番号を振るということの意味があまり感じられないですね。

public class OfficeParking {
 public int spacesUsed(String[] events) {
  int maxUsed = 0;
  int currentUsed = 0;
  for( int i=0 ; i<events.length ; i++){
   String tmp[] = events[i].split(" ");
   if( tmp[1].equals("arrives")==true ){
    currentUsed++;
   }else{
    currentUsed--;
   }
   if( maxUsed < currentUsed ){
    maxUsed++;
   }
  }
  return maxUsed;
 }
}

得点は292.32/300と、最高点に近い出来。正解までたどり着いた人は約80%。Javaで文字列を分割する際にはsplitメソッドを用いることを学んだ。また、他の解答から、maxUsed = Math.max(maxUsed,curerntUsed)という更新の方法で書くと、行数が少なくなって見通しが良くなるということに気付いた。スピードも大事だが、可読性も考慮しなければ。

Rのtable関数に関する調査

R言語のtable関数はクロス集計のために用いられる関数である。Excelではピボットテーブルに相当する機能である。呼び出しの形式は以下の通りである。

table(..., exclude = if (useNA == "no") c(NA, NaN), useNA = c("no","ifany", "always"), 
       dnn = list.names(...), deparse.level = 1) 

多くの場合、オプションは気にしなくても良いようである。単純な使い方から順に説明する。

1つのカテゴリ変数をtable関数に与えると、カテゴリごとの集計が行われる。次の例を見て欲しい。

> table(state.region) # アメリカ50州の国勢調査対象地域の分類
# 地域ごとの集計結果が出力される
state.region
    Northeast         South North Central          West 
            9            16            12            13 
> table(rbinom(10,1,0.5)) # 0,1が0.5の割合で現れる2項分布から10個データをランダムに生成
# 0,1になった個数が、それぞれ3、7であったことを示している(ランダムなので結果は毎回異なる)
0 1 
3 7 

2変数を与えるとクロス集計もできる。

# state.x77はアメリカ50州のデータ。平均所得の範囲を確認
> range(state.x77[,"Income"]) 
[1] 3098 6315
# 1000刻みで数値をカテゴリに変換する
> state.income <- cut(state.x77[,2],breaks=seq(from=3000,to=7000,by=1000))
> table(state.income,state.region)
               state.region
state.income    Northeast South North Central West
  (3e+03,4e+03]         2    10             0    1
  (4e+03,5e+03]         5     5            10    9
  (5e+03,6e+03]         2     1             2    2
  (6e+03,7e+03]         0     0             0    1

この表から、南部の収入がやや低い傾向を窺うことができる。余談ではあるが、1人当たりの平均所得が一番高い州(上の表では右下の1のこと)はアラスカであった。資源が豊富で、油田による収益が大きいのがその理由である。

TopCoder SRM186 Div2 250Pts

今日も英語の速読とJavaのトレーニング。問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

問題を大まかに説明する。お題はゴルフについて。パーになる打数の整数型配列と、プレーヤーのスコアシート(triple bogeyやbirdieなどの文字列配列)が与えられたときに、合計打数を返すメソッドを作成せよ。

私の解答は以下の通り。

public class GolfScore {
 public int tally(int[] parValues, String[] scoreSheet) {
  int totalStrokes = 0;
  String pattern[] = {"triple bogey","double bogey","bogey","par","birdie","eagle","albatross"};
  int stroke[] = {3,2,1,0,-1,-2,-3};
  int idx = 0;
  for( int i=0 ; i<parValues.length ; i++){
   if( scoreSheet[i].equals("hole in one") ){
    totalStrokes++;
   }else{
    for( int j=0 ; j<pattern.length ; j++ ){
     if( scoreSheet[i].equals(pattern[j]) == true){
      idx = j;
      break;
     }
    }
    totalStrokes += (parValues[i] + stroke[idx]);
   }
  }
  return totalStrokes;
 }
}

点数は226.47/250でした。以前嵌った文字列比較はequalsメソッドで無事解決。反省会と称して他の人の解答を見ていくと、わざわざホールインワンを特別に扱わなくとも、scoreSheetに登場しうる文字列に応じてif文を8つ書いてしまう方が単純だし、バグも少なくて楽に書けることに気付いた。他にもハッシュを用いた回答がいくつかあった。今後の参考としたい。

同値分割と境界値分析

今日はソフトウェアテストの手法についての基本的な手法についてのまとめ。

次の問題を考える。日本人はその年齢に応じて0-14歳が年少、15-64が生産年齢、65歳-150歳(本当は年齢に上限はないのだが、人間が生きられる年齢の上限として150を設定した)を老年と分けることができる。ある画面で年齢を(正しいフォーマットの整数だけ入力可能な)テキストボックスに入力してOKボタンを押したときに、その区分を表示させるようなプログラムを作成する。このとき、同値分割と境界値分割の考え方を用いて、テストケースを作成せよ。

同値分割という言葉を説明する。同値分割は、値をグループに分けてその中から代表値を選んでテストを行う手法のことである。ありとあらゆるケースを想定してテストすることは不可能(無限にある整数の値を入力することなどできるわけがない)なので、代表値を選ぶのである。

例題のように、処理が年齢に応じて変化する場合、1つ1つの年齢に対しテストを行うのでは面倒である。そこで、年少の代表として7、生産年齢の代表として40、老年の代表として75というように値を取り出してテストを行う。

マイナスの年齢や151歳以上の年齢は処理の対象にならない異常な値である。このような値の範囲は「無効同値クラス」と呼ばれている。一方、0-14、15-64、65-150の範囲の値は「有効同値クラス」という。正常値だけでなく、異常値も代表を出して(-5、160など)エラーが正しく処理されているかテストを行う必要がある。

境界値分析というのは、バグの起きやすい箇所である端の値をテストする手法である。プログラマがイコールを付け忘れるというバグを取り出すことができる。上記の例では、同値分割されたクラスの端の値である-1、0、14、15、64、65、150、151をテストすることになる。もちろん前提として、1歳刻みであるから、今挙げた値が境界値になるということを付け加えておく。単位によって確認するべき境界値が変化するということに注意しなければならない。例えば「普通、デジタル温度計は何度刻みか?」と質問された場合、1度、あるいは0.1度という、人によって異なる答えが返ってくるであろう。これをソフトウェアのテストで考えると、25度と24度か25度と24.9度のどちらで境界値を確認するかというような違いが出てくる。テストの際には仕様の確認や思い込みの排除が重要である。

下の図に書かれている数値は、例に用いた年齢による区分ごとの処理でテストすべき値である。

境界値分析は一つの数直線上の値(変数)をテストする手法であるが、複数の変数が関連している場合は、ドメイン分析と呼ばれる手法でテストを行う。ドメイン分析は境界値分析の多次元版である。例えば、同時にa,b,cという1つ境界値を持つ変数に対してドメイン分析手法に基づくテストを行う場合、以下のテーブル(Binderのドメイン分析テストマトリックス)に従って1から6のテストを行う方法がある。

onは無効同値クラスに接した有効同値クラスの値で、offは有効同値クラスに接した無効同値クラスの値、inはonではない(境界値でなく、バグは出ないだろう箇所と考えられる)有効同値クラスの値である。表には無いが、端の値でない無効同値クラスの値はoutと呼ばれる。

テストマトリックスの例

変数	タイプ	1	2	3	4	5	6
a	on	○
	off		○
	in			○	○	○	○
b	on			○
	off				○
	in	○	○			○	○
c	on					○
	off						○
	in	○	○	○	○
結果

Binderの手法では、1つの変数だけをon、offと変化させて、残りをinとする。一度に1変数だけ変化させるのは、2変数を同時にon/offに設定すると、境界値で両方とも問題があるときに、どこに問題があるか分かりにくくなるためである。

TopCoder SRM185 Div2 250Pts

英語の速読とJavaのトレーニング。今日の問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

問題について大まかに和訳する。進級試験について考える。進級試験に合格するには、全試験の合計点の65%以上の得点率が必要である。最終試験直前までの試験の点数(pointsPossible[])とそれぞれの試験で得た点数(pointsEarned[])（もちろん順番はpointsPossibleに対応している）、および最終試験の合計点(finalExam)が与えられたとする。このとき最終試験で何点得られれば合格になるかを返す関数を作成せよ。ただし、最終試験で最高点を取得しても合格できない場合は-1を返せ。

例えば、pointsEarned={1,2,3,4}、pointsPossible={2,3,4,5}、finalExam=7とする。試験の満点は21点(=2+3+4+5+7)であり、21*0.65=13.65を上回るには最終試験で4点を取ればよいので、4を返すように関数を作成すればよい。私の解答は以下の通りである。

public class PassingGrade {
 public int pointsNeeded(int[] pointsEarned, int[] pointsPossible, int finalExam) {
  int sumEarned = 0,sumPossible=0;
  for( int i=0 ; i<pointsEarned.length ; i++){
   sumEarned += pointsEarned[i];
   sumPossible += pointsPossible[i];
  }
  for( int i=0 ; i<=finalExam ; i++){
   if( (double)(sumEarned+i) / (sumPossible+finalExam)  >= 0.65 ){
    return i;
   }
  }
  return -1;
 }
}

得点は234.93/250と上位15%以内に入る高速解答。高速に解答できた一番の理由として、for文で何点とったら最大得点の0.65を超えるかという判定を書いたことがあるだろう。変に計算しなくて良いので、非常に問題が単純化された。ただし、これは問題設定でfinalExamの上限値が1から3000であり、高々3000回のループで終了するということで、特にスピードを意識しなくてもよいからである。finalExamの最高値が1000000程度になるのであれば、きちんと計算して65%になる点数を計算する必要があるだろう。

TopCoder SRM184 Div2 250Pts

今回の問題はこちら(要TopCoder登録 & 問題文は英語)。

次に問題を説明する。2回異なる距離を走って得られた距離と時刻の組から、3回目に2回の中間に相当する距離を走った場合に、走りきるのにかかる時刻を予測したい。予測の計算式はすでに与えられているので、フォーマットに従ってかかる時刻を出力せよという問題である。私の解答は以下の通り。

public class RaceApproximator {

 public String timeToBeat(int d1, int t1, int d2, int t2, int raceDistance) {
  int takenSeconds = (int)(t1*Math.exp( Math.log((double)t2/t1)*
                     Math.log((double)d1/raceDistance)/Math.log((double)d1/d2)  ));
  int hours = takenSeconds/3600;
  int minutes = (takenSeconds-hours*3600)/60;
  int seconds = takenSeconds-hours*3600-minutes*60;
  return String.format("%d:%02d:%02d", hours,minutes,seconds);
 }

}

得点は132.63/250。C言語のsprintfに相当するのがString.formatであるということを学んだ。低得点に終わった理由はMath.exp()で囲む範囲を間違えてしまったことで、勿体ないことをした。

Rで円周率計算+並列計算

前回の計算の続きということで、snowパッケージを用いて並列処理させることにより、円周率の近似計算を高速化させることを行った。前回の記事は>>こちら<<である。リンク先の記事に一度目を通してから、以下に進んでほしい。

1行に座標が与えられた行列で、原点からの距離を行ごとに計算するということは並列化可能（ある行の結果が他の行の結果に依存しない）と考えられるので、大規模になるにつれて高速化の効果が出るのではないかというのが、並列計算を思いついたきっかけである。データ数を10倍にしながら、円周率の精度と計算にかかった時刻について調べてみた。並列化したコードは以下の通りである。

library(snow)
set.seed(1)
tens <- 10^c(1:6)
# データ数を10倍しながら、かかる時間を調べている
for( points.num in tens ){
 coords <- matrix(runif(2*points.num),ncol=2)
 start <- proc.time()
 cl <- makeSOCKcluster(rep("localhost",4)) # 4は利用するマシンのコア数
 dist.from.origin <- parRapply(cl,coords,function(x){sqrt(sum(x^2))})
 myPI <- sum(dist.from.origin<1)/points.num*4
 diff.time <- proc.time()-start
 print(diff.time)
}
stopCluster(cl)

makeSOCKclusterで、ローカルマシンの4つのコアに計算を割り振ることにした。また、parRapplyという行方向の計算を行うapplyを並列化した関数で各コアに計算を割り振っている。一般的なparApplyよりも効率がよいこともあるという理由で試している。

並列化しない前回のコードでも同様に、距離計算と円周率計算の箇所のみで処理時間を計測した。次の表が比較した結果である。CPUはCore2Quad 3GHzを用いている。2つの表を比較すると、データが少ないうちは並列化しない方が高速で、データが大きくなると、並列化した方が速くなっていることが分かる。データが少ないうちはデータを割り振ることや、割り振ったものが返ってきた結果をまとめることで、かえって時間がかかるため、並列化のメリットは無いようである。

並列化しない場合の実行時間 行数 ユーザ システム 経過 10 0 0 0 100 0 0 0 1000 0 0 0 10000 0.24 0.00 0.23 100000 0.89 0.00 0.89 1000000 10.68 0.02 10.75

並列化した場合の実行時間 行数 ユーザ システム 経過 10 0.01 0.00 5.03 100 0.00 0.00 2.19 1000 0.02 0.03 2.33 10000 0.02 0.02 2.53 100000 0.13 0.08 3.40 1000000 0.94 0.14 6.48

最後に参考文献として、Rパッケージガイドブック(東京図書)を挙げておく。snowパッケージの英語のマニュアルを読むのがつらいという場合には、日本語で書かれた文献として参照されたい。

追記(2011/11/09)
念のためこちらにも。前回の記事(Rで円周率計算)を読んでいればご存知かとは思いますが、上記のコード中のsqrtは不要です。実行時間が変わるので、コードの修正はしませんが、もう少し高速化することはできます。

Rで円周率計算

Rでモンテカルロ法（大量に試行して精度の高い結果を得ようとする方法）によって、円周率を計算することを行った。

set.seed(1)
points.num <- 1000
coords <- matrix(runif(2*points.num),ncol=2)
dist.from.origin <- apply(coords,1,function(x){sqrt(sum(x^2))})
myPI <- sum(dist.from.origin<1)/points.num*4

コードを説明する。set.seed(1)は乱数のシードを固定するためのものである。毎回同じ結果を得るためだけに利用している。points.numはシミュレーションに用いる点の数である。coordsはpoints.num*2の行列であり、1行が1組の(x,y)座標を表している．座標は[0,1]×[0,1]の領域で一様乱数を発生させて得られた点になる。dist.from.originは、原点からの距離を計算した結果である。定義どおりに距離を計算しているが、最終的に原点からの距離が1未満の点の数を求めるだけなので、実はsqrtは不要である。0以上の実数aに対し、a*a<1とsqrt(a*a)<1は同値だからである。myPIが円周率の近似解になる。円周率は原点からの距離が1未満である点の割合を4倍したものになる。4倍するのは、一様乱数を発生させた領域が第1象限のみに限られているからである。

上記のコードを走らせるとmyPIは3.148という値が得られる。実際の円周率3.141592...に近い値が得られていることが確認できる。精度を上げようとしてpoints.numを大きくすると、急激に時間がかかるようになる。そこで、次回はsnowパッケージを用いて、並列処理をさせてみることにしよう。

追記(2011/06/08) 並列処理のコードを実装しました。こちらよりご覧ください。

追記(2011/11/09) 上のコードをいじった高速版のコードを以下に挙げておきます。@a_bickyさんのツイートと、とあるブログからの指摘がありました。applyとrowSumsの速度比較結果についてはまた後日。

set.seed(1)
points.num <- 1000
coords <- matrix(runif(2*points.num),ncol=2)
dist.from.origin <- rowSums(coords^2) # 上で説明した通りsqrtは不要
myPI <- sum(dist.from.origin<1)/points.num*4

追記(2011/12/11)
applyとrowSumsの速度比較を行ってみました。詳細はこちら。

TopCoder SRM183 Div2 350Pts

あー、前回の300点問題よりもまた難しくなってるよ～と思いながら開いた今回の問題。
今回の問題はこちら(要TopCoder登録 & 問題文は英語)。

今回の問題は数を数えるゲームの必勝法について。普通は、自分と相手が1からgoalまで、順にmaxAddまで数えられるという形式であるが、さらに自分がnextの数から数えるということになっている。もし自分がgoalの数を言うことができ、ゲームに勝てるとしたら、自分は最初にnextから数えるとして、いくつの数字を言えばよいか返すメソッドを作成せよというのが問題である。

例えばgoal=20、maxAdd=3、next=10とするのであれば、自分は20を言えば勝ち、16を言えば勝ち、12を言えば勝ちになるので、10、11、12と3つコールすれば勝つことができ、3を返すことになる。もし、どうあがいても勝てない場合は-1を返す。

ゲームに勝つためにここでコールを止めればよいという数字は、goal、goal-(maxAdd+1)、goal-2*(maxAdd+1)、...となっていることに注意。

私の最終的な実装は下のようになった。残念ながら、最初の提出ではシステムテストをクリアできなかった。

public class CountGame {

 public int howMany(int maxAdd, int goal, int next) {
  // これが言えたら勝ちという数字でnext以上の最小値を求める
  while(true){
   if( goal-(maxAdd+1)<next ){
    break;
   }
   goal -= maxAdd+1;
  }
  // 言えたら勝ちという数字は自分がコールできる範囲の値か?
  if( next+maxAdd-1>=goal ) return goal-next+1;
  return -1;
 }

}

システムテストで引っかかったのは、maxAdd=8、goal=1000、next=1のケースだった。間違いの原因はwhile文の中にあるif文で等号をつけていたことである。

得点はシステムテストに一発で通らなかったので、参考までに。再提出でシステムテストをクリアした時点で158.19/350。上のコードに書き直した時点で、105/350である。最初は冗長なコードだったけど、最終的にはスマートになったかな?

TopCoder SRM182 Div2 300Pts

今日もJavaと英語の練習。300点問題ということもあり、いつもの250点問題より難しめかと身構えてみる。

本日の問題はこちら(要TopCoder登録 & 問題文は英語)。

問題を大まかに説明する。
国際バカロレア資格で高校生は卒業時の試験で、1-7の7段階に成績で分けられる。ただ分けられた試験の結果を大学入学の決定には利用できない。そこで先生は試験の結果を予測するということが要求される。学生の将来がかかっているので、学校は精度の評価に非常に興味を持っている。問題としては、getSummaryというメソッドを持つIBEvaluatorを作成する。予測結果predictedGrades[]と実際の結果actualGrades[]があり、各インデックスが一人に対する値を表している。2つの配列が与えられたとき、メソッドは7つの要素を持つ配列を返す。内容は、0-6の誤差が何%現れたかというパーセンテージが入ったものである。返す配列の型は整数値で、パーセンテージの値は小数点以下を切り捨てたものとする。したがって、返す配列のインデックス0の値の中身は予測と実際の値が一致した割合を示している。インデックス1は、予測と実際の誤差の絶対値が1であることを示している。

import java.math.*;

public class IBEvaluator {

 public int[] getSummary(int[] predictedGrades, int[] actualGrades) {
  int array[] = new int[7];
  for( int i=0 ; i<predictedGrades.length ; i++ ){
   int diff = Math.abs(predictedGrades[i]-actualGrades[i]);
   array[diff]++;
  }
  double percentEachPerson = 100.0/predictedGrades.length;
  for( int i=0 ; i<7 ; i++ ){
   array[i] = (int)(array[i]*percentEachPerson);
  }
  return array;
 }

}

点数は264.09/300、結局思ったよりもずっと簡単で、拍子抜け。スピードとしては2部リーグのほぼ中程度。ポカしてなければもっと速く実装できたが、勿体ない。