TopCoder SRM296 Div2 250Pts

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

N1={1,2,...,1000}という配列が与えられる。ここから2の倍数番目に現れるものを取り除いた{1,3,5,...,999}をN2とする。さらにN2から3の倍数番目に現れる要素を取り除いた{1,3,7,9,13,...}をN3とする。このような操作を繰り返すとN10というものが生成できるが、このN10のn番目の要素の値を返せ。なお、N10の要素数は101になる。

私の解答はこちら。

import java.util.TreeSet;

public class EratosthenSieve2 {

 public int nthElement(int n) {
  TreeSet<Integer> work = new TreeSet();
  Integer[] res = null;
  for( int i=1 ; i<=1000; i++ ){
   work.add(i);
  }
  for( int i=2 ; i<=10 ; i++ ){
   res = (Integer[])work.toArray(new Integer[0]);
   work.removeAll(work);
   for( int j=0 ; j<res.length ; j++ ){
    if( (j+1)%i != 0 ) work.add(res[j]);
   }
  }
  res = (Integer[])work.toArray(new Integer[0]);
  return res[n-1];
 }

}

得点は128.10/250、中央値は約163点。return直前のresへの代入が抜けていて嵌ること約10分...

TopCoder SRM263 Div2 250Pts

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

あなたは、全員が互いの名前を知らないパーティーに出席している。二人が握手するたびに、二人は互いを紹介試合、パーティでこれまでに知った人たちの名前を共有し合う。nというパーティの出席者数と、personA[]、personB[]という人々を表す数字が0から始まる配列が与えられる。この配列は誰が握手しあったのかということを時系列的に表している(つまり先頭から後方に向かって後のことを表すようになっている)。personAとpersonBの添え字が同じものが1つの握手を表している。パーティで知った人数の平均値を返せ。ただし、自分の名前はそれに含めないものとする。また、personA[i]とpersonB[i]は0からn-1の値を取り、かつ1つの添え字に着目したとき、同じ値は入らない。

私の解答はこちら。

public class Party {

 public double averageNames(int n, int[] personA, int[] personB) {
  // i行j列の要素はiという人がjという人を知っているか否かを表す
  boolean[][] known = new boolean[n][n]; // falseで初期化される。falseは知らないを意味する。
  for( int i=0 ; i<personA.length ; i++ ){
   int A = personA[i];
   int B = personB[i];
   known[A][B] = true; // 互いを紹介
   known[B][A] = true;
   for( int j=0 ; j<n ; j++ ){ // これまでに知った人を互いに共有
    // known[B][B]は常にfalseなのでj!=Bが必要
    if( known[A][j] && j!=B ){ // AがBに教える
     known[B][j] = true;
    }
    if( known[B][j] && j!=A ){ // BがAに教える
     known[A][j] = true;
    }
   }
  }
  int cnt = 0; // 知っている人数を合計
  for( int i=0 ; i<n ; i++ ){
   for( int j=0 ; j<n ; j++ ){
    if( known[i][j] ) cnt++;
   }
  }
  return (double)cnt/n; // 知っている人数の平均はnで割って求まる
 }

}

得点は75/250。相手を知っているというデータ構造を考え付くのに、2次元配列という発想が出なかったため、何週間か考えて解答。

TopCoder SRM295 Div2 300Pts

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

とてもわくわくするジャンケントーナメントが始まりました!予選では、各プレーヤはすべての相手と向かい合って5回手を出します。各勝負では、プレーヤはグー(P)、チョキ(S)、パー(S)の中から1つ選びます。1回の勝負は次のように決まります。パーはグーに勝ち、グーはチョキに勝ち、チョキはパーに勝つ。もし二人が同じ手を出したなら、どちらの勝ちにもなりません。ゲームの勝者は5回の勝負でより勝った方になります。もし、二人が同じ勝ち数であったら、ゲームは同点と扱われます（予選なので、同点も許されます）。予選を抜ける人を決めるため、得点システムを次のようにします。このゲームに勝つと、1点、同点なら0.5点、負けなら0点とします。もっとも点数を得た1人だけが予選を抜けます。もし複数のプレーヤが同じ点数で並んだ場合は、入力で一番最初に現れた人が勝つものとします。

すべてのプレーヤは単純な戦略に従います。それは全員が出す手の順番を用意しておき、すべてのゲームで同じ手をその順で出すというものです。players[]というか各プレーヤーの出す手を表す配列が与えられたときに、予選を抜けたプレーヤの添え字を返せ（先頭のプレーヤの添え字は0から始まるものとする）。プレーヤの各要素は5文字であり、Pはグー、Sはチョキ、Rはグーを表すものとする。

私の解答はこちら。

public class PaperRockScisQuals {

 public int whoPassed(String[] players) {
  // 問題文では勝負の結果で1、0.5、0点与えるとあるが、2倍しても答は変わらないので、
  // 2、1、0という点数を与えるようにしておく。こうすると整数値で扱える。
  int[] points = new int[players.length];
  for( int i=0 ; i<players.length ; i++ ){
   for( int j=i+1 ; j<players.length ; j++ ){
    String iHands = players[i];
    String jHands = players[j];
    int iWin = 0;
    int jWin = 0;
    for( int k=0 ; k<players[i].length() ; k++ ){
     int res = judge(iHands.charAt(k), jHands.charAt(k));
     if( res > 0 ){
      iWin++;
     }else if( res < 0 ){
      jWin++;
     }
    }
    if( iWin > jWin ){ // iとjに点数を与える
     points[i] += 2;
    }else if( iWin == jWin ){
     points[i]++;
     points[j]++;
    }else{
     points[j] += 2;
    }
   }
  }
  int idx = -1;
  int max = -1;
  for( int i=0 ; i<points.length ; i++ ){ // 最高点判定ロジック
   if( points[i] > max ){
    max = points[i];
    idx = i;
   }
  }
  return idx;
 }
 private int judge(char i,char j){ // ジャンケンの勝負判定ロジック
  if( i == j ){ // 同じ手
   return 0;
  }else if( (i == 'P' && j == 'R') || (i == 'S' && j == 'P') || (i == 'R' && j == 'S') ){
   return 1; // iの勝ち
  }else{
   return -1; // jの勝ち
  }
 }
}

得点は165.76/300、中央値は約185点。当初は最初から見て最初に勝った方が勝者という判定ロジックを書いていたため、5回のジャンケンの結果で判定を行わないといけないということに気付かず、解答が遅くなってしまった。また、日本語と英語でジャンケンの手の名称が異なるため、しっくりこない感もあるが、PはPaper（紙）、SはScissors（ハサミ）、RはRock（岩）という英単語の略である。

