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。英語の説明が難しいので、大分意訳して説明しています。詳細は英語の問題文をご覧ください。

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を探してしまうワタシ。

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回に分けて計算するということだと思います。それ以外は、特に悩まなかったです。

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;
 }

}

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。アルゴリズムは分かっているのに、実装の方法が分からないことで、大幅なタイムロス。イテレータとか仕事で使いませんからとか言ってみる。

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というのが方針。実装するに当たり、空白は飛ばすなど要求と異なる実装をしていたので、かなり時間がかかってしまいました。

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登録 & 問題文は英語)。それでは、問題について説明する。

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

1	0	3	4	1
4	5	8	15	20
1	10	23	46	81
0	11	44	113	240
3	14	69	226	579

一番上の行と、一番左の列を除いて、各数は左、上、左上の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列目に設定してしまえば、簡単な問題に落とし込めると思います。