2011年12月29日木曜日

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分...

2011年12月28日水曜日

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次元配列という発想が出なかったため、何週間か考えて解答。

2011年12月27日火曜日

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を引数に取るようなメソッドになるでしょうか。

2011年12月25日日曜日

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まで調べる方針で対応しました。

2011年12月23日金曜日

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だったのですね。

2011年12月22日木曜日

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))の実現方法の思いつきに時間がかかってしまいました。

2011年12月21日水曜日

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メソッドにはまっていたのを解消したついでに解きました。

2011年12月20日火曜日

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が発生して解くのに時間がかかってしまった。

2011年12月19日月曜日

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メソッドも繰り返し利用することで遅くなるので、その辺を中心に改良してみました。

2011年12月18日日曜日

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点にはなりますが。あまり使う機会はないですが、全員同じように再帰で書くので、再帰も全員必須の共通技術になっているのだなと思いました。

2011年12月17日土曜日

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点。

2011年12月16日金曜日

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で十分。

2011年12月15日木曜日

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。

2011年12月14日水曜日

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。簡単でした。

2011年12月13日火曜日

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があることは大変ためになった。

2011年12月11日日曜日

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重ループになりました。

2011年12月8日木曜日

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がデジタル数字の棒のことを指しているということに気付くのに時間がかかってしまいました。

2011年12月5日月曜日

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を上回るものの、その差は列数固定の場合よりは小さい
applyとrowSumsの速度比較(列数一定) applyとrowSumsの速度比較(行数一定)

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

2011年12月4日日曜日

2011年11月の学習記録

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

なぜ、あなたはJavaでオブジェクト指向開発ができないのか(pp.151~読了)
プロになるためのWeb技術入門(pp.1~読了)
Webは多くのことを満遍なく知っておかなければならない。ネットワーク、サーバ、セキュリティ、プログラミング。気の遠くなるような話です。
演習で学ぶソフトウェアメトリクスの基礎(pp.1~19)
どんな指標にも顧客がいるわけで、例えば、テストで検出されたバグ数は開発マネージャというように、人によって最適なメトリクスは違うという言葉が印象的です。
ネットワークの構築・管理がしっかりわかる本(pp.1~読了扱い)
Windowsで小規模ネットワークの管理をするには良いかも。Linuxサーバを利用してネットワークを構築したいと思っているので、後半はニーズからそれていたため流し読み。

2011年12月1日木曜日

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にしておくと、集合を昇順にソートしてくれるので、そのまま問題に適用可能です。

2011年11月30日水曜日

TopCoder SRM269 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について、おおまかに説明する。ひさびさに練習できる環境になったので、問題をといてみました。

あなたは今、古いコードを新しいコンパイラ用に変換している。"->"を"."に書き換えるのであるが、コメント部では置き換えてはならない。コメントの部分は//で始まり、行末で終わりである。program[]というコードの文字列型配列が与えられたとき、そのコードを変換した結果を返せ。

public class AccessChanger {

 public String[] convert(String[] program) {
  for( int i=0 ; i<program.length ; i++ ){
   int posComment = program[i].indexOf("//");
   if( posComment < 0 ){ // コメントがない場合
    program[i] = program[i].replaceAll("->", ".");
   }else{
    // コメント前だけ取り出して置換
    String tmp = program[i].substring(0, posComment);
    tmp = tmp.replaceAll("->", ".");
    // コメント以降を結合
    program[i] = tmp + program[i].substring(posComment);
   }
  }
  return program;
 }

}

得点は218.66/250。正直、入力となるprogram[]を破壊する書き方はあまり好きではないですね。コピーしたものを返したくなります。どちらが便利かは状況に依るのでしょうが。

2011年11月13日日曜日

TopCoder SRM268 Div2 250Pts

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

あなたはクロスワードパズルを作成している。盤面は作成したのだが、パズルに単語をあてはめる必要がある。空のクロスワードパズルはXという黒マスと.という空のマスからなる。スロットの長さがNというのは、Nの空マスが連続した状態として定義され、黒マスあるいは盤面の端に挟まれたものである。Nは最低でも2とする。
board[]という空のクロスワードパズル(Xと.の文字のみからなる)と、スロットのサイズsizeが与えられたとき、水平方向のスロットで長さがちょうどsizeになるものの数を返せ。boardの各要素はパズルの各行を表しているものとする。

私の解答はこちら。1行取り出して.がちょうどsize個現れる回数をカウントするという、言われた通りのことを実装するだけで済む。

public class CrossWordPuzzle {

 public int countWords(String[] board, int size) {
  int n=0;
  for( int i=0 ; i<board.length ; i++ ){
   String[] aLine = board[i].split("X");
   for( int j=0 ; j<aLine.length ; j++ ){
    if( aLine[j].length() == size ) n++;
   }
  }
  return n;
 }

}

得点は247.08/250。行方向のみカウントすればよいので、特にインデックス操作もいらず、非常に簡単に解くことができた。列方向もカウントすると、charAtメソッドなどを使って解くのだろうなと考えながら解いていました。

2011年11月11日金曜日

2011年10月の学習記録

2011年10月に学習した主な本一覧。仕事が割と修羅場に近い状態が続いたので、あまり勉強していませんが。

なぜ、あなたはJavaでオブジェクト指向開発ができないのか(pp.86~150)
この本は読むだけでなく、手を動かして理解するということが重要そうだと思いました。実装に現れるモノを洗い出して、シーケンス図やクラス図を書くというのは割と普通だと理解しました。普段テストばかりで開発をすっかり忘れている感もありますが、開発のイメージをする/思い出すには悪くない本かなと考えています。
Eclipseで学ぶはじめてのサーブレット&JSP(pp.1~20)
Webそのものを知ること、Javaの実装能力を上げること、Web系の言語も触っておきたいなということからJSPに手を出してみました。
微分積分学(pp.26~30)

TopCoder SRM267 Div2 250Pts

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

最低10万ドル以上の課税可能な人の2004年の税金は以下のテーブルから計算される(表は問題文中を参照)。あなたの税金を計算するために、課税対象収入と税率と控除の適切なグループを見つけよ。

誰かがいくら税金を払うか分かった時、元の課税対象の収入はいくらだったのかということが知りたい。taxAmountという課税された額が引数として与えられたときに、もとの課税対象収入のもっとも近い額を返すTaxTableというメソッドを作成せよ。結果は最も近いドルの値で返せ(つまり小数点第1位で四捨五入)。もし、taxAmountが小さすぎて、テーブルになければ-1を返すようにせよ。

私の解答はこちら。

public class TaxTable {

 public int income(int taxAmount) {
  int max = (1000000 + 25357)*20 / 7 + 1; // 入力の上限から分かる探索範囲の上限
  int ret = -1;
  int least = 25000 - 6525; // 入力の下限を計算
  if( taxAmount < least ){
   return -1;
  }
  double minDiff = Double.MAX_VALUE;
  // 入力の下限から上限までで誤差が最小になる収入額を計算
  for( int i=100000 ; i<=max ; i++ ){
   double mul = retMultiplier(i);
   double sub = retSubtraction(i);
   double diff = Math.abs((i*mul-sub)-taxAmount);
   if( diff < minDiff ){
    minDiff = diff;
    ret = i;
   }
  }
  return ret;
 }
 private double retMultiplier(int v){ // 課税対象額に応じた税率
  if( v>=100000 && v<117250 ){
   return 0.25;
  }else if( v<178650 ){
   return 0.28;
  }else if( v<319100 ){
   return 0.33;
  }else{
   return 0.35;
  }
 }
 private double retSubtraction(int v){ // 課税対象額に応じた控除額
  if( v>=100000 && v<117250 ){
   return 6525.0;
  }else if( v<178650 ){
   return 10042.50;
  }else if( v<319100 ){
   return 18975.0;
  }else{
   return 25357.0;
  }
 }
}

得点は126.90/250。毎回300万回程度のループが回っているので、あまり速い動作にはならないと思います。TopCoderでは2秒で結果が返ってこればOKで、目安としては1000万回のループ以下であればOKということになるそうです。入力の上限がない場合は工夫が必要とは思いますが、コンテストで簡単な部類の問題なのでそこまで考えなくても良いようにできているのだと思います。

2011年11月9日水曜日

JMRX勉強会【プレゼンストラテジー リサーチへの応用】のメモ

約二か月前のことですが、初めてマーケティング業界の勉強会に参加してきました。マーケティング業界の悲哀が伝わってきました。プレゼンについては働く業界が違えど、あまり変わらないのかなという思いになりました。

マーケティングのお仕事の辛そうな点@打ち合わせ中

  • 意思決定者(=経営者)に、前提をひっくり返されること
  • クライアントの理解度がばらついている中、バランスを取った説明をすること

マーケティングの個人における課題

  • 話すのが苦手、あるいは得意すぎて話し過ぎる
  • 緊張、話が飛ぶ
  • 時間配分のコントロール
  • 人の目が見れない
  • 話し方、動きに癖がある

リサーチの目的とは?やりたいことの発案->やりたいことの実現

  1. 対象・マーケットの価値観の汲み取り
  2. イノベーションの導入
  3. 競合との差別化
  4. ニーズの反映
  5. 生み手・作り手の情熱
辛いのは、クライアントの後押しばかりではないということ。時にはリサーチの結果、無理であることを伝えなければならないということもある。また、リサーチの中でクライアントが欲していることに応えられているかということは意識する必要がある。

プレゼンの基本~魅力を伝える3つの価値

  1. 表層価値
  2. 経験価値
  3. 背景価値

3つの価値はお見合い相手の女性にも当てはまるようだ。表層価値は体裁であり、美しさである(短時間で分かる)。経験価値は将来を共有することで得られる価値、つまり気が利くということを表している。背景価値というのは、対象の背景に存在し、将来享受できると想像される価値、つまり育ちの良さということになる。プレゼンでは、表層価値に該当するのは身なり、経験価値(プレゼンではこれが一番大事!)は誠実感や時間配分、背景価値は会社のブランドやプレゼンターの知見ということになる。

プレゼンをより良いものにする改善策としては、見た目については次のようなものがある。

  • 服装は無難に
  • 自分らしさを出しすぎない
資料については、次のような方針がよい
  • 見せる資料と配る資料は別の方が良い。また極力シンプルなものがよい
  • 主文は言い切りで、最小限の文字数に
  • 表は着眼点を明確に(見て欲しい所は強調)
  • グラフは主張しすぎないように
  • 明確な構図
    • 例:左ビジュアル、右文章
  • 見出しコピーはキャッチーに
  • 読ませる工夫が重要
  • 集計データの報告ではない(結論が先)
プレゼンについては、次のような方針がよい。
  • 時間配分は2/3型
    • つかみ、概要、総括、詳細、まとめまでが2/3、残りの1/3は質疑応答
  • ちょっと勿体つけて、最後にドカン
    • 根拠や理屈はあとから熱く、細かく

プレゼンの作法は人によって違うので、参考になる箇所、認められないという箇所さまざまありました。コミュニケーション能力の向上を目指してうまいこと取り込んでいきたいです。