TopCoder SRM294 Div2 250Pts

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

あなたは正当な提案と思われることをしてきた立派な男性に偶然にも出会った。スリーカードモンテをしようというのである。男性はまず、テーブルにカードをジョーカー、エース、ジョーカーの順にテーブルに並べる。あなたがちょっとだけお金をかけた後に、男性は2枚のカードの位置を交換する操作を始める。交換が終わったら、あなたはどこにエースがあるかを推測する。カードの位置交換はswapsという文字列で与えられる。文字の中身はL、R、E、Fの4文字からなる。swaps[0]が最初の男性のカードの位置交換を表す。4文字の意味はそれぞれ次の通りである。

• L：左と真ん中のカードを交換
• R：右と真ん中のカードを交換
• E：左と右のカードを交換
• F：だましの交換（実際にはカードは入れ替わらない）

全ての交換が終わった後に、エースの位置を返すメソッドを作成せよ。メソッドの返り値は、エースが左にあるなら"L"、右にあるなら"R"、真ん中にあれば"M"を返すようにせよ。

私の解答はこちら。

public class ThreeCardMonte {

 public String position(String swaps) {
  String[] cPos = {"J", "A", "J"}; // Jがジョーカー、Aがエースを表す
  // 前半のfor文でスワップが終わる。後半のfor文で返す文字を探索する。
  for( int i=0 ; i&;t;swaps.length() ; i++ ){
   char c = swaps.charAt(i);
   if( c == 'L'){ // 各文字ごとの処理、Fの処理は不要
    String tmp = cPos[0];
    cPos[0] = cPos[1];
    cPos[1] = tmp;
   }else if( c == 'R' ){
    String tmp = cPos[1];
    cPos[1] = cPos[2];
    cPos[2] = tmp;
   }else if( c == 'E' ){
    String tmp = cPos[2];
    cPos[2] = cPos[0];
    cPos[0] = tmp;
   }
  }
  String[] ret = {"L", "M", "R"}; // どこにAがあるかを示す文字
  for( int i=0 ; i<cPos.length ; i++ ){
   if( cPos[i].equals("A") ) return ret[i];
  }
  return null; // C言語と違って必ず返す値があるように見せかけないといけない。
 }
}

得点は226.69/250、中央値は約217点。スワップはメソッド化してもよかったかもしれません。作成するとするのであれば、交換する位置2つ（整数値）とcPosを引数に取るようなメソッドになるでしょうか。

TopCoder SRM293 Div2 250Pts

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

あなたは水槽を持っている。fishSizes[]という、水槽の中にいる魚のサイズが与えられる。これまではうまくやってきた魚たちだが、あたなはここにBobという新しい魚を加えたいと思っている。魚たちは互いに食べてしまうということがある。魚たちは2倍以上10倍以下のサイズの魚がいるとそれを食べてしまうと見積もっている。このことを考慮して、Bobは次のようなサイズのものがよいと思っている。

• Bobは食べられる心配がない(他の魚と比べてBobは1/10から1/2のサイズにならない)
• Bobはほかの魚を食べる心配がない(他の魚がBobの1/10から1/2のサイズにならない)

あなたへの課題は、minSize以上maxSize以下のBobのサイズ(整数値)が与えられたときに、上のような互いに食べあう"衝突"が発生しないBobのサイズの数を返すことである。

私の解答はこちら。

public class Aquarium {

 public int peaceful(int minSize, int maxSize, int[] fishSizes) {
  boolean[] isDangerous = new boolean[maxSize-minSize+1];
  for( int i=minSize ; i<=maxSize ; i++ ){
   int idx = i - minSize;
   for( int j=0 ; j<fishSizes.length ; j++ ){
    if( i >= fishSizes[j]*2 && i<= fishSizes[j]*10 ){
     isDangerous[idx] = true;
     break;
    }
    if( fishSizes[j] >= i*2 && fishSizes[j] <= i*10 ){
     isDangerous[idx] = true;
     break;
    }
   }
  }
  int nPeace = 0; // 上のループで一度にカウントできますね。
  for( int i=0 ; i&l;isDangerous.length ; i++ ){
   if( isDangerous[i] == false) nPeace++;
  }
  return nPeace;
 }

}

得点は226.19/259、中央値は約209点。後半のnPeaceをカウントするfor文は、前半に組み込んで回答することもできる。

TopCoder SRM292 Div2 250Pts

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

高速道路が東西に延々と続いている。小心者のボブは直線に歩く。ボブの歩いたパスが与えられたとき、彼が何回道を渡ったかということが知りたい。ただし、彼が道でぶらぶらしていて、途中で元来た道を行った場合は、渡った回数として数えない。道は大したことのない幅なので、あるy座標を固定した水平線のように考えてよい。roadYという道の座標値とbobX[]、bobY[]というボブの通ったパスが引数として与えられるので、ボブが道を渡りきった回数を返すメソッドcrossingを作成せよ。bobX[]とbobY[]のi番目の要素がボブの通ったパスの座標になる。ボブは最初の位置から動きだし、次の点へ直線に動き、最後の点までそれを繰り返す。ボブは道の上で動き出したり、止まったりはしない。

例えば、roadY=6、bobX[]={3,7,9,2}、bobY[]={-3,8,8,2}とすると、2が答えになる。(3,-3)->(7,8)で6をまたぐので1回、(9,8)->(2,2)で6をまたぐので2回というカウントを行う。

私の解答はこちら。

public class FowlRoad {

 public int crossings(int roadY, int[] bobX, int[] bobY) {
  boolean isBobSouth = bobY[0]>roadY ? false : true; // ボブは南側にいるか?
  int nCross = 0;
  for( int i=1 ; i<bobY.length ; i++ ){
   if( bobY[i-1] >= roadY && bobY[i]<roadY && isBobSouth == false ){
    nCross++;
    isBobSouth = true;
   }else if( bobY[i-1] <= roadY && bobY[i]>roadY && isBobSouth == true ){
    nCross++;
    isBobSouth = false;
   }
  }
  return nCross;
 }

}

得点は218.14/250、中央値は約198点。提出後に気付いたのですが、if文に含まれている直前のi-1の情報はisBobSouthで管理しているので不要のはず。また、bobX[]というのは全く利用しないで回答ができる。気を付けるのは、渡りきったということを表現する方法でしょう。ちょうど道の上に乗って、そこから折り返すか進むかでカウントするしないが決まるので、その処理を誤らないことが肝心。

TopCoder SRM291 Div2 250Pts

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

素数というのは、1よち大きい整数で、1とそれ以外で割り切れないものである。もしあるNに対してN-10からN+10にある数で割り切れない場合、その数Nは「素数から遠い」と考えられる。つまりN-10からN+10までの数はすべて素数でないということである。さて、AとBという二つの整数が与えられる。このとき、AとBの間にある「素数から遠い」数はいくつあるかを求めて返せ。なお、常にB>=Aの関係が成り立つものとする。

私の解答はこちら。

public class FarFromPrimes {

 public int count(int A, int B) {
  int nFarFromPrime = 0;
  for( int i=A ; i<=B ; i++ ){
   boolean isFarFromPrime = true;
   for( int j=i-10 ; j<=i+10 ; j++ ){
    boolean isOK = false;
    for( int k=2 ; k<=j/2 ; k++ ){
     if( j % k == 0 ){ // 途中で素数でないと分かればOK
      isOK = true;
      break;
     }
    }
    if( isOK == false ){ // 素数でない数がi-10からi+10の間に存在した
     isFarFromPrime = false;
     break;
    }
   }
   if( isFarFromPrime == true ) nFarFromPrime++; // 全部素数ならカウント
  }
  return nFarFromPrime;
 }

}

得点は183.67/250、中央値は約190点。ある数nが素数か否かの検討は本来ならsqrt(n)まで調べればよいはずなのですが、面倒なので、n/2まで調べる方針で対応しました。

TopCoder SRM290 Div2 250Pts

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

ジョニーは偉大なプログラマになりたいので、いつもプログラミングスキルを改良しようと練習している。ジョニーはより速くタイピングができるようになれば、時間が節約できると思っている。速いタイピングの鍵はリズムを保つ、すなわち一定の時間間隔でキーをたたくということであると言われている。ジョニーのような多くのプログラマーは統計が大好きなので、タイピングプロセスを測るプログラムを書いた。プログラムはlettersというタイピングした文字列と、times[]という整数型の配列で、何ミリ秒でキーを押したかという情報を受け取る。times[]のi番目の要素は、lettersのi番目の要素のキーをたたいた時間である。どのキーも1度しか叩かれておらず、timesの内容は練習セッションを始めてからの時間になる。この問題を特に当たり、1つのキーを叩くのにかかる時間は整数であると仮定する。あなたへの課題はジョニーがタイピングするのに平均時間以上かかった文字を求めることである。これにより、ジョニーはそれらの文字のタイピングをより練習することができる。タイピングで平均以上タイプにかかった文字を入力のlettersの順序ですべて出力せよ。

私の解答はこちら。

public class SpeedTyper {

 public String lettersToPractice(String letters, int[] times) {
  int ave = average(times); 
  StringBuffer sb = new StringBuffer();
  int[] t = takenTimes(times);
  for( int i=0 ; i<t.length; i++ ){
   if( t[i] > ave ) sb.append(letters.charAt(i)); // 平均以上なら文字列の後ろに追加
  }
  return sb.toString();
 }
 private int average(int[] t){ // 配列の平均値を計算して返す
  int total = t[0];
  int len = t.length;
  for( int i=1 ; i<len ; i++ ){
   int tmp = t[i] - t[i-1];
   total += tmp;
  }
  return total/len;
 }
 private int[] takenTimes(int[] t){ // 配列の隣り合う要素の差分をとった結果を返す
  int len = t.length;
  int[] ret = new int[len];
  ret[0] = t[0];
  for( int i=1 ; i<len ; i++ ){
   ret[i] = t[i] - t[i-1];
  }
  return ret;
 }
}

得点は226.34/250、中央値は約219点。実は平均を求めるメソッドが無駄ということに気付いて愕然としました。ave=times[letters.length-1]/times.length;でOKだったのですね。

TopCoder SRM289 Div2 300Pts

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

ある物体がxy-座標系の(x,y)(ただしx>0かつy>0)という座標にある。物体はまっすぐx軸方向に1秒当たり1の速さで落ちていく。それ以外にも、物体は障害物に当たる可能性がある。各障害物はx軸方向に水平な線領域である（つまりy軸方向の厚さは0と考える)。物体が障害物に当たる度に、地面への落下は5秒遅れる。この遅れの間に物体は障害物の右端へ向かい、その位置から垂直に再び落ちる。

初期状態の位置を表す(x,y)と、障害物の位置を表す文字列型の配列obstacles[]が与えられたとき、最終的にx軸に届くまでに何秒かかったかを返すメソッドを作成せよ。obstacles[]の各要素は"y x1 x2"という形式で与えられ、yは障害物のy座標の値、x1とx2はそれぞれ障害物の左端と右端を表している。なお、y、x1、x2は3桁の整数で、桁数が2桁以下であれば先頭に0が埋められている。また、障害物のy座標に重複はないものとする。

私の解答はこちら。

import java.util.Arrays;

public class ObjectFall {

 public int howLong(int x, int y, String[] obstacles) {
  Arrays.sort(obstacles);
  // かかった時間。yの値で初期化すれば、物体に当たった回数のみ考えればよい。
  int nTime = y; 
  int cy = y; // cx、cyは現在の物体の位置を表す。
  int cx = x;
  // y座標の大きい方から検討
  for( int i=obstacles.length-1 ; i>=0 ; i-- ){
   String[] coords = obstacles[i].split(" ");
   int yPos = Integer.parseInt(coords[0]); // 先頭に0があってもこれでOK
   int xl = Integer.parseInt(coords[1]);
   int xr = Integer.parseInt(coords[2]);
   // 衝突の条件はx座標が間に収まることと、y座標が現在の位置以下にあること。
   if( cy >= yPos && cx >= xl && cx <= xr ){
    nTime += 5;
    cy = yPos;
    cx = xr;
   }
  }
  return nTime;
 }

}

得点は184.29/250、中央値よりは下の点数。最初にy座標でソートして、y座標の値が大きい障害物から順番に検討していけばよいということに気付いたものの、ソート(Arrays.sort(obstabcles))の実現方法の思いつきに時間がかかってしまいました。

TopCoder SRM288 Div2 250Pts

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