2011年11月8日火曜日

TopCoder SRM265 Div2 250Pts

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

GUIは、さまざまなGUIコンポーネントで単語を適切に表示するテキストの決まりごとに依存している。1行のテキストで幅を決められれば、ウィンドウ中のテキストを中央にするのに役立てられる。あなたには、文字と空白からなる文が与えられる。また、あるフォントに対する、アルファベットの小文字(lowercawse)と大文字(uppercase)の文字の幅が与えられる。このとき、文の幅を返すメソッドを作成せよ。

uppercase[]とlowercase[]は26の要素からなる。uppercaseの先頭はAという文字の幅を表し、最後はZという文字の幅を表す。小文字の場合も同様で先頭はaの幅、最後はzの幅を表す。空白はいつも3ピクセルに相当する。また、文字が描画されたとき、隣り合う文字は1ピクセルあけられているものとする。

私の解答はこちら。

public class FontSize {

 public int getPixelWidth(String sentence, int[] uppercase, int[] lowercase) {
  int totalWidth = 0;
  for( int i=0 ; i<sentence.length() ; i++ ){
   if( Character.isUpperCase(sentence.charAt(i)) ){
    int idx = sentence.charAt(i) - 'A';
    totalWidth += uppercase[idx];
   }else if( Character.isLowerCase(sentence.charAt(i)) ){
    int idx = sentence.charAt(i) - 'a';
    totalWidth += lowercase[idx];
   }else{
    totalWidth += 3;
   }
   if( i < sentence.length()-1 ) totalWidth++;
  }
  return totalWidth;
 }

}

制約上、文字はアルファベットと空白しかないので、上のような回答が許されていることに注意。ちょっとした場合分けで解けるので、難しくはないと思います。

2011年11月7日月曜日

TopCoder SRM231 Div2 450Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文のおおまかな和訳については、後日掲載するものとして、ひとまず解答だけ載せておく。

public class Stitch {
 public String[] stitch(String[] A, String[] B, int overlap) {
  String[] blended = new String[A.length];
  for( int i=0 ; i<A.length ; i++ ){
   blended[i] = A[i].substring(0, A[i].length()-overlap);
   for( int j=1 ; j<=overlap ; j++ ){
    double val = ((overlap+1.0-j)*A[i].charAt(A[i].length()-overlap+j-1)+
                 j*B[i].charAt(j-1))/(overlap+1);
    char cval = (char)Math.round(val);
    blended[i] += cval;
   }
   blended[i] += B[i].substring(overlap);
  }
  return blended;
 }
}

昔解いた問題を下書きに置きっぱなしにしておくのももったいないので、掲載することにした。

2011年11月6日日曜日

TopCoder SRM266 Div2 250Pts

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

2つの飛び乗れる石がある10フィートの川を渡りたいと思っている。何回かジャンプが必要になるが、興味があるのは、一番長い距離のものだけである。これは明らかに大事な問題で、できるだけ飛ぶ距離の最大値を小さくしたいと思っている。二つの石の距離はユークリッド距離で定義する。
さて、整数型のx[]とy[]という2つの要素を持つ配列が与えられる。(x[i]、y[i])はi番目の石の座標を表している。あなたははじめ、x座標が0で、y座標は任意の値を取り得る川岸にいる。反対側の岸はx座標が10でy座標は任意の値を取る川岸である(つまり、川はy軸に平行なものと考え、その中に石が二つ置かれているということになる)。
あなたが飛ばなければならない最大距離をもっとも近い整数値に丸めて返せ。なお、石はx座標の1~9の整数値、y座標の0~10の整数値の場所にあるものとする。また、二つの石は同じ場所にはないものとする。

私の解答はこちら。

// 石1 -> 石2 -> 対岸
// 石1 -> 対岸
// 石2 -> 石1 -> 対岸
// 石2 -> 対岸
// 以上の4パターンを飛ぶ順番として列挙しておけばよい。以下のコードでは上から順に0~3という
// 添字を割り当てて、各ケースにおける飛ばなければならない距離の最大値を計算している。
public class SwimmersDelight {
 public int longestJump(int[] x, int[] y) {
  double[] maxDist = new double[4];
  double distBetweenStones = Math.sqrt(Math.pow(x[0]-x[1],2)+Math.pow(y[0]-y[1],2));
  maxDist[0] = Math.max(x[0], distBetweenStones);
  maxDist[0] = Math.max(maxDist[0], 10-x[1]);
  maxDist[1] = Math.max(x[0], 10-x[0]);
  maxDist[2] = Math.max(x[1], distBetweenStones);
  maxDist[2] = Math.max(maxDist[2], 10-x[0]);
  maxDist[3] = Math.max(x[1], 10-x[1]);
  double max = 10;
  for( int i=0 ; i<4 ; i++ ){
   if( maxDist[i] < max ){
    max = maxDist[i];
   }
  }
  return (int)Math.round(max);
 }

}

得点は108.13/250。結局、全パターンを列挙して求めるのが一番早いようだ。提出者の正解率が3割程度ということから、結構難しい問題だったようだ。

2011年11月2日水曜日

TopCoder SRM264 Div2 250Pts

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

ある先生が二つの成績をつける手法を思いついた。学生は点数を0~100の間で受ける。全学生の成績はscores[]という整数型配列で表され、昇順にソートされている。学生は最終的に0から8のグレードで評価される。先生は知的に各生徒に必要な成績を割り当てている。scoreのi番目の要素はi番目の要素のグレードに対応する。同じ点数の場合、グレードは高い方から低い方にソートされる。
最初の成績をつける方法では、ある学生にXという成績をつけたいと思った場合、それ以上の成績を持つ学生は少なくともX以上の成績になる。この制約はさておき、学生はとりうる中で最も低いグレードを付けられる。例えば、3人の学生の成績が{60,80,80}であり、先生が彼らに{3,8,6}というグレードを割り当てたいと思った場合、学生は{3,8,8}というグレードを受け取ることになる。3番目の学生は同じ点数の人で6より高い8という評価を受けている人がいるため、少なくとも8の成績を受け取ることになるからである。
2番目の方法では、ある学生にXという成績をつけたいと思った場合、その学生の点数以下の学生は最大でもXという評価しかしないというものである。先ほどの例では、3人の学生は{3,6,6}というグレードを受け取ることになる。というのも、2番目の学生は3番目の学生の評価に引きずられるからである。
二つの手法を適用し、各学生に対しグレードの差の絶対値を求め、その総和を返すようなメソッドを作成せよ。

私の解答はこちら。

public class GradingSystem {
 public int fairness(int[] scores, int[] grades) {
  int min = 8;
  int max = 0;
  int sMax = 0;
  int sMin = 0;
  for( int i=0 ; i<scores.length ; i++ ){
   max = Math.max(max, grades[i]);
   sMax += max;
  }
  for( int i=scores.length-1 ; i >= 0 ; i-- ){
   min = Math.min(min, grades[i]);
   sMin += min;
  }
  return Math.abs(sMax - sMin);
 }
}

この問題のポイントになるのは、同じ成績であれば、グレードは降順にソート済みであるということである。この条件により実装の量は少なくて済むようになっている。これに気付くのが遅かったため、コーディングにはかなり時間がかかりました。

2011年10月21日金曜日

TopCoder SRM261 Div2 250Pts

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

この問題では、エクセルのシートの列ラベルの生成ルールについて考えている。エクセルのシートの列は、1列目はA、2列目はB、...26列目はZ、27列目はAA、28列目はAB、...702列目はZZという関係がある。何列目かを表す整数型の値column(1~702に限定)が与えられたときに、列を表す文字列を返すというのが問題である。

私の解答はこちら。

public class SpreadsheetColumn {
 public String getLabel(int column) {
  int d1 = column / 26;
  int d2 = column % 26;
  char c2 = d2 == 0 ? 'Z' : (char) (d2-1+'A');
  d1 = d2%26==0 ? d1-1 : d1;
  if( column > 26 ){
   char c1 = d1 == 27 ? 'Z' : (char) (d1-1+'A');
   return "" + c1 + c2;
  }else{
   return "" + c2;
  }
 }
}

正直なところ、結構苦労していました。10進数の0に相当するものがない(Aは1扱いなので)のが、解く際に混乱していた原因です。もっとも、0に相当する文字があれば、簡単すぎる問題になってしまうのでしょうけれど。

TopCoder SRM257 Div2 250Pts

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

codeの文字列を先頭から順番に調べ、keyにマッチしたものがあれば、それが何番目になるかということを調べ、エンコーディングした結果を返す。例えばkey="ABCDEFGHJK"(10文字で固定)、code="XJK"であれば、90になる。Xは存在せず、Jは9番目の文字で、Kは10番目の文字(10番目の文字は0と扱う)だからである。また、少なくともcodeの1文字はkeyの中に存在しているものとする。

私の解答はこちら。

public class SubstitutionCode {
 public int getValue(String key, String code) {
  int num = 0;
  for( int i=0 ; i<code.length() ; i++ ){
   // indexOfは引数の文字がkeyに存在すれば0以上の値になる。
   // 存在しない場合は-1になる
   int v = key.indexOf(code.charAt(i));
   if( v >= 0 ){
    num = num * 10 + (v+1) % 10;
   }
  }
  return num;
 }
}

得点は242.99/250。英語の説明が難しいので、大分意訳して説明しています。詳細は英語の問題文をご覧ください。

2011年10月17日月曜日

TopCoder SRM262 Div2 250Pts

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

numという数値が与えられる。numに対し、小さい方の二桁の数を置き換えて、factorで割り切れるようにする。置き換えた結果の数はできるだけ小さくしたい。置き換えた数値を(2桁の)文字列として返せ。例えば、num=275とfactor=5であれば、"00"が回答になる。小さい二桁の数を00から99まで順に検討していくと、候補となる値の最小値200は5で割り切れるからである。

私の解答はこちら。

public class DivToZero {

 public String lastTwo(int num, int factor) {
  int n = num - num % 100;
  int res = 0;
  for( int i=0 ; i<100 ; i++ ){
   int val = i+n;
   if( val % factor == 0){
    res = i;
    break;
   }
  }
  return String.format("%02d",res);
 }

}

得点は240.22/250。C言語を使っていたのが長いせいか、ついフォーマット整形関数にsprintfを探してしまうワタシ。

2011年10月11日火曜日

TopCoder SRM260 Div2 250Pts

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

イジングモデルとは、磁性体の性質をシミュレーションする統計的物理学でよく用いられているモデルである。このモデルでは、長方形のグリッドを考え、各点で+と-という値があると考える。
そのような詩ピンの設定があった時、エネルギーは隣り合うセルとの組み合わせを足し合わせることによって計算される(水平方向と垂直方向のみ考える)。もし、対が同じ値(+と+、あるいは-と-)であれば、エネルギーの合計量に-1を加える。そうでなければ、+1を加えることになる。spins[]という各点の値が与えられるとき、この状態に対するエネルギーの合計量を計算せよ。 (注:spins[]の各要素は同じ長さであり、+や-という文字が長方形に並ぶのである)

私の解答はこちら。