TopBankという金融機関で働いており、初期口座収支と1日の取引一覧にそって、その日の最後の収支を返すというモジュールを書く仕事を割り当てられた。各取引は口座に入金するcreditと、口座からお金を引き出すdebitのどちらかからなる。もしdebitがある時間に利用できるお金を超えていたら、収支バランスはマイナスになる。初期の口座のバランスを表すstartingBalanceとtransactions[]という1日の取引履歴が与えられる。取引を表す文字列は"type amount"という形式であらわされる。creditは"C"、debitは"D"という文字でtypeを表す。取引高は1から100000の整数値であり。0は数値の先頭にはつかない。作成するメソッドが返すものはすべての取引を処理した後のバランスとなる整数値である。

例えばstartingBalence=100で、transactions[]={"C 10","D 5","D 20"}とすると、返す値は100+10-5-20=85となる。

私の解答はこちら。

public class AccountBalance {

 public int processTransactions(int startingBalance, String[] transactions) {
  int ret = startingBalance;
  for( int i=0 ; i<transactions.length ; i++ ){
   String[] tr = transactions[i].split(" ");
   int money = Integer.parseInt(tr[1]);
   if( tr[0].equals("C") ){
    ret += money;
   }else{
    ret -= money;
   }
  }
  return ret;
 }

}

得点は246.92/250、中央値は約238点。1発で通しました。

TopCoder SRM278 Div2 300Pts

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

グループに分けられた長方形のリストを持っている。グループのインデックスはグループ内のすべての長方形の面積の総和である。もっとも大きいインデックスになるグループを求めようとしている。rectangles[]という文字列型の配列が与えられる。各要素は1つの長方形を表しており、そのフォーマットは"G L W"で表される。Gは長方形が属するグループ、Lは長方形の高さ、Wは長方形の幅を表している。作成するメソッドが返す文字列のフォーマットは"G I"である。Gは最大のインデックスになるグループの名前、Iはそのグループのインデックスである(先頭に0はつかない)。もし最大のインデックスになるものが複数あった場合、アルファベット順で一番最初に来るものを返すようにせよ。グループを表す文字は正規表現で言うところの[A-Z]である。

私の解答はこちら。

import java.util.Set;
import java.util.TreeMap;

public class RectangleGroups {

 public String maximalIndexed(String[] rectangles) {
  String[] work;
  // キー値をアルファベット順にしておくためにTreeMapを利用する。
  TreeMap<String, Integer> tm = new TreeMap<String, Integer>();
  for( int i=0 ; i<rectangles.length ; i++ ){
   work = rectangles[i].split(" ");
   // 面積sは必ず利用するので先に計算しておく。
   int s = Integer.parseInt(work[1])*Integer.parseInt(work[2]);
   if( tm.containsKey(work[0]) == false ){
    tm.put(work[0], s);
   }else{
    Integer v = (Integer)tm.get(work[0]);
    tm.remove(work[0]);// 本当はリムーブは不要で
    tm.put(work[0], v+s); // これで上書きすればよい。
   }
  }
  Set<String> it = tm.keySet();
  String[] keys = (String[]) it.toArray(new String[0]);
  int max = 0;
  String ret = "";
  // 先頭から順にみて、面積最大を更新するグループを求める
  // ここでTreeMapを利用したことが活きる
  for( int i=0 ; i<keys.length; i++ ){
   if( tm.get(keys[i]) > max ){
    max = tm.get(keys[i]);
    ret = keys[i] + " " + max;
   }
  }
  return ret;
 }

}

得点は90.0/300、中央値は約239点。敗因はSetを配列に変換する方法(toArrayメソッドでnew String[0]を引数に取ること)を知らなかったことです。何日か前に同じようなパターンでtoArrayメソッドにはまっていたのを解消したついでに解きました。

TopCoder SRM287 Div2 250Pts

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

文字列型のcustomerNames[]という、データベースから抽出された顧客のリストが与えられる。あなたのやることは1度よりも多くリストに現れた人と、その現れた回数を報告することである。レポートは文字列型の配列で返す。配列の各要素は"NAME OCCURS"という形式で返す。NAMEは顧客の名前で、OCCURSは顧客がリスト中に登場した回数である。出力は顧客の名前でアルファベット順にするようにせよ。なお、顧客名は常に大文字のみからなる。

私の解答はこちら。

import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeMap;

public class CustomerStatistics {

 public String[] reportDuplicates(String[] customerNames) {
  // 顧客の名前でソートしたいのでHashMapを利用する
  TreeMap<String,Integer> tm = new TreeMap();
  for( int i=0 ; i<customerNames.length ; i++ ){
   if( tm.containsKey(customerNames[i]) == false ){ // 初登場の名前
    tm.put(customerNames[i], 1);
   }else{
    int n = tm.get(customerNames[i]); // 登場回数を記録し、
    tm.remove(customerNames[i]); // 情報を取り除き、
    tm.put(customerNames[i], n+1); // 1つ加えてハッシュに入れる
   }
  }
  // イテレータは順序があれば、その順序は保証することになっている
  // ただのMapなどでは順序が保証されない。
  Iterator<String> it = tm.keySet().iterator(); 
  ArrayList<String> aList = new ArrayList();
  while( it.hasNext() ){
   String s = it.next();
   int val = tm.get(s);
   if( val >= 2 ){
    aList.add(s + " " + val); // 条件に合うものだけ取り出しリストに入れる
   }
  }
  // リストを配列に変換する。引数のnew String[0]がポイント。
  String[] ret = (String[])aList.toArray(new String[0]);
  return ret;
 }

}

得点は169.21/250、中央値は約213点。Listを配列に変換する方法が分からなくて苦労していた。toArrayメソッドはしっていただが、new String[0]を引数に取らなかったために、ClassCastExceptionが発生して解くのに時間がかかってしまった。

TopCoder SRM286 Div2 250Pts

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

うっかりものがフェンスを作るためにいくつもの種類の棒を地中に埋めてしまった。同じ長さにするべきなのだが、違う長さに切られてしまったのである。そこでオーナーは同じ長さにするだけでなく、できるだけ棒を長くしたいと思っている。やることは最も長い棒を切って、もっとも短いものにくっつけるということである。このために、まず棒を短い方から順に並び替えて以下のことを行う。

• もっとも長い棒を棒の平均の長さになるように1回だけ切る
• 切ったものをもっとも短い棒の上にくっつける
• 棒を長さで再度ソートして、最初のステップに戻って、すべての棒の長さが同じになるまで繰り返す。

棒の長さを表すpole[]という整数型の配列が与えられたときに、すべての棒の長さが同じになるまで何回上記アルゴリズムが実行されるかを求めて返すメソッドを作成せよ。なお、poles[]の平均値は必ず整数になるものとする。

私の解答はこちら。

import java.util.Arrays;

public class CuttingPoles {

 public int countCuts(int[] poles) {
  int nProcedure = 0;
  while( true ){
   Arrays.sort(poles);
   if( poles[0] == poles[poles.length-1]) break; // 終了条件は最小と最大が同じになったとき
   int ave = average(poles);
   int diff = poles[poles.length-1]-ave; // 継ぎ接ぎする棒の長さ
   poles[0] += diff; // 棒を接ぐ
   poles[poles.length-1] -= diff; // 棒を短くする
   nProcedure++;
  }
  return nProcedure;
 }
 private int average(int[] array){ // 配列の平均を求めるメソッド
  int sum = 0;
  for( int i=0 ; i<array.length ; i++ ){
   sum += array[i];
  }
  return sum/array.length;
 }
}

得点は240.86/250、中央値は約208点。上のコードは汚いので改良するとこんな感じ。

import java.util.Arrays;

public class CuttingPoles {

 public int countCuts(int[] poles) {
  int nProcedure = 0;
  int nPoles = poles.length; // 繰り返し利用する値は定数扱いする
  int ave = average(poles);
  while( true ){
   Arrays.sort(poles);
   if( poles[0] == poles[nPoles-1]) break;
   int diff = poles[nPoles-1]-ave;
   poles[0] += diff; 
   poles[nPoles-1] -= diff;
   nProcedure++;
  }
  return nProcedure;
 }
 private int average(int[] array){
  int sum = 0;
  for( int i=0 ; i<array.length ; i++ ){
   sum += array[i];
  }
  return sum/array.length;
 }
}

lengthメソッドも繰り返し利用することで遅くなるので、その辺を中心に改良してみました。

TopCoder SRM285 Div2 250Pts

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

リンゴが入ったカゴを持っている。以下の手続きによって残っているリンゴの数を最大化したい。まず、いくつかのカゴを捨てる。そして、残ったカゴのリンゴの数が同じでなかったら、余分なリンゴをカゴから取り除く。

apples[]というi番目の要素がi番目のカゴの中にあるリンゴの数を表す整数型の配列があったときに、上記の手続きを実行して最大化されたリンゴの数がいくつになるかを求めて返すメソッドを作成せよ。

例えば{1, 2, 3, 4}という配列が与えられたら、6が答になる。リンゴを一切取り除かないと1*4=4、1だけを除くと2*3=6、1と2だけを除くと3*2=6、1と2と3を除くと4となるからである。

私の解答はこちら。

import java.util.Arrays;

public class BasketsWithApples {

 public int removeExcess(int[] apples) {
  Arrays.sort(apples); // ソートしておく
  int max = 0;
  if( apples.length == 1) return apples[0];
  for( int i=0 ; i<apples.length-1 ; i++ ){
   int sum = apples[i]*(apples.length-i);
   int comp = apples[i+1]*(apples.length-i-1); // 不要
   max = Math.max(max, sum);
   max = Math.max(max, comp); // 不要
  }
  return max;
 }

}

得点は124.67/250、中央値は227点。iをapples.length-1までループするようにすれば、実はcompに関連する2行は不要というオチに気付きました。道理で平均点が高くなるわけです。

TopCoder SRM275 Div2 500Pts

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

Haarウェーブレット変換というのは、1909年にHarrによって導入された最初のウェーブレット変換である。1次元の変換は整数列を次のように変換する。最初に数列を近接した値のペアに分ける。最初は先頭と2番目、次に3番目と4番目という具合である。次に、これらのペアの輪を計算し、新しい数列をつくる。そして、こんどはペアの差を計算(先の値-後の値)し、新しく作成した数列の後ろに追加する。数列の結果はlevel-1変換という。この変換では入力として要素数が偶数であることが要求される。level-2変換は、level-1変換で作成した数列の前半分に対して同様のことを行うものである。つまり後ろ半分は何も変化しない。これらの操作は要素数が2の累乗であればいつでも可能である。data[]という整数列とLという値が与えられたとき、level-LのHaar変換の結果を返すメソッドを作成せよ。

例えば、{1, 2, 3, 4}という数列に対してlevel-1変換は{3, 7, -1, -1}となる。1+2=3、3+4=7、1-2=-1、3-4=-1だからである。level-2変換は{10, -4, -1, -1}である。3+7=10、3-7=-4だからである。後半の-1、-1は変化しない。

私の解答はこちら。

public class Haar1D {

 public int[] transform(int[] data, int L) {
  int[] ret = new int[data.length];
  int[] tmp = new int[data.length];
  for( int i=0 ; i<data.length ; i++ ){
   ret[i] = tmp[i] = data[i];
  }
  for( int i=0 ; i<L ; i++ ){
   int n = data.length/(int)Math.pow(2,i+1); // level-iで変換対象となる要素数の半分
   for( int j=0 ; j<n ; j++ ){
    ret[j] = tmp[2*j]+tmp[2*j+1]; // 前半
   }
   for( int j=0 ; j<n ; j++ ){
    ret[j+n] = tmp[2*j]-tmp[2*j+1]; // 後半
   }
   for( int j=0 ; j<data.length ; j++ ){
    tmp[j] = ret[j]; // 更新
   }
  }
  return ret;
 }

}

得点は322.87/500。要素の破壊を伴うため、2つの配列を用意して解答している。level2の問題にしては簡単かと思います。

TopCoder SRM284 Div2 250Pts

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

山積みされた荷物を倉庫からトラックに載せたいと思っている。計画では荷物は2つの荷物に分けるということをトラックに載せられる量になるまで繰り返す(もちろん奇数の荷物を半分に分けるというのは、片方が他方より1つだけ荷物が多い状態にすることである)。問題は荷物を載せるのにトラックがいくつ必要になるかということである。numCreatesという荷物の数と、loadSizeというトラックに積み込める荷物の最大個数が与えられたときに、必要となるトラックの数を返すメソッドを作成せよ。

私の解答はこちら。

public class Truckloads {

 public int numTrucks(int numCrates, int loadSize) {
  if( numCrates <= loadSize ) return 1;
  if( numCrates % 2 == 0 ){
   return 2* numTrucks(numCrates/2, loadSize);
  }else{
   return numTrucks(numCrates/2, loadSize) + numTrucks(numCrates/2 + 1 , loadSize);
  }
  // ああそうか的な解答(こちらではif文の分岐が不要になる)
  // return numTrucks(numCrates/2, loadSize) + numTrucks(numCrates/2+ numCrates%2, loadSize);
 }

}