public class IsingModel {
 public int energy(String[] spins) {
  int nRow = spins.length;
  int nCol = spins[0].length();
  int nSame = 0;
  int nDiff = 0;
  for( int i=0 ; i<nRow ; i++ ){
   for( int j=0 ; j<nCol-1 ; j++ ){
    if( spins[i].charAt(j) == spins[i].charAt(j+1) ){
     nSame++;
    }else{
     nDiff++;
    }
   }
  }
  for( int i=0 ; i<nRow-1 ; i++ ){
   for( int j=0 ; j<nCol ; j++ ){
    if( spins[i].charAt(j) == spins[i+1].charAt(j) ){
     nSame++;
    }else{
     nDiff++;
    }
   }
  }
  return nDiff-nSame;
 }
}

ポイントは、水平方向と垂直方向で、ループのさせ方が異なるので、2回に分けて計算するということだと思います。それ以外は、特に悩まなかったです。

2011年10月10日月曜日

TopCoder SRM259 Div2 250Pts

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

どんな競技においても、レーティングが上がり続けることはとても重要な統計量である。あなたは、あるプレーヤーに対し、その統計量を計算することになった。ratingChanges[]というあるプレーヤーのレーティングの時系列に沿った変化を表す整数型の配列が与えられる。レーティングが正の変化を連続で続けた最大回数を返すメソッドを作成せよ。また、0は正の値ではないことに注意せよ。

私の解答はこちら。最大を更新したか?というboolean変数を準備しようと思っていたのですが、それもコードを書くうちに必要がないということが判断でき、比較的シンプルに書けたと思います。

public class CompetitionStatistics {

 public int consecutiveGrowth(int[] ratingChanges) {
  int maxlen = 0;
  int len = 0;
  for( int i=0 ; i<ratingChanges.length ; i++ ){
   if( ratingChanges[i] > 0 ){
    len++; // 連続で続いたので1加える
   }else{
    len=0; // リセット
   }
   maxlen = Math.max(maxlen, len); // これまでの最高回数に達したか?
  }
  return maxlen;
 }

}

2011年10月9日日曜日

TopCoder SRM258 Div2 250Pts

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

この問題は、0点から100点までのテストの点数の配列scores[]が与えられたとき、その配列のモードを配列にして返せというものである。モードは最頻値とも呼ばれており、もっとも出現回数が多かった値を指す。モードが配列になるのは、最頻値が複数になることもありうるからである。例えばsocres[] = {10,10,20,20,25}であれば、最頻値は2回登場した{10,20}ということになる。

私の解答はこちら。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;

public class ClassScores {
 public int[] findMode(int[] scores) {
  HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
  // Hashで、点数(キー)と出現回数の組を作る
  for( int i=0 ; i<scores.length ; i++ ){
   if( hm.containsKey(scores[i]) == false ){
    hm.put(scores[i], 1);
   }else{
    hm.put(scores[i], hm.get(scores[i])+1);
   }
  }
  // 出現回数の最大値を計算する
  int maxTimes = 0;
  Iterator<Integer> it = hm.keySet().iterator();
  while( it.hasNext() ){
    Integer val = it.next();
    int times =  hm.get(val);
    if( times > maxTimes ) maxTimes = times;
  }
  // 出現回数が最大値の点数をリストにする
  ArrayList<Integer> list = new ArrayList<Integer>();
  it = hm.keySet().iterator();
  while( it.hasNext() ){
    Integer val = it.next();
    if( maxTimes ==  hm.get(val) ){
     list.add(val);
    }
  }
  int[] array = new int[list.size()];
  for( int i=0 ; i<list.size() ; i++ ){
   array[i] = list.get(i);
  }
  // リストは昇順にソート
  Arrays.sort(array);
  return array;
 }
}

得点は122.25/250。アルゴリズムは分かっているのに、実装の方法が分からないことで、大幅なタイムロス。イテレータとか仕事で使いませんからとか言ってみる。

2011年10月5日水曜日

TopCoder SRM254 Div2 500Pts

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

多人数協力型のオンラインゲームを作っている。チームのプレーヤーはゲームの間互いにチャットができ、敵を作るAIを作成するときに、その会話を利用したいと思っている。AIの機能には、与えられたフレーズがプレーヤーのチャットの一部であるか判断するということが含まれている。もちろん、さまざまなフレーズが与えられるのだが、できるだけそれを見つけ出したいと思っている。フレーズに使われるのは、簡略表記が最も一般的であろう。例えば、cptrというのはcaptureという言葉の略である。さて、問題ではtypedというプレーヤーがタイプした文字列と、それに対しチェックしたいphraseという文字列が与えられる。phraseからtypedの文字を取り除いた結果を返せ。もし、phraseからtypedを単に除いた文字列が得られないようであれば、"UNMATCHED"を返せ。なお、この制約により、返す文字列は唯一に定まる。

私の解答はこちら。

public class ListeningIn {

 public String probableMatch(String typed, String phrase) {
  StringBuilder sb = new StringBuilder();
  int nStart = 0;
  int nPrev = 0;
  for( int i=0 ; i<typed.length() ; i++ ){
   String aTyped = typed.substring(i, i+1);
   if( nPrev > phrase.length()-1 ){
    // まだ検討しなければならない文字が残っているのに、終端まで来てしまった
    return "UNMATCHED";
   }
   for( int j=nStart ; j<phrase.length() ; j++ ){ // 直前の文字の次からスタート
    if( phrase.substring(j, j+1).equals(aTyped) ){ // 探したい文字があった
     nStart = j+1; // 次の開始位置
     break;
    }
   }
   if( nPrev == nStart ) return "UNMATCHED"; // 次の開始位置が見つからなかった
   // typedに現れた2文字の間を解答を格納する変数に入れる
   sb.append(phrase.substring(nPrev, nStart-1));
   nPrev = nStart; // 次の開始位置は直前の開始位置になる
  }
  sb.append(phrase.substring(nPrev));
  String ret = sb.toString();
  return ret;
 }

}

typedの先頭から順に何番目の文字と一致するかということを調べて、次の文字からは先頭の位置から順に後方に現れ、phraseの一番後ろに行くまでにtypedがすべて現れればOKというのが方針。実装するに当たり、空白は飛ばすなど要求と異なる実装をしていたので、かなり時間がかかってしまいました。

2011年10月1日土曜日

9月の学習記録

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

マンガで分かるWebマーケティング(読了)
マーケティングでは、目標に向けた指標を導入するというのが重要なんですね。Webサイトだと、単にPVを増やすだけではなく、購買行動につながるようにしなければならないわけで、ここを間違えてはいけない。
マインドマップから始めるソフトウェアテスト(読了)
マインドマップはアイディアの発散に使えます。AといえばB、BといえばC...ということです。これがソフトウェアテストになぜ使えるか?というと、テストで大事なことは機能を網羅する(特に境界値などエラーに対する処理)ということで、発想を広げることが大事だからということです。ただし、バグは複数の機能の組合せによって発生することが多いので、それを考慮してテストケースにまとめるということが重要です。
なぜ、あなたはJavaでオブジェクト指向開発ができないのか(pp.1~85)
オブジェクト指向のイメージというのを、簡単につかめないかとよんでます。
遺伝的アルゴリズム(pp.31~50)(著:坂和)
微分積分学(pp.1~25)

TopCoder SRM256 Div2 250Pts

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

次のような数字の並びを考える。

10341
4581520
110234681
01144113240
31469226579

一番上の行と、一番左の列を除いて、各数は左、上、左上の3つの値の和になっている。1行目を表すrow[]と、1列目を表すcol[]が与えられたときに、最も右下の値の計算結果を返せ。上の例ではrow[] = {1,0,3,4,1}、 col[] = {1,4,1,0,3}という意味になる。また、row[]とcol[]の要素数は常に一致するものとする。

私の解答はこちら。

public class GridGenerator {

 public int generate(int[] row, int[] col) {
  int[][] grid = new int[row.length][col.length];
  for( int i=0 ; i<row.length ; i++ ){
   grid[i][0] = row[i];
   grid[0][i] = col[i];
  }
  for( int i=1 ; i<row.length ; i++ ){
   for( int j=1 ; j<col.length ; j++ ){
    grid[i][j] = grid[i][j-1] + grid[i-1][j-1] + grid[i-1][j];
   }
  }
  return grid[row.length-1][col.length-1];
 }

}

row[]、col[]を二次元配列の1行目、1列目に設定してしまえば、簡単な問題に落とし込めると思います。

2011年9月29日木曜日

TopCoder SRM255 Div2 250Pts

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

数値を文字列としてソートしてしまうというのは、よくある話である。ここでは、sequence[]という、文字列を昇順で並べた文字列型配列が引数として与えられる(ソートの方法は辞書式順序のルールに従う)。これに代わって、配列の要素を数値と見なして配列を昇順にソートしたときの結果を返せ。返す型は文字列型であることに注意。

私の解答はこちら。

import java.util.Arrays;

public class SequenceOfNumbers {
 public String[] rearrange(String[] sequence) {
  int[] intSeq = new int[sequence.length];
  for( int i=0 ; i<intSeq.length ; i++ ){
   intSeq[i] = Integer.parseInt(sequence[i]);
  }
  Arrays.sort(intSeq);
  String[] ret= new String[intSeq.length];
  for( int i=0 ; i<ret.length ; i++ ){
   ret[i] = Integer.toString(intSeq[i]);
  }
  return ret;
 }
}

得点は245.26/250。コンパイルエラー・バグなしの一発回答。素直に実装するだけ。

2011年9月28日水曜日

TopCoder SRM254 Div2 250Pts

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

conflicts[]という文字列型配列が与えられる。配列の各要素は多人数が参加するゲームの1人のプレーヤーを表している。i番目の要素がプレーヤーiを表し、プレーヤーiを表す配列のj番目の要素はiがjに対し、勝つのであれば'W'、同点なら'T'、負けなら'L'という文字になる。やるべきことは、各プレーヤーが他のプレーヤーに対し、少なくともp%勝ち、q%負けるということを保証することである。もしこれらの要求が満たされないプレーヤーがいれば、0を始点としたインデックスでプレーヤーを表したときに、初めて現れる要求を満たさないプレーヤーのインデックスを返し、全員が要求を満たすのであれば、-1を返す。もし全体でN人いるようであれば、少なくともWはceil((N-1)*p/100)(小数点以下切り上げを行った整数のこと)の割合でプレーヤーiを表す配列の要素中に'W'という文字が現れることになる。負けを表す式も同様である。

また、配列全体の要素を数えるとWとLは同数である。また、プレーヤーiのi番目の要素は常にTである(自分自身と戦うわけではない)。

私の解答はこちら。

public class BalancedGame {
 public int result(String[] conflicts, int p, int q) {
  int nPlayer = conflicts.length;
  for( int i=0 ; i<nPlayer ; i++ ){
   int nW = 0;
   int nL = 0;
   for( int j=0 ; j<conflicts[i].length() ; j++ ){
    if( conflicts[i].charAt(j) == 'W' ){
     nW++;
    }else if( conflicts[i].charAt(j) == 'L' ){
     nL++;
    }
   }
   if( (double)nW/(nPlayer-1) < p/100.0 || (double)nL/(nPlayer-1) < q/100.0 ) return i;
  }
  return -1;
 }
}