得点は244.77、中央値は約222点。1つ撃墜したので+50点にはなりますが。あまり使う機会はないですが、全員同じように再帰で書くので、再帰も全員必須の共通技術になっているのだなと思いました。

TopCoder SRM283 Div2 250Pts

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

正方行列の不釣り合いの度合いを計算しようとしている。正方行列の不釣り合いとは、主対角成分の和から補対角成分の和を引き算したものである。補対角成分はn*nの行列において、(1,n)、(2,n-1)、...、(n,1)の成分を指す。文字列型配列matrix[]が与えられたときに、対角成分の不釣り合いを計算して返せ。matrix[i]番目のj番目の文字が(i,j)成分を表すものとする(つまり、数値は0-9という1桁の数になる)。

私の解答はこちら。

public class DiagonalDisproportion {

 public int getDisproportion(String[] matrix) {
  int main = 0;
  int collateral = 0;
  int len = matrix.length;
  for( int i=0 ; i<len ; i++ ){
   main += matrix[i].charAt(i)-'0'; // 主対角成分の総和を計算
   collateral += matrix[i].charAt(len-1-i)-'0'; // 補対角成分の総和を計算
  }
  return main-collateral;
 }

}

得点は243.79/250、中央値は約239点。

TopCoder SRM282 Div2 250Pts

このTopCoderの問題はリンクが無いので原文は省略。問題文について、おおまかに説明する。

数値の配列と目標となる平均値が与えられる。あと1つ数値をリストに加えて、新しくできたリストの平均が目標値になるようにしたい。例えば、{ 3.0, 7.0, 2.5 }という配列と目標となる平均値が4.5と与えられた場合、リストに加える値は5.5になる。理由は(3.0+7.0+2.5+5.5)/4 = 4.5だからである。

私の解答はこちら。

public class FixTheAverage {

 public double add(double[] list, double target) {
  double num = target * (list.length+1); // 目標となる平均になるときの合計で初期化
  for( int i=0 ; i<list.length ; i++ ){
   num -= list[i]; // リストの要素で引き算
  }
  return num; // 残った値が答
 }

}

得点は248.69/250、中央値は245.14という易問。特に説明はいらないでしょう。

TopCoder SRM281 Div2 250Pts

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

ランレングス符号化とは同じ文字が連続して続く文字列を文字の発生回数とその文字によって圧縮するという手法である。例えば"AAAABBBCDDE"を圧縮すると"4A3BC2DE"である。1はこの例のように省略されることもあるし、そうでないこともある。前に正の整数がオプションとしてつけられたアルファベットの大文字からなる任意の文字列は適切にエンコードされた文字列と呼ばれる。適切にエンコードされたtextという文字列が与えられたときに、デコードされた文字列を返せ。もし、デコードされた文字列の長さが50文字を超えるようであれば、"TOO LONG"という文字列を返せ(ダブルクォートは不要)。

私の解答はこちら。

public class RunLengthEncoding {

 public String decode(String text) {
  StringBuffer sb = new StringBuffer();
  int n = 1;
  boolean isPrevNum = false; // 直前の文字は数字だったか
  for( int i=0 ; i<text.length() ; i++ ){
   if( Character.isDigit(text.charAt(i)) ){
    if( isPrevNum == true){
     n = n*10+Integer.parseInt(text.substring(i, i+1)); // 数値の更新
     if( n>50 ) return "TOO LONG"; // 途中で50を超えたら終了
    }else{
     // 直前がアルファベットだったら注目する文字を数値化
     n = Integer.parseInt(text.substring(i, i+1));
     isPrevNum = true;
    }
   }else{ // 数字とその文字からデコードを行う
    StringBuffer tmp = new StringBuffer();
    for( int j=0 ; j<n ; j++ ) tmp.append(text.charAt(i));
    sb.append(tmp);
    n = 1;
    isPrevNum = false;
   }
  }
  String ret = sb.toString();
  // デコードした結果、長すぎと分かった場合
  if( ret.length() > 50 ) return "TOO LONG";
  return ret;
 }

}

得点は199.34/250、中央値は約121点。提出者の正解率は約52%とやや低め。最初のコンパイルでコンパイルエラーがでたのは、途中で50を超えたら終了するというロジックがなかった点である。このロジックを入れないと、10000000000000000000Aのような符号化された文字が現れたときに、整数型で扱える範囲を超えておかしくなってしまうというのが原因だった。

TopCoder SRM280 Div2 250Pts

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

1以上、正の整数n未満の整数で、各桁の数がすべて違うものはいくつあるかを返すメソッドを作成せよ。

私の解答はこちら。

import java.util.HashSet;

public class UniqueDigits {

 public int count(int n) {
  int nUnique = 0;
  HashSet<Character> set = new HashSet();
  for( int i=1 ; i<n ; i++ ){
   String num = "" + i;
   for( int j=0 ; j<num.length() ; j++ ){
    set.add(num.charAt(j)); // 各桁を分解して集合を取る
   }
   // もとの桁数と集合の要素数が一致したら各桁の数はすべて異なる
   if( set.size() == num.length() ) nUnique++; 
   set.removeAll(set); // 集合は空にしておく
  }
  return nUnique;
 }

}

得点は233.17/250。中央値は約220点。要素は昇順にしなくても良いので、TreeSetではなくHashSetで十分。

TopCoder SRM279 Div2 300Pts

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

文章は踊っているとは、最初の文字が大文字で、続く文字が直前の反対の文字になっていることを言う。スペースは文字の種類(大文字、小文字)を決めるときには無視される。例えば、"Ab Cd"は踊っているという。sentenceという文字列が与えられたとき、この文字列を必要があれば(大文字と小文字を)変えて踊っているようにせよ。すべての空白について保存されるようにせよ。

私の解答はこちら。

public class DancingSentence {

 public String makeDancing(String sentence) {
  boolean nextUpper = true;
  StringBuffer sb  = new StringBuffer();
  for( int i=0 ; i<sentence.length() ; i++ ){
   char c = sentence.charAt(i);
   if( c == ' ' ){
    sb.append(" ");
    continue;
   }
   if( nextUpper == true ){
    sb.append(Character.toUpperCase(c));
    nextUpper = false;
   }else{
    sb.append(Character.toLowerCase(c));
    nextUpper = true;
   }
  }
  return sb.toString();
 }

}

得点は282.36/300、中央値は約272点。1文字ずつ逐次チェックすればOK、簡単な部類の問題と思います。