先頭のプレーヤーから順番にWとLを数えて、条件を満たさないプレーヤーのインデックスを返せばよい。割り算はnPlayer-1であることに注意がいる。当初nPlayerで割っていたので、1回システムテストで落とされてしまった。

2011年9月25日日曜日

TopCoder SRM253 Div2 250Pts

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

長方形の物体といくつかのサイズが異なる箱が与えられる(この問題では箱の高さは考慮しない)。あたなは、物体を詰めるのに十分なもっとも小さい面積の箱を知りたい。箱に物体を詰めるとき、辺は箱と平行にしなければならない。つまり、物体は0度、90度、180度、270度にしか回転させられない(実際には0度と90度だけ考えればよいのは明らかだが)。

物体の縦横のサイズを表す整数値objWidth、objLengthと箱の縦横のサイズを表すboxWidth[]、boxLength[]が与えられる。2つの配列のi番目の要素がi番目の箱のサイズを表している。物体が収まるもっとも面積が小さい箱の、その面積を返せ。どの箱にも収まらないなら-1を返せ。

私の解答はこちら。

public class ObjectPacking {

 public int smallBox(int objWidth, int objLength, int[] boxWidth, int[] boxLength) {
  int s = Math.min(objWidth, objLength); // 物体の短い辺
  int l = Math.max(objWidth, objLength); // 物体の長い辺
  int minVolume = Integer.MAX_VALUE;
  for( int i=0 ; i<boxWidth.length ; i++ ){
   int si = Math.min(boxWidth[i], boxLength[i]); // i番目の箱の短い辺
   int li = Math.max(boxWidth[i], boxLength[i]); // i番目の箱の長い辺
   if( s <= si && l <= li ){ // 箱に収まる条件
    int vol = si * li;
    if( vol < minVolume) minVolume = si*li;
   }
  }
  return minVolume == Integer.MAX_VALUE ? -1 : minVolume; // 箱に収まるものがあればminVolumeになる。
 }

}

結局、箱を回転させて収められるという制約は、物体の縦横の小さい辺と大きい辺がそれぞれ、i番目の箱の小さい辺と大きい辺に収まるという"置き換え"ができるか否かに尽きるような問題でした。

TopCoder SRM252 Div2 250Pts

今日の問題はなぜか検索をかけても出てこないのでリンクは省略。それでは、問題について説明する。

山の離れた地域で交戦中の一族がいる。軍隊をよりよい組織にするために、N個の前哨基地を丘に沿ってまっすぐに建てた。各前哨基地は怪しい動きの監視と、非常事態には知らせを広める役割がある。一旦基地が警報を受け取ると、メッセンジャーは継続的にアルプフォンを吹き、他の基地に警報を知らせる。二つの隣り合う基地に音が届くのに、ちょうど1単位の時間がかかる。ある基地と最も近い警報源からの距離がxだけ間が離れていれば、x単位時間音が届くのに時間がかかるということになる。

いくつかの基地が刑法を鳴らしたとしよう。あなたは、その他のすべての基地が知らせを受け取るのに何単位時間かかるかということを決めるのが課題である。outposts[]というN個の基地の状態を表す文字列が引数で与えられる。i番目の文字がi番目の基地であり、xという文字が警報を、-が静かな状態を表すものとする。

例えば、"--x-x---"であれば、3を返す。これは一番右の-にxからの警報が届くのに3単位時間かかるからである。

私の解答はこちら。

public class WarCry {
 public int alertTime(String outposts) {
  char[] line = outposts.toCharArray();
  int[] dist = new int[line.length];
  // とりうる距離の最大値は配列の長さ-1なので、それ以上に大きい値で初期化
  for( int i=0 ; i<dist.length ; i++ ){
   dist[i] = dist.length;
  }
  // 各xからの距離(インデックスの差)を計算する
  // xが出てきたときが更新するタイミングになる
  // ループの中で距離は最小値に更新されていく。
  for( int i=0 ; i<line.length ; i++ ){
   if( line[i] == 'x' ){
    for( int j=0 ; j<line.length ; j++){
     int tmpDist = Math.abs(i-j);
     if( tmpDist < dist[j] ){
      dist[j] = tmpDist;
     }
    }
   }
  }
  // 全体で最も警報源から離れている場所を調べる
  int maxDist = -1;
  for( int i=0 ; i<dist.length ; i++ ){
   if( dist[i] > maxDist ) maxDist = dist[i];
  }
  return maxDist;
 }
}

得点は220.84/250。xが出るたびに何度も更新しないといけないので、もう少しうまくかけないかなと思いました。一番簡単な解答ではあると思います。

2011年9月24日土曜日

TopCoder SRM251 Div2 250Pts

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

国の大統領になる二人の候補者によるキャンペーンが行われている。新聞の世論調査では、各州で何パーセントの人が各候補者に投票するかということがはっきりしている。候補者1は最後の宣伝をしたく、どこの州に行くべきか知る必要がある。likelihoods[]という文字列型配列が与えられる。各文字列は1つの州を表している。文字列は1と2からなり、1は1に投票する数を、2は2に投票する数を表している。最も1に対する投票率が低い州のインデックスを返せ(インデックスは0から始まる)。もし最低投票率の州が複数あるようであれば、最初に現れた州のインデックスを返すようにせよ。

私の解答はこちら。

public class Elections {
 public int visit(String[] likelihoods) {
  int visit = 0;
  double ratio = 1.0;
  for( int i=0 ; i<likelihoods.length ; i++ ){
   char[] aState = likelihoods[i].toCharArray();
   int n1 = 0;
   for( int j=0 ; j<aState.length ; j++ ){
    if( aState[j]=='1' ) n1++;
   }
   if( (double)n1/aState.length < ratio ){
    visit = i;
    ratio = (double)n1/aState.length;
   }
  }
  return visit;
 }
}

charの配列に1文字ずつに分解するか、Stringのi番目の文字として逐一取り出す方が良いのか悩ましいところ。

2011年9月22日木曜日

TopCoder SRM250 Div2 250Pts

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

電機メーカーがあなたに抵抗の色コードを解読するプログラムを書くように呼んだ。code[]という、抵抗に刻まれた3つの色帯が文字列型配列として与えられる。その抵抗が表す抵抗値(オーム)を返せ。最初の2つの色が値を、最後の1つの色が先頭2つの値に対して掛ける値を示している。

例えば、code[]={"red","brown","red"};であれば、返すべき抵抗値は21*10^2=2100になる。

抵抗に用いる色については一般的な抵抗と同じである。例えば、こちらを参考されたい。

私の解答はこちら。

public class ColorCode {
 public long getOhms(String[] code) {
  String[] color = {"black","brown","red","orange","yellow",
                    "green","blue","violet","grey","white"};
  int val = 0;
  for( int i=0 ; i<2 ; i++ ){
   for( int j=0 ; j<color.length ; j++){
    if( code[i].equals(color[j]) ){
     val = val*10 + j;
     break;
    }
   }
  }
  int p = 0;
  for( int i=0 ; i<color.length ; i++ ){
   if( code[2].equals(color[i])){
    p = i;
    break;
   }
  }
  return (long)(val*Math.pow(10,p));
 }

}

得点は181.20/250、中央値は約195点。方針を立てるのは容易でしたが、とんでもない勘違いで、大幅にタイムロスしてしまいました。

TopCoder SRM249 Div2 250Pts

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

チャットの会話を受け取った。会話の1要素は1行に対応する。nameという人が何回発言したかを知りたい。このために、nameで会話が始まり、直後にコロンが来た回数を数える。この比較は大文字と小文字を区別するものとする。

私の解答はこちら。

public class ChatTranscript {
 public int howMany(String[] transcript, String name) {
  int cnt = 0;
  // コロンで会話のテキストを区切って、先頭の要素とnameを比較する
  for( int i=0 ; i<transcript.length ; i++ ){
   if( transcript[i].contains(":") == false) continue;
   String[] sp = transcript[i].split(":");
   if( sp.length>0 && sp[0].equals(name) ) cnt++;
  }
  return cnt;
 }
}

得点は約85点。splitした後のif文でsp!=nullなどと書いていたのですが、提出までできてもシステムテストで落とされること数回。ようやく解答にたどりついたけど、何がダメなのか...

2011年9月19日月曜日

Javaのthreadの呼び出し方2

複数のスレッドが動いているときに、1つのスレッドがある変数Aをいじっている最中に、スレッドが切り替わって別のスレッドからAを書き換えるようなことが起きると不便なことがある。勝手にスレッドは動作するため、スレッドを制御する方法としてsynchronizedという修飾子を用いた、排他制御の仕組みが用意されている。排他制御はその名の通り、スレッドが実行している間、synchronized修飾子がかかっている箇所にロックをかけて、他のスレッドはロックがかかっているうちはアクセスができないようにすることである。

以下の例では、複数のスレッドが、計算を繰り返し、その結果をBadのvalueに記録するというものである。スレッド1が1を足して、スレッド1が抜ける前にスレッド2が1を足すということになると、エラーで停止してしまう。排他制御を行わないと、スレッド1がadderを実行している最中に、スレッド2がadderを実行してしまうのである。

BadTest.javaの中身

public class BadTest extends Thread{
 Bad test;
 public BadTest(Bad bd){
  this.test = bd;
 }
 public void run(){
  for( int i=0 ; i<10 ; i++ ){
   test.adder(1);
  }
 }
 public static void main(String[] args){
  Bad bd = new Bad();
  new BadTest(bd).start();
  new BadTest(bd).start();
 }
}

Bad.javaの中身

public class Bad{
 private int value = 0;
 public void adder(int v){
  int tmpValue = value;
  System.out.println(Thread.currentThread() + " is at adder");
  value += v;
  if( tmpValue + v != value ){ // 単純に足しただけだが...
   System.out.println(Thread.currentThread() + " conflicted!");
   System.exit(-1); // 異常終了
  }
  System.out.println(Thread.currentThread() + " get out of adder");
 }
}

上のコードをコンパイルして実行すると次のようになり、矛盾が発生していることが分かる。

d:\java>javac BadTest.java Bad.java // ファイルをまたいでいるので、まとめてコンパイル
javac BadTest.java Bad.java

d:\java>java BadTest
java BadTest
Thread[Thread-0,5,main] is at adder
Thread[Thread-1,5,main] is at adder
Thread[Thread-0,5,main] get out of adder
Thread[Thread-1,5,main] conflicted! // ここで矛盾
Thread[Thread-0,5,main] is at adder
Thread[Thread-0,5,main] get out of adder

この矛盾を解決するのがsynchronized修飾子である。synchronizedは以下のようにadder関数に修飾するとよい。

public synchronized void adder(int v)

これによって、一つのスレッドがadder関数を実行している間、同じインスタンスを利用する別スレッドからはadder関数が利用できなくなり、矛盾(=conflicted!の表示)は発生しなくなる。また、synchronized修飾子はメソッドにもブロックにもかけられる。ブロックにsynchronized修飾子をつける場合は、ロックをかけるオブジェクトを指定する必要がある。

public void adder(int v){
 synchronized(this){
  ...
 }
}

TopCoder SRM248 Div2 250Pts

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

英語では音節は遮られない音の集まりとゆるやかに定義される。発音された数で音節を定義するということもある。ただ、一般には単語の音節を数えるプログラムを書くのは容易ではない。ここでは、音節を数えるのに次の手続きを踏むものとする。それはA、E、I、O、Uという母音の集まりを1つの音節とし、単語の音節の総数に1つ加えるということである。
母音の集合は子音(母音でない21の文字)、もしくは単語の先頭または最後尾によって区切られる。例えば、FOOBARは2つの音節がある。OO、Aの二つが音節になる。

inputという文字列が引数に与えられたときに、上の音節の数え方で、単語にいくつ音節が含まれているかを返すメソッドを作成せよ。

私の解答はこちら。

public class SyllableCounter {
 public int countSyllables(String word) {
  boolean inVowel = false; // 注目している文字が母音ならtrue
  boolean prev = false; // 直前の文字が母音ならtrue
  int cnt = 0; // 音節の登場回数
  for( int i=0 ; i<word.length() ; i++ ){
   if( word.charAt(i) == 'A' || word.charAt(i) == 'I' ||
    word.charAt(i) == 'U' || word.charAt(i) == 'E' ||
    word.charAt(i) == 'O' ){
    inVowel = true;
   }else{
    inVowel = false;
   }
   if( inVowel == true && prev == false ){
    cnt++; // 新たに母音が現れた
   }
   prev = inVowel; // 注目している文字は注目する文字の直前の文字になる
  }
  return cnt;
 }
}

得点は238.15/250。C言語にはないbooleanが大活躍するプログラムですね。

2011年9月18日日曜日

TopCoder SRM247 Div2 500Pts

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

互いに素な整数から0と1の間の既約分数を作成することができる(つまり無限に分数が存在していることを示している)。それらを表す時は、通常次のように表す。

1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/7 ...

2/4というのは数列中にはないが、これは1/2に約分できるからである。既約分数が与えられたときに、上のような順序の数列の何番目に現れるかということが知りたい。例えば、1/3であれば2というインデックスが知りたい。FracCountという分子と分母の互いに素な整数が与えられたときに、その2数から作られる分数が何番目に現れるかを返すメソッドを作成せよ。

私の解答はこちら。

public class FracCount {
 public int position(int numerator, int denominator) {
  int idx = 0;
  for( int i=2 ; i<=denominator ; i++ ){
   for( int j=1 ; j<i ; j++ ){
    // 最大公約数が1であれば、約分不可なので、初登場の分数になる
    if( gcd(i,j) == 1 ) idx++;
    // 求めている分数が現れた時点で処理は終了
    if( i==denominator && j==numerator)break;
   }
  }
  return idx;
 }
 private int gcd(int a, int b){
     return b == 0 ? a : gcd(b, a % b);
 }
}

得点は419.40/500。500点問題にしては、全体の解答者が50%と高めだったので解いてみたところ、予想よりすんなりと解けました。breakに関連した処理を入れ忘れて再提出したのですけどね。

TopCoder SRM247 Div2 250Pts

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

ユークリッド幾何において、三角形は角度で3種類に分類される。もし、三角形のすべての角が90度以下であれば、鋭角三角形である。もし1つの角が90度を超えていれば鈍角三角形である。もし90度の角があれば直角三角形という。また、3つの整数が与えられたとき、その数で三角形を構成できないこともある。それは1つの辺の長さが他の2辺の長さの和以上に長いときである。端点がくっつけられなくなり、三角形が構成できなくなる。3辺が引数に与えられたときに三角形を構成できなければ"IMPOSSIBLE"、鋭角三角形であれば"ACUTE"、鈍角三角形であれば"OBTUSE"、直角三角形であれば"RIGHT"を返すメソッドを作成せよ。

私の解答はこちら。Noteの項目には判定方法が載っているので、それを活用している。Noteが与えられなければ、余弦定理で3つの角度をすべて求めて判定しようと考えていました。

import java.util.Arrays;

public class TriangleType {
 public String type(int a, int b, int c) {
  int[] array = {a,b,c};
  Arrays.sort(array);
  if( array[0]+array[1] <= array[2] ){
   return "IMPOSSIBLE";
  }else if( array[0]*array[0]+array[1]*array[1] < array[2]*array[2]){
   return "OBTUSE";
  }else if( array[0]*array[0]+array[1]*array[1] > array[2]*array[2] ){
   return "ACUTE";
  }else{
   return "RIGHT";
  }
 }

}

得点は238.84/250なのですが、提出したコードが汚いので、ちょっとだけ改良しました。ソート前のa、b、cだけで可能な限り判別しようとしたのですが、a、b、cをソートした配列だけでコードを書いてみたところ、読みやすいので、それを採用して載せました。途中から判定方法を変えず、一貫性があるから読みやすくなったのだと思います。

2011年9月17日土曜日

TopCoder SRM246 Div2 250Pts

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

新しい計算ソフトウェアの開発をしている。ソフトウェアのテストの段階において、小数点の文字が場合によっては違うというということに気付いた。さらに、テストケースにおいて、役に立たない空白文字が含まれていることもある。そのような数値はフォーマットを統一したい。数値はnumbers[]という文字列型の配列で表されている。空白(アスキーコードで32)をすべて取り除き、数字の桁でない文字は"."に置き換えよ。それ以外は変更を加えてはならない。

なお、numbers[]は少なくとも1つ以上の桁(数値)を持ち、空白でも数字でもない文字は高々1であるものとする。本当はもう少し条件があるのだが、実装上はこれで問題無い。

私の解答はこちら。

public class CalcTest {
 public String[] uniform(String[] numbers) {
  for( int i=0 ; i<numbers.length ; i++ ){
   numbers[i] = numbers[i].replaceAll(" ", ""); // 空白は取り除く
   // 数字でない文字は.に変換。[^0-9]は\\Dに代用可能
   numbers[i] = numbers[i].replaceAll("[^0-9]", "."); 
  }
  return numbers;
 }
}

得点は242.70/250、中央値は約226点。否定の正規表現を調べながら解きました。Javaの利用者はこのような正規表現による置換を利用して解答をしている人がちらほらといました。

2011年9月15日木曜日

TopCoder SRM245 Div2 250Pts

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

ストレートの数に関するトランプゲームで遊んでいる。値が連続したカードの集合が手の強さを決める。hand[]という整数型配列のi番目の値が手の中のiという値の数を表している。長さkのストレートの数を返せ。

例えば、hand[] = { 0, 3, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0 }という手が与えられると、k=2のストレートの数(強さ)は5になる。これは2のカードと3のカードの組が3通り、3のカードと4のカードの組が2通りあるので、長さ2のストレートの数は3+2=5になるわけである。

私の解答はこちら。

public class Straights {
 public int howMany(int[] hand, int k) {
  int cnt = 0;
  for( int i=0 ; i<hand.length-k+1 ; i++ ){
   int perm = hand[i];
   for( int j=1 ; j<k ; j++ ){
    perm *= hand[i+j];
   }
   cnt += perm;
  }
  return cnt;
 }
}

得点は229.00/250、中央値は約190点。英語の読解と実装に同じぐらいの時間かかったかな?IndexOutOfBoundsExceptionにだけ注意しましょう(コンパイル後のテストでhand[i+j]で何度か例外を投げられてしまった)。

2011年9月14日水曜日

Javaのthreadの呼び出し方1

Javaのスレッドの基本的な呼び出し方法についてのまとめ。スレッドというのは複数の動作を平行して行うようにするための仕組みである。呼び出し方は大きく2種類ある。

  1. Threadクラスの拡張
  2. Runnableインタフェースの実装

スレッドというのは、特に指定がないと実行されるタイミングを制御することはできない(synchronizedなどを付けない限り)。例えば、Threadクラスを拡張して作成した次のスレッドを含むプログラムを実行すると、mainと書かれた行とrunと書かれた行はランダムに現れることが確認できる。runとmainが交互に現れることや、runが先に10行現れてmainが10行現れるといったことには必ずしもならない。

class countTen1 extends Thread{
 public static void main(String[] args){
  countTen1 ct = new countTen1(); // スレッドを実行するインスタンスを作成
  ct.start(); // スレッドの実行開始
  for( int i=0 ; i<10 ; i++ ){
   System.out.println("main i = " + i);
  }
 }
 public void run(){
  for( int i=0 ; i<10 ; i++ ){
   System.out.println("run i = " + i);
  }
 }
}

参考までに、手持ちの環境で実行した結果の例は次の通り。最後にmainとrunが連続で発生しており、規則性がないということが分かる。

d:\java>java countTen1
java countTen1
main i = 0
run i = 0
main i = 1
run i = 1
main i = 2
run i = 2
main i = 3
run i = 3
main i = 4
run i = 4
main i = 5
run i = 5
main i = 6
run i = 6
main i = 7
run i = 7
main i = 8
main i = 9
run i = 8
run i = 9

スレッドの実行はスレッドクラスのインスタンスが持つstartメソッドで開始する。また、スレッドの実行内容はrunメソッドに記述する。このとき、呼び出し方は必ずpublic void run()になる。

次にRunnableインタフェースを実装するスレッドの作成方法を示す。上のスレッドを拡張した場合と同じように動作するプログラムである。

class countTen2 implements Runnable{
 public static void main(String[] args){
  countTen2 ct = new countTen2();
  // スレッドインスタンスの生成時にRunnableを実装したインスタンスを渡す
  Thread t = new Thread(ct);
  t.start(); // スレッドの実行開始
  for( int i=0 ; i<10 ; i++ ){
   System.out.println("main i = " + i);
  }
 }
 public void run(){
  for( int i=0 ; i<10 ; i++ ){
   System.out.println("run i = " + i);
  }
 }
}

特徴は、Runnableインタフェースを実装したクラスはスレッドクラスではないので、スレッドクラスのインスタンスを作成するときに引数にクラスを入れてしまうということである。

2種類のスレッドの呼び出し方の使い分け方は、クラスの拡張を繰り返して作成された下の階層に属するようなクラスはRunnableを利用し、手軽にスレッドを利用したいのであれば、Threadを拡張して利用するということになる。

TopCoder SRM231 Div2 450Pts

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

多くの画像編集プログラムでは、二つの画像を縫い合わせて大きな画像を作るということができる。この問題では、二つの画像を表す文字列が与えられる。文字列はビットマップ(非圧縮画像ですね)を表しており、文字列のi番目の要素の値jというのは、画像においてはi行j列の色を表している。二つのイメージを縫い合わせることを行え。この問題では画像A[]を画像B[]の左に置き、Aの右側とBの左側を重ねる。明らかな人工物であることを防ぐために、縫い合わせた領域はAからBに向けて徐々に色が混ざるようにしたい。重なっている領域の左からi番目(i=1から始まるとする)の値は次式のようになる。