TopCoder SRM277 Div2 250Pts

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

なにか食べたくなってサンドイッチバーに着いた。多くの人のように、私はあるサンドイッチが好きである。事実、私は好きなタイプのサンドイッチを一覧にしたものを持っている。サンドイッチバーでは、特定の食べ物が食べられる。私は好きな順にサンドイッチの一覧を用意し、バーで作れるもっとも好きなサンドイッチを買う。バーがサンドイッチを買わせるためには、バーは欲しいと思う食材をすべて含んだものを用意しなければならない。available[]というサンドイッチバーが利用可能な食材のリストと、orders[]という私が好きな順にサンドイッチを並べたものが与えられたとき、私が買うサンドイッチの添え字を先頭を0としたうえで求めて返せ。私の好きなサンドイッチ(orders[])の各要素は、食材ごとにスペースで文字が区切られている。もし、バーが私の好きなサンドイッチを作れないようなら、-1を返せ。

重要な条件としてはorders[]の各要素の先頭と最後にはスペースはなく、文字はa-zとスペースからなるということと、available[]の各要素はa-zのアルファベットのみからなるということが挙げられる。

私の解答はこちら。

public class SandwichBar {

 public int whichOrder(String[] available, String[] orders) {
  for( int i=0 ; i<orders.length ; i++ ){
   String[] orderList = orders[i].split(" "); // 入れて欲しい食材一覧
   Boolean isOK = false;
   for( int j=0 ; j<orderList.length ; j++ ){
    isOK = false;
    for( int k=0 ; <available.length ; k++ ){
     if( available[k].equals(orderList[j])){
      isOK = true; // バーが用意できる食材ならOKで継続
     }
    }
    if( isOK == false ) break; // 途中で用意できない食材とわかったら次へ
   }
   if( isOK == true ) return i; // 全部食材が用意できたら、それが答。
  }
  return -1; // リストの最後までバーは好きなサンドイッチが作れなかった
 }

}

得点は228.95/250、中央値は約156/250。

TopCoder SRM276 Div2 250Pts

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

簡単に言うと、0点から10000点の成績が入った配列scores[]が与えられたときに、最高点に100点、最低点の人に0点を与えるよう正規化し、その結果を返せというものである。なお、正規化の結果発生する小数点以下の値はいつでも切り捨てるものとする。

私の解答はこちら。

public class TestCurve {

 public int[] determineGrades(int[] scores) {
  int max = 0;
  for( int i=0 ; i<scores.length ; i++ ){
   max = Math.max(scores[i], max); // CらしくなくJavaらしい、最大値を求めるループ
  }
  for( int i=0 ; i<scores.length ; i++ ){
   scores[i] = (int)(scores[i]*100.0/max);
  }
  return scores;
 }

}

得点は247.18/250。簡単でした。

TopCoder SRM275 Div2 250Pts

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

みんなはキッチンの入り口なんかでヒンジ付きのドアをみたことがあるかと思う。下の図をみるとはっきりするだろう（図は問題文で見てください）。このヒンジ付きドアは次のように動作する。止まる場所からある方向へ押すと、ドアは押し込まれる(1st swing)。ドアから手を離すと、ドアは反対側に振れる(2nd swing)。このとき、振れる角度は直前の角度のある数倍になる。反対側に振れることを繰り返すうちに、一定の割合で触れる角度は減っていく。5度以下になった時点でドアは振れなくなり、安定する。初期の押し込み角度initialAngle(整数型)と角度が減る割合(reduction)が与えられたとき、安定するまでに何回振れたかを返すメソッドを作成せよ。ドアは直前の振れた角度よりも次に振れる角度の方が小さいことに注意せよ。

私の解答はこちら。

public class HingedDoor {

 public int numSwings(int initialAngle, int reduction) {
  int nSwings = 0;
  double currentAngle = initialAngle;
  while( true ){
   if( currentAngle <= 5.0 ) break;
   currentAngle /= reduction;
   nSwings++;
  }
  return nSwings;
 }

}

得点は246.00/250。intをdoubleで扱うことに引っかからなければ易問。訳してて思ったのは、最初の押しを1st swingとすると、誤解を招くんじゃないかということです。押しただけでは振れた回数は0になるのよね。

TopCoder SRM274 Div2 250Pts

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

sequence[]という整数の配列が与えられる。これから重複した要素を取り除きたい。ただし、どの要素も最後に現れたものを残すようにせよ。唯一の要素は変化の内容にしなければならない。

私の解答はこちら。

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class SimpleDuplicateRemover {

 public int[] process(int[] sequence) {
  List<Integer> seq = new ArrayList<Integer>();
  for( int i : sequence ){
   seq.add(i);
  }
  Collections.reverse(seq); // 配列が逆順になる
  Set<Integer> uniq = new LinkedHashSet<Integer>();
  for( int i : seq ){
   uniq.add(i); // そこから最初に現れたものからなる集合を作る
  }
  seq = new ArrayList<Integer>(uniq); // さらにひっくり返すと答になる。
  Collections.reverse(seq);
  int[] ret = new int[seq.size()];
  for( int i=0 ; i<ret.length ; i++ ){
   ret[i] = seq.get(i);
  }
  return ret;
 }

}

この問題はギブアップ。集合ををひっくり返すCollections.reverse()を知っていれば簡単だったのだが。また、HashSetという入力順序を維持するSetがあることは大変ためになった。

TopCoder SRM273 Div2 250Pts

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

これまでの授業でもらった成績がmarks[]という整数型の配列で与えられる。成績はすべて0から10で与えられている。以降の宿題ではすべて10をもらうものとして、少なくとも最終成績で10を受け取るためには最低でもいくつの課題が必要になるか求めよ。平均成績が9.5以上であれば、10の成績を受けられるものとする。

私の解答はこちら。

public class AimToTen {

 public int need(int[] marks) {
  double total = 0.0;
  for( int i=0 ; i<marks.length ; i++ ){
   total += marks[i]; // totalはこれまでの課題の合計点
  }
  int nAssign = 0;
  while( true ){
   if( total / (marks.length + nAssign) >= 9.5 ) break; // 平均点計算
   total += 10; // 毎回課題は10点
   nAssign++;
  }
  return nAssign;
 }

}

得点は240.66/250。ちょっときれいに書こうとして時間を食ってしまいました。

TopCoder SRM272 Div2 250Pts

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