((overlap+1-i)*a+(i*b))/(overlap+1)

ここで、aとbはそれぞれAとBの画素値である。overlapは重ねた画素数である。したがって、重なっている領域の一番左の画素値は次のようになる。

(overlap*a+b)/(overlap+1).

なお、どの場合でも値は最も近い整数値に変換せよ(四捨五入せよ)。画素値は文字のASCIIコードの値で与えられる。

私の解答はこちら。

public class Stitch {
 public String[] stitch(String[] A, String[] B, int overlap) {
  String[] blended = new String[A.length];
  for( int i=0 ; i<A.length ; i++ ){
   blended[i] = A[i].substring(0, A[i].length()-overlap);
   for( int j=1 ; j<=overlap ; j++ ){
    double val = ((overlap+1.0-j)*A[i].charAt(A[i].length()-overlap+j-1)+j*B[i].charAt(j-1))
      /(overlap+1);
    char cval = (char)Math.round(val);
    blended[i] += cval;
   }
   blended[i] += B[i].substring(overlap);
  }
  return blended;
 }

}

2011年9月13日火曜日

TopCoder SRM244 Div2 400Pts

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

典型的な電話機の番号の配列は次の通りである。

123
456
789
*0#

指の動きの量を二つのボタンのマンハッタン距離で定義する。電話番号を表す文字列が与えられたときに、電話番号を押すのに必要な指の動きの最小値を返せ。なお、指の初期位置は5に設定されているものとする。

私の解答はこちら。

public class PhonePad {
 public int fingerMovement(String phoneNumber) {
  // 2次元配列の座標で番号を表現
  String[][] pos = {{"1","2","3"},{"4","5","6"},{"7","8","9"},{"*","0","#"}};
  // 1文字ずつに分解
  String[] pushedArray = phoneNumber.split("");
  // 直前の指の座標、yが縦方向、xが横方向(画像処理的に)
  int x = 1;
  int y = 1;
  int totalMove = 0; // 指の動いた距離の合計
  for( int i=0 ; i<pushedArray.length ; i++ ){
   String current = pushedArray[i];
   for( int j=0 ; j<pos.length ; j++ ){
    for( int k=0 ; k<pos[j].length ; k++ ){
     if( pos[j][k].equals(current)){
      int aMove = Math.abs(y-j) + Math.abs(x-k);
      totalMove += aMove;
      y = j;
      x = k;
     }
    }
   }
  }
  return totalMove;
 }

}

得点は328.80/400、提出者の正解率は約90%。マンハッタン距離をどうやって表すかということがポイントで、2次元配列にすれば、インデックスの差がそのまま距離にできるというところがポイントだと思いました。レベル2の問題にしては簡単だったと思います。

2011年9月11日日曜日

TopCoder SRM243 Div2 250Pts

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

あなたはいくつかアルゴリズムのテストをしており、一番早いものを見つけたいと思っている。アルゴリズムの計算量というのは、三つからなる。constant、power、logPowerである。これらは配列で与えられており、i番目のアルゴリズムは、次式で与えられる。

constant[i]*N^power[i]*log(N)^logPower[i]

上の3つの配列と、サイズを表すNが与えられたときに最も速い(計算量が少ない)アルゴリズムのインデックスを返せ(先頭は0から始まるものとして)。タイのものがある場合には、インデックスが最も小さいものを返せ。

私の解答はこちら。

public class ComputationalComplexity {
 public int fastestAlgo(int[] constant, int[] power, int[] logPower, int N) {
  // こういう風に定義するのもあり。こちらを利用する場合、int i=0からループを開始することになる。
  // 解答の美しさを考慮すると、minはコメントにあるものの方が好きです。
  // double min = Double.POSITIVE_INFINITY;
  double min = constant[0]*Math.pow(N, power[0])*Math.pow(Math.log(N),logPower[0]);
  int idx = 0;
  for( int i=1 ; i<constant.length ; i++ ){
   double ith = constant[i]*Math.pow(N, power[i])*Math.pow(Math.log(N),logPower[i]);
   if( ith < min ){
    idx = i;
    min = ith;
   }
  }
  return idx;
 }
}

得点は205.78/250。数式をコードに落とすのに間違いがあり、解答にやや時間がかかってしまった。次の問題はSRM182 Div2 300Ptsと同じなので省略。

TopCoder SRM242 Div2 250Pts

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

ゲームで二つのチームにメンバーを分けるということをしたい。分けるためにまずはキャプテンを決める。そして交互にチームを作るためにプレーヤーを選択する。それぞれのターンでは一人ずつメンバーを選ぶ。キャプテンは強いメンバーが欲しいので、残っている中でベストなプレーヤーを選ぶ。プレーヤの強さはstrengths[]という配列で与えられており、値が大きいほど良いプレーヤーである。全員選び終えたところで、チームの強さというのはプレーヤーの強さの総和で計算される。二つのチームの強さの絶対値を返せ。

人数が奇数の時は先に選ぶキャプテンがとることになるため、2チームの人数は同じとは限らないことに注意。

私の解答はこちら。

import java.util.*;

public class TeamSplit {
 public int difference(int[] strengths) {
  int diff = 0;
  Arrays.sort(strengths);
  for( int i=0 ; i<strengths.length ; i++ ){
   if( i % 2 == 0 ){
    diff += strengths[strengths.length-i-1];
   }else{
    diff -= strengths[strengths.length-i-1];
   }
  }
  return diff;
 }
}

得点は236.44/250。ソートを楽にする方法がArrays.sortだった。最初から逆順から並べるにはコンパレータ使わないとダメかな?

TopCoder SRM241 Div2 250Pts

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

ブラックジャックでは、プレーヤーはディーラーよりも数字が大きいか、もしくはディーラーがバースト(21を超える)し、プレーヤーが21を超えない場合、掛け金と合わせて、同じ額を余分に受け取ることができる。もし、プレーヤーが21以下で、ディーラーと同じ数になったらプッシュという状態になり。掛け金はそのままになる(プラスマイナス0の状態)。もしプレーヤーがディーラーの数より小さいか、21を超えてしまった場合、掛け金を失う。

ブラックジャックというのは21ポイントの状態で、すべての手を負かす。この場合、プレーヤーは掛け金の1.5倍を得ることができる。もし、プレーヤーもディーラーもブラックジャックであれば、プッシュになる。もし、ディーラーがブラックジャックで、プレーヤーがブラックジャックでないものの21であった場合は、ディーラーの勝ちで、プレーヤーは掛け金を失う。

プレーヤーの掛け金betと、ディーラーのスコアdealer、プレーヤーのスコアplayerと、2人がブラックジャックかそうでないかを表す状態(dealerBlackjack、blackjack)が与えられている。ブラックジャックである状態は1、そうでない状態は0で表す。このとき、プレーヤがの収支を返せ。勝てばプラス、負ければマイナス、プッシュは0になる。

私の解答はこちら。

public class BlackjackWinner {
 public int winnings(int bet, int dealer, int dealerBlackjack, int player, int blackjack) {
  if( dealerBlackjack == 0 && blackjack == 1){
   // プレーヤーのみブラックジャック
   return (int)(bet*1.5); // 掛け金は常に偶数
  }else if( dealerBlackjack == 1 && blackjack == 1){
   return 0; // 両者ブラックジャック(プッシュになる)
  }else if( dealerBlackjack == 1 && blackjack == 0 ){
   return -bet; // ディーラーのみブラックジャック
  }else{
   // どちらもブラックジャックではない
   if( player > 21 ){ // プレーヤーがバースト
    return -bet;
   }else if( player <= 21 && dealer > 21 ){
    return bet; // ディーラーがバースト
   }else if( player <= 21 && dealer <= 21 ){
    // どちらもバーストしてない
    if( player > dealer  ) return bet;
    if( player == dealer ) return 0;
    if( player < dealer  ) return -bet;
   }
  }
  return 0;
 }
}

得点は183.25/250。場合分けが細かいですね。

TopCoder SRM240 Div2 250Pts

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

ピーターは難しい単語の発音に難がある。特に子音が3つ以上連続する単語が発音できない(streetとか)。さらに、異なる母音が2つ以上続いている単語も発音できない(goalとか)。同じ母音が2つ続いているものについては発音できる(needとか)。

母音はa、i、u、e、oであり、その他は子音である。単語の集まりwords[]が与えられる。もしピーターがwords[]をすべて発音できるのであれば空文字を返せ。そうでなければ、発音できないもののうち、最初に現れたものを返せ。

私の解答はこちら。

public class Pronunciation {
 public String canPronounce(String[] words) {
  for( int i=0 ; i<words.length ; i++ ){
   int consonants = 0;
   int vowel = 0;
   char prevAlphabet = '\0';
   for( int j=0 ; j<words[i].length() ; j++ ){
    // 母音の処理
    char currentAlphabet = words[i].toLowerCase().charAt(j);
    if( currentAlphabet == 'a' ||
     currentAlphabet == 'i' ||
     currentAlphabet == 'u' ||
     currentAlphabet == 'e' ||
     currentAlphabet == 'o' ){
     consonants = 0;
     vowel++;
     if( vowel >= 2 && prevAlphabet != currentAlphabet ){
      return words[i];
     }
     prevAlphabet = currentAlphabet;
    }else{ // 子音の処理
     consonants++;
     vowel = 0;
     if( consonants >= 3 ){
      return words[i];
     }
    }
   }
  }
  return "";
 }

}

得点は197.52/250、中央値は82点。母音と子音に分けて処理を書くことでスムーズに実装できた。

TopCoder SRM239 Div2 300Pts

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

家族でバーベキューをし、肉は皆に1切れずつということになっていた。肉を食べる前にサッカーをしてバーベキューをする場所に戻ってきたところ、犬が肉を1切れ食べてしまっていた。そこで、長兄は投票をして、1人犬を散歩に連れて遊ばせることにし、その他の人は肉を食べるということにした。家族はn人で0からn-1の添え字で一人一人を表す。voter[]は投票者を表す配列であり、値は家族のメンバーを表す0からn-1の数字が入っている。excluded[]はバーベキューから追い出したい人を表す。こちらも家族のメンバーを表す0からn-1の数字が入っている。

バーベキューからの追い出すルールは、次のルールに従う。

  1. 最多得票者が追い出される
  2. 最多得票者数が複数いたら、最多得票者の中で最も多く投票した人が追い出される
  3. 最多投票者が複数いたら、添え字の小さい方が追い出される

このとき、追い出される人を表す添え字を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.*;
import java.lang.*;