2つの数のハミング距離というものは2進数表現したときに、値が異なる位置の数である(同じ長さにするために、先頭に0を補うこともある)。例えば"11010"と"01100"は1、3、4桁目の値が違うので、ハミング距離は3になる。numbers[]といういくつかの2進数が文字列が配列として与えられる。それらの数からもっともハミング距離が小さくなる組のその距離を返せ。なお、numbers[]に登場する文字列はすべて長さが同じになっているものとする。

私の解答はこちら。

public class HammingDistance {

 public int minDistance(String[] numbers) {
  int max = numbers[0].length();
  for( int i=0 ; i<numbers.length ; i++ ){
   for( int j=i+1 ; j<numbers.length ; j++ ){
    int diff = 0;
    for( int k=0 ; k<numbers[i].length() ; k++ ){
     if( numbers[i].charAt(k) != numbers[j].charAt(k) ) diff++;
    }
    if( diff < max ) max = diff;
   }
  }
  return max;
 }

}

得点は246.57/250で比較的容易に解けました。i、jの2重ループで2つの文字列の組を、kで比較するので全部で3重ループになりました。

TopCoder SRM271 Div2 250Pts

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

全体が0～9の数値で表されたcodeという文字列が与えられる。各桁はいくつかのダッシュからなっている(下の表を見よということだが、表にはデジタル時計に見られるような、複数の棒を組み合わせた数値が書かれている）。メッセージのcheck functionというのは、メッセージ中のダッシュの合計で定義される。文字列codeのcheck functionの値を返せ。

私の解答はこちら。

public class CheckFunction {

 public int newFunction(String code) {
  int[] dashTable = {6,2,5,5,4,5,6,3,7,6}; // 0～9を表すのに用いられるダッシュの数
  int totalDash = 0;
  for( int i=0 ; i<code.length() ; i++ ){
   int num = (int)code.charAt(i)-'0';
   totalDash += dashTable[num];
  }
  return totalDash;
 }

}

得点は246.97/250。実装そのものよりもdashがデジタル数字の棒のことを指しているということに気付くのに時間がかかってしまいました。

RのapplyとrowSumsの比較

各所で行方向の和を求める際にはapplyよりもrowSumsがオススメであるということを聞いた。本当にそうなのか、確認するためにコードを書いてみた。下記の2パターンでapplyとrowSumsの実行時間がどのように変化するかということを調べている。サイズによる処理時間の変化を観察することにする。

• 列数10で固定で、行数のみ増やす
  
• 行数10で固定で、列数のみ増やす
  

# 行方向のみ数が変化する(列数は10で固定)
for( sz in (1:10)*50000 ){
 data <- matrix(runif(sz*10),nrow=sz)
 print(system.time(rowSums(data)))
 # print(system.time(apply(data,1,sum))) # applyの実行時間を測る場合はコメントを解除
}

# 列方向のみ数が変化する(行数は10で固定)
for( sz in (1:10)*50000 ){
 data <- matrix(runif(sz*10),ncol=sz)
 print(system.time(rowSums(data)))
 # print(system.time(apply(data,1,sum)))
}

上のような時間を出力するコードを私のマシンで実行し、出力された経過時間(system.time関数の返り値の第3引数)をプロットしたのが下の二つの図である。上図は列数固定の結果である。横軸は行数で縦軸は経過時間(単位は秒)を表している。下図は行数固定とした結果である。横軸は列数で、縦軸は経過時間(単位は秒)を表している。経過時間は、表示など処理のすべてにかかった時間である。下図は時間が0になっているが、表示の都合上小数点2桁までしか表されず、それ以下の細かい値まで取れていないためである。各計測点で2回経過時間を計測した平均をとっているが、2回の測定とも、概ね同じような実行時間になっていた。この結果より次のことが言える。

• applyは行数に比例して処理時間がかかるのに対し、rowSumsは数十万行の規模でもほぼ一定の短い時間で処理が可能
  
• 行数が一定の場合でもrowSumsの性能がapplyを上回るものの、その差は列数固定の場合よりは小さい
  

なお、rowSumsの仲間で、列方向の和を求める関数colSumsが存在する。また、マトリックスの行/列方向の平均を求める関数として、rowMeans/colMeansというものが存在する。今回のような単純な集計に対しては、applyよりも更に速い処理ができる関数があるということは覚えておいて損はないと思う。

2011年11月の学習記録

2011年11月に学習した主な本一覧。

なぜ、あなたはJavaでオブジェクト指向開発ができないのか(pp.151～読了)

プロになるためのWeb技術入門(pp.1～読了)

Webは多くのことを満遍なく知っておかなければならない。ネットワーク、サーバ、セキュリティ、プログラミング。気の遠くなるような話です。

演習で学ぶソフトウェアメトリクスの基礎(pp.1～19)

どんな指標にも顧客がいるわけで、例えば、テストで検出されたバグ数は開発マネージャというように、人によって最適なメトリクスは違うという言葉が印象的です。

ネットワークの構築・管理がしっかりわかる本(pp.1～読了扱い)

Windowsで小規模ネットワークの管理をするには良いかも。Linuxサーバを利用してネットワークを構築したいと思っているので、後半はニーズからそれていたため流し読み。

TopCoder SRM270 Div2 250Pts

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

スティーブは新しい車を買いたいと思っている。ただ、お金がないので、リーズナブルな安いものを好んでいる。ただ一番安い車の品質は疑問である。そこで、スティーブは車の価格一覧から3番目に安い価格の車を買うことにした。prices[]という、整数型の車の価格が入った配列が与えられる。pricesには何度も同じ価格が現れることもあるが、それは1度数えるだけとする。prices[]で3番目に安い車の価格を返す関数を作成せよ。もし、車の価格が3種類に満たない場合は、-1を返すようにせよ。

私の解答はこちら。

import java.util.Iterator;
import java.util.TreeSet;

public class BuyingCheap {

 public int thirdBestPrice(int[] prices) {
  TreeSet<Integer> ts = new TreeSet<Integer>();
  for( int i=0 ; i<prices.length ; i++ ){
   ts.add(prices[i]); // ユニークな集合の作成
  }
  if( ts.size() < 3 ) return -1; // 集合のサイズが2以下なら3番目に安い車はない
  Iterator<Integer> it = ts.iterator();
  int i = 0;
  while( it.hasNext() ){ // イテレータを利用して3番目に小さい要素を返す
   if( i==2 ){
    return it.next();
   }
   it.next();
   i++;
  }
  return -1;
 }

}

得点は136.52/250。Setの使い方の良い復習になりました。TreeSetにしておくと、集合を昇順にソートしてくれるので、そのまま問題に適用可能です。