public class Barbecue {
 public int eliminate(int n, int[] voter, int[] excluded) {
  int[] nVote = new int[n];
  int[] nVoted = new int[n];
  for( int i=0 ; i<voter.length ; i++ ){
   nVote[voter[i]]++;
   nVoted[excluded[i]]++;
  }
  int maxVoted = maxArray(nVoted);
  //int maxVoter = maxArray(nVote);
  ArrayList<Integer> maxVotedList = new ArrayList();
  ArrayList<Integer> maxVoterList = new ArrayList();
  for( int i=0 ; i<n ; i++ ){
   if( nVoted[i] == maxVoted ){
    maxVotedList.add(i);
   }
  }
  System.out.println("-------");
  for( int i=0 ; i<n ; i++ ){
   System.out.println(nVote[i]);
  }

  // 最多得票者
  if( maxVotedList.size() == 1) return maxVotedList.get(0);
  // 得票最多数がタイだった場合
  // 該当者の中で投票数が最多だった人が選ばれる
  // それでも同じなら先に出てきた人。
  Collections.sort(maxVotedList); // ソートしておく
  //ArrayList<Integer> maxVoterVotedList = new ArrayList();
  int[] candidate = new int[maxVotedList.size()];
  int idx = 0;
  for( Integer i : maxVotedList ){ // 得票を得た人を対象に出現回数を集計
   candidate[idx] = nVote[i.intValue()];
   idx++;
  }
  int maxVoter = maxArray(candidate); // 最多得票数
  boolean flg = false;
  int res = 0;
  for( int i=0 ; i<candidate.length ; i++ ){
   if( candidate[i] == maxVoter ){
    maxVoterList.add(i); // 一番投票した人一覧作成
    if( flg == false ){
     flg = true;
     res = maxVotedList.get(i);
    }
   }
  }
  return res;
 }
 private int maxArray(int a[]){
  int max = -1;
  for( int i=0 ; i<a.length ; i++ ){
   max = Math.max(max,a[i]);
  }
  return max;
 }
}

得点は90/300。結局2時間かけて解きました。正解率は私の予想よりも高く、約72%もあるようです。

2011年9月6日火曜日

Rで実験計画法 前編

Tokyo.R#16にて、実験計画法の話題について話をしてきました。ソフトウェアテストに使われる直交表について学ぶついでに、本や資料をいくつか読んだので、それらをまとめました。

2011年9月4日日曜日

Javaの私的まとめ18

Javaのお勉強その18

  1. NavigableSetとTreeSet

    TreeSetはNavigableSetを実装したものである。TreeSetに格納されるデータは自然順序付けによってソートされている。順序付けのないものにはComparableを実装するか、Comparatorを渡して順序付ける。

  2. NavigableMapとTreeMap

    TreeMapはNavigableMapを実装したものである。TreeMapに格納されるデータは自然順序付けによってソートされている。順序付けのないものにはComparableを実装するか、Comparatorを渡して順序付ける。

  3. ジェネリックス

    以下のコードはすべてコンパイルはできる。

    ArrayList a1 = new ArrayList();
    ArrayList a2 = new ArrayList();
    ArrayList a3 = new ArrayList();
    ArrayList a4 = new ArrayList();
    

    a1は古い書き方、リストに入れるときの型に注意が必要。a2は現在のJavaの書き方。安全。a3は型が定まらないので、String str = (String)a3.get(0);のようなキャストが必要になる。getで戻す型はObjectである。a4はStringとそのサブクラスしか入れられない。

    関数の引数にリストを渡す場合、int method(List list){ ... }のような書き方がある。

    class Super{ ... }
    class Sub extends Super { ... }

    に対して、以下のようにすると、a1にはSuper、Subのどちらのオブジェクトも格納できる。

    ArrayList<super> a1 = new ArrayList<super>;
    Super[] a1 = new Sub[10]; // エラーにならない
    ArrayList<super> a1 = new ArrayList<sub>(); // エラーになる
    // Superかそのサブクラスのコレクションを参照する変数
    // 要素の追加ができない
    ArrayList<? extends Super> a2 = new AraryList<sub>(); // OK
    // Subかそのスーパークラスのコレクションを参照する変数
    // 要素の追加はできる
    ArrayList<? super Sub> a3 = new ArrayList<super>(); // OK
    

Javaの私的まとめ17

Javaのお勉強その17

  1. コンパレータ

    コレクションや配列を自分が決めた順序でソートしたい場合には、Comparatorを実装するクラスを書く。C言語で言うところのqsort関数に渡す関数ポインタみたいなもの。コンパレータは次の形式である。

    public int compare(値1,値2)

    値1が値2より小さい場合は負、等しい場合は0、値1が値2より大きい場合は正の整数を戻すように定義する。

    自分で順序を決めたいものの型をXとするとき、コンパレータは次のようになる。

    class MyComparator implements Comparetor{
     public int compare(X x1, X x2){
      return (x1,x2の比較結果);
     }
    }

    例えば、数値を絶対値の小さい順に並べるコンパレータは次のようになる。このようなコンパレータをArrays.sortの引数や、Collections.sortの引数に与えることで、自分の基準でソートができる。

    class MyComparator implements Comparetor{
     public int compare(Integer x1, Integer x2){
      return Math.abs(x1)-Math.abs(x2);
     }
    }
  2. java.util.comparable

    Comparatorとの違いは、自分自身と引数に与えられた値を比較するという点である。次のような形をしており、引数は1つだけになる。

    public int compareTo(値)

    Xというクラスに自分で定義した順序を与える場合、次のように書く。

    class X implements Comparable{
     public int compareTo(X x1){
      return (自身とx1との比較結果);
     }
    }

    Comparableを実装しているクラスにはラッパークラス、String、DateCalenderなどがある。

    Comparableでは1つのクラスに1つの順序しか与えられないが、Comparatorでは、比較するクラスから独立しており、必要なだけ順序付けを定義することができる。

    Comparableを実装した場合、Arrays.sortなどの第2引数の指定は必要なくなる。

  3. 反復子

    コレクションの要素の繰り返しを扱うためのインタフェース。IteratorやIteratorを実装したクラス、オブジェクトを反復子という。List、Setにはiterator()というIteratorを返すメソッドがある。

    Listの主なメソッド
    boolean hasext() さらに要素がある場合にtrueを返す
    next() 反復子が指している要素を返し、反復子に次の要素を指すようにさせる。
    void remove() 反復子によって最後に返された要素を削除する

    反復子のサンプルプログラム。要素がそのままの順で1行につき1単語ずつ出力される。

    import java.util.*;
    class ite{
     public static void main(String[] args){
      List list = Arrays.asList("This","is","a","pen");
      Iterator it = list.iterator(); // 反復子の設定
      while(it.hasNext()){ // リストに次の要素があるうちは
       System.out.println(it.next()); // 注目している値を表示して、次を指すようにせよ。
      }
     }
    }
  4. Hash関連

    HashMap、Hashtableでは、ハッシュと呼ばれる、値を識別キーに対応させる方法を使う。検索の高速化が目的である。

    キーはObjectのメソッドであるequalsとhashCodeを使う。hashCodeはハッシュコードというint型の値を返すメソッドである。これらを正しく実装しないクラスのオブジェクトはHashtableなどのキーにすることはできない。

    hashCodeはequalsで等しいとされるオブジェクトは同じハッシュコードを戻すようにしなければならない。等しくない場合は任意であるが、異なるハッシュコードにする方が検索等が速くなる。

    import java.util.*;
    class A{
        int weight;
        A(int w){ weight = w; }
        public boolean equals(Object obj){
    	if( (obj instanceof A) && weight == ((A)obj).weight ){
    	    return true;
    	}else{
    	    return false;
    	}
        }
        public int hashCode(){
    	return weight % 10;
        }
    }
    
    class hashtest{
        public static void main(String[] args){
    	Hashtable ht =
    	    new Hashtable();
    	ht.put(new A(3),"hello");
    	ht.put(new A(5),"world");
    	System.out.println(ht.get(new A(5)));
    	System.out.println(ht.get(new A(2)));
        }
    }

    実行結果は次の通り。2に対応するオブジェクトがないので、nullが返ってくる。

    world
    null

Javaの私的まとめ16

Javaのお勉強その16

  1. コレクション

    コレクションクラスのオブジェクトの作成方法は次の通り。昔は<Integer>は不要であったが、今は型を明示するのが一般的。

    ArrayList<Integer> list = new ArrayList<Integer>;
    Listの主なメソッド
    add(値) 値を要素に追加
    add(インデックス,値) リストの指定したインデックスの位置に値を追加
    contains(値) 値がリスト中にあればtrueが返される
    get(インデックス) リストのインデックスの位置にある値を返す
    indexOf(値) 指定した値がある位置を返す(一番最初に現れるものに限られるが)
    remove(インデックス) 指定したインデックスを削除
    remove(値) 指定した値を持つ要素を削除(先頭のみ)
    toArray() リストの全要素を格納する配列を返す(Object[]型で)
    iterator() イレテータを返す
    Mapの主なメソッド
    containsKey(値) Map中にキーがあればtrue
    containsValue(値) Map中に値があればtrue
    get(キー) キーで指定される値を戻す
    put(キー、値) Mapの要素を追加
    remove(キー) キーで指定される要素を破棄
    Set keySet() マップに格納されているキーの一覧を得る
    Setの主なメソッド
    add(値) 値をSetの要素に追加
    contains(値) Set中に値があればtrue
    remove(値) 指定した値を持つ要素を削除
    toArray() すべての値を持つ配列を返す(Object[]型で)
    iterator() イテレータを作成する
    Set keySet() マップに格納されているキーの一覧を得る
    List、Map、Hashの共通メソッド
    clear() 全要素の削除
    isEmpty() 要素が空の場合にtrueを返す
    size() 要素数を返す
    Queueの主なメソッド
    add(値) 値をキューに入れる
    offer(値) 値をキューに入れる。addとの違いはaddは入れられない場合に例外を投げるのに対し、offerはfalseを返すだけである。
    peek() キューの先頭の値を返す。キューが空だとnullが返される。
    poll() キューの先頭の値を返し、先頭の要素を削除する。キューが空だとnullが返される。
  2. CollectionsとArrays
    Collectionsの主なメソッド(全部staticメソッドである)
    binarySearch(リスト,値) リストを2分探索し、値のインデックスを返す
    binarySearch(リスト,値,コンパレータ) リストを2分探索し、値のインデックスを返す。要素の比較はコンパレータに従う。
    reverse() リストを反転させる
    shuffle() リストをランダムに並び変える
    sort(リスト) リストを型にとって自然な順序で昇順にソート、文字列なら辞書順、数値は昇順。
    sort(リスト,コンパレータ) リストをコンパレータに従ってソート
    emptyList()、emptyMap()、emptyHash() 空のリスト、マップ、ハッシュの生成

    java.util.Arraysは配列を扱うためのstaticメソッドを持っている。

    Ararysの主なメソッド
    asList(要素の型... a) リストを生成する。aは可変長引数リストや配列を想定している。
    binarySearch(配列,値) 配列を2分探索し、値の見つかった位置を返す。
    binarySearch(配列,値,コンパレータ) 配列をコンパレータに従って二分探索し、値の見つかった位置を返す。
    equals(配列1、配列2) 二つの配列のデータが一致するとtrueが返される。
    sort(配列) 配列を昇順でソート。
    sort(配列、コンパレータ) 配列をコンパレータに従ってソート。
    toString() 配列の内容の文字列表現を返す。

    ここまでの二分探索メソッドで見つけようとした値がコレクションの中にない場合は負数が返される(-1とも限らない)


Javaの私的まとめ15

Javaのお勉強その15

  1. シリアライズ・デシリアライズ

    オブジェクトのデータを書き込み、読み込みすることをそれぞれシリアライズ、デシリアライズという。

    シリアライズできるクラスはインタフェースSerializeableを実装したものである。インタフェースはメンバを持たないので、特別な実装は不要。

    aというファイルにあるクラスAAのオブジェクトAを書き込む方法はつぎのようになる。

    FileOutputStream fos = new FileOutputStream("a");
    ObjectOutputStream oos = new ObjectOutputStream(fos);
    oos.writeObject(A);
    oos.close();
    

    逆にファイルを読み込む方法は次のようになる。aというファイルからオブジェクトを読み込む。

    FileInputStream fis = new FileInputStream("a");
    ObjectInputStream ois = new ObjectInputtStream(fis);
    AA aa = (AA)ois.readObject(); // Object型で読み込まれるのでキャストする
    ois.close();

    transientなフィールド、staticなフィールドはシリアライズされない。

    DataInputStreamのreadInt、DataOutputStreamのwriteIntなどでも特定の型のデータの読み書きができる。

    スーパークラスがSelializableを実装している場合、そのサブクラスもSelializableを実装していることになる。サブクラスのオブジェクトのシリアライズ・デシリアライズはスーパークラスの部分も対象とする。

    スーパークラスがSerializeを実装していない場合、サブクラスのシリアライズ・デシリアライズではスーパークラスのシリアライズ・デシリアライズは行われない。オブジェクトのスーパークラス部分はスーパークラスの引数を取らないコンストラクタで初期化される。

  2. コンソール

    コンソールはGUIを使わない入出力を簡単・安全にする。次のようにするとConsoleオブジェクトが得られる。

    Console c = system.console();
    printfの書式(フラグ)
    String readLine() キーボードから1行テキストを読みこむ
    String readLine(String format,Object...args) 書式設定したうえで1行読み込む
    char[] readPassword エコーを無効にしたコンソールから1行テキストを読み込む
    char[] readPassword(String fmt,Object ...args) 書式設定したうえで、エコーを無効にしたコンソールから1行テキストを読み込む
    Console format(String fmt,Object... args) 書式付文字列をコンソールに書き込む
    void flush() コンソールをフラッシュして出力を直ちに書き込む
  3. コレクション

    コレクションとは、複数のオブジェクトを格納しておくクラス、インタフェースのことである。java.utilパッケージに属する。

    主なインタフェースの種類
    Collection コレクションのルート。順序も重複も規定されていない
    List 順序づけられたコレクション。任意の位置に対する要素の挿入・削除が速い
    Map キーとデータを対応させたコレクション。キーはユニークになる。
    Set 重複のないコレクション、数学の集合に相当。
    Queue キュー(FIFO)
    主なコレクションクラス
    ArrayList 要素を変えられる配列のようなもの。スレッドセーフでないがVectorより高速。(Listの実装)
    Vector 要素を変えられる配列のようなもの。スレッドセーフ。(Listの実装)
    HashMap ハッシュを使ったマップ。nullが利用できる。(Mapの実装)
    Hashtable ハッシュを使ったマップでnullが使えない。スレッドセーフ。(Mapの実装)
    HashSet ハッシュを使ったセット(Setの実装)

2011年9月2日金曜日

Javaの私的まとめ14

Javaのお勉強その14

  1. 表示
    String a = "small";
    String A = "large";
    System.out.printf("a = %2$s, A = %1$s",A,a);
    とすると、a = small, A = largeと表示される。番号$は省略できるが、その場合は埋め込む文字の順序は変更できない。後ろにつけたものから順に埋められる。

    printfの書式をいくつか示す。

    printfの書式(フラグ)
    - 左揃えにする
    + 符号をつける
    0 空きを0で埋める
    , コンマ区切りを使う
    ( 負の値をかっこで囲む
  2. File

    java.io.Fileはファイルやディレクトリ(!)を表すクラスである。

    Fileオブジェクトはいくつかのコンストラクタを持つ。

    File(String name)
    File(String dir, String name)
    File(File dir, String name)

    Fileオブジェクトを生成してもファイルはすぐに作成できない。createNewFile()でファイルを作成する。ただし、ファイルが生成できない場合はjava.io.IOExceptionがスローされる。

  3. ReaderとWriter

    java.io.Readerとjava.io.Writerは文字の入出力に使うためのクラスである。

    FileReader/Writerはファイルの入出力に使う。

    BufferedReader/Writerはバッファを使い、効率よく入出力を行う。BufferedReader/WriterはReader、Writer(入出力のためのクラス)から生成できる。

    Print.Writerは文字・文字列の入出力に使う。System.outのクラスである。File、Writer、Stringなどから生成できる。

    Reader、Writerのメソッド(失敗時にIOExceptionが投げられる)
    int read() 文字を1文字読みだして戻す
    void write(char c) cを書き込む
    void write(String s) sを書き込む
    void flush() フラッシュする
    void close() 閉じる
    閉じる

    BufferedReaderはString readLine()という文字列を1行読み込んで返すメソッドを持っている。

    BufferedWriterはvoid newLine()という文字列を1行書き込むメソッドを持っている。

    import java.io.*;
    class file{
     // IOExceptionを投げると書かないとコンパイルエラーになるよ。
     // readLineメソッドなどは例外を投げる可能性があるので。
     public static void main(String[] args)throws IOException{
      File f = new File("test.txt");
      PrintWriter pw = new PrintWriter(f);
      pw.write('x'); // 書き込み
      pw.println("hello"); // これも書き込み
      pw.flush();
      pw.close();
      // ReaderからBufferedReaderを生成する。
      BufferedReader br = new BufferedReader(new FileReader(f));
      System.out.println(br.readLine());
     }
    }

8月の学習記録

2011年8月に学習した本一覧。Javaの試験勉強と統計勉強会のスライド作りであまり進んでないですが...

よくわかる実験計画法(pp.136~読了)
バランスが取れている実験(ある水準に注目したときに、他の因子は水準数が均等に登場する)しか登場しないのだけど、直交表ってまさにその性質を満たしていて、意外と使える範囲は広いのだなと思いました。次の実験計画法関連の本を読むとしたら、田口玄一氏の実験計画法あたりかな?高いけど...
Java言語プログラミングレッスン下(pp.1~142)
結構読みやすい。Javaはもう少し手を動かして理解したい。
遺伝的アルゴリズム(pp.1~30)(著:坂和)
遺伝的アルゴリズムはナップサック問題のように、組み合わせが指数的に増える問題を近似的に解くのに使える。テキストを通じて、突然変異や交差といった用語がようやく理解できた。演習がもう少しあればいうことがないのだが。
わかりやすいパターン認識(pp.1~20)
まだパーセプトロンの初歩的な話だけど、もう少し熟読してから先に進みたい。

2011年8月31日水曜日

Javaの私的まとめ13

Javaのお勉強その13

  1. クラス2

    メソッド内でクラスとオブジェクトの生成を同時に行う。以下の例ではインタフェースをmain内で実装し、オブジェクトを作成している。引数にnewを渡して関数を呼ぶことも無名クラスを利用したことになる。

    interface IF{
     void method();
    }
    
    class mumei{
     public static void main(String[] args){
      IF ifobj = new IF(){
       public void method(){
        System.out.println("Hello,java");
       }
      };
      ifobj.method();
     }
    }
    結果は次の通り。
    Hello,java
  2. Scanner

    java.util.Scannerは入力の読み込みに使われる。

    Scanner sc = new Scanner(入力ファイルパスor入力ストリームor文字列オブジェクト)

    標準入力からの読み込みを行う場合はScannerの引数にSystem.inを与える。

    Scannerには区切りを表す文字(","などのStringまたはPattern)を引数に取り、その結果をScannerに戻すメソッドuseDelimiterというメソッドがある。

    Scannerの検索メソッド
    String findInLine(Pattern p) pで指定されるパターンを検索し、見つけたものを戻す。なければnullを戻す
    String findInLine(Pattern p) pで指定される文字列を検索し、見つけたものを戻す。なければnullを戻す
    boolean hasNext(Pattern p) 次に読み込むべきものがpで指定されるパターンであればtrueを戻す。
    String next(Pattern p) pで指定されるパターンに一致するものを読み込んで戻す。
  3. 正規表現

    正規表現を使うときにはjava.util.regex.*(PatternとMatcher)をimportする必要がある。

    パターンは文字列検索に用いることができる。Patternオブジェクトの作成は次の形式で作成される。Matcherオブジェクトはpで指定した正規表現を検索するためのオブジェクトである。

    Pattern p = Pattern.complile("ABA");
    Matcher m = p.matcher("abcABABAdABA")
    Matcherクラスのメソッドの代表例
    boolean find() 正規表現に一致したものがあればtrueを返す。
    int start() 見つかったパターンの先頭インデックスを返す。
    String group() 見つかったパターンに該当した文字列を返す。
    正規表現の例
    .任意の文字
    \d数字
    \s空白文字
    c?cが1or0回
    \wアルファベット、数字、アンダーバーのいずれか
    c*cが0回以上
    c+cが1回以上

    ScannerクラスのfindInLineによりパターンの検索ができる。

    StringにはString[] split(String s)というメソッドがある。sには正規表現を指定することもできる。

2011年8月29日月曜日

TopCoder SRM222 Div2 250Pts

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

入力の文字列inputが与えられたときに、2回以上同じ文字列が現れる文字列の中で、最長になる文字列を返せ。なお、文字列inputの長さの上限は50であり、文字列に利用可能な文字は小文字、大文字のアルファベットのみとする。

私の解答はこちら。

public class TextCompressor {
 public String longestRepeat(String sourceText) {
  for( int i=sourceText.length()/2 ; i>0 ; i-- ){
   for( int j=0 ; j<sourceText.length()-i ; j++ ){
    String tar = sourceText.substring(j, j+i);
    if( sourceText.substring(j+i).contains(tar) ) return tar;
   }
  }
  return "";
 }
}

実はSRM198の問題とコードはほとんど同じ。返す値が最長の文字列そのものか、その長さなのかという違いぐらいしかないというオチ。

TopCoder SRM198 Div2 250Pts

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

入力の文字列inputが与えられたときに、2回以上同じ文字列が現れる文字列の中で、最長になる文字列の長さを返せ。なお、文字列inputの長さの上限は50であり、文字列に利用可能な文字は小文字、大文字のアルファベットのみとする。

サンプルとなる解答はこちら。

public class Reppity {
 public int longestRep(String input) {
  for( int i=input.length()/2 ; i>0 ; i-- ){
   for( int j=0 ; j<input.length()-i ; j++ ){
    String tar = input.substring(j, j+i);
    if( input.substring(j+i).contains(tar) ) return i;
   }
  }
 return 0;
 }
}

長い方の文字列から探索していくのがキモ。気持ちのよい解き方が思い浮かばず解くのを断念してしまいました。解答を見れば納得できるのですがね...

フォロワー

ブログ アーカイブ

ページビューの合計