TopCoder SRM324 Div2 250Pts

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

頭韻とは、二つ以上の連続する単語が同じ文字で始まることをいう（大文字・小文字の区別は無視）。words[]という単語の配列が与えられたとき、それ以上拡張ができないもののみを考慮し、頭韻の数を返すメソッドを作成せよ(要は同じ頭文字で続くものが3つあった場合、2つ連続したものがが2つあると数えないという意味である)。

私の解答はこちら。

public class Alliteration {

 public int count(String[] words) {
  String str = "";
  for( int i=0 ; i<words.length ; i++ ){
   str += words[i].substring(0, 1).toLowerCase();
  }
  int n = 0;
  int cnt = 1;
  char c = str.charAt(0);
  for( int i=1 ; i<str.length() ; i++ ){
   if( str.charAt(i) == c ){
    cnt++;
    if( cnt == 2 ) n++; // 連続で2回続いたらカウント(3回以上は無視)
   }else{
    c = str.charAt(i);
    cnt = 1;
   }
  }
  return n;
 }

}

得点は238.33/250、中央値は約194点。わざわざfor文を2回にしなくても、1回のループで解くことができることには後から気付きましたとさ。

TopCoder SRM323 Div2 250Pts

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

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

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

import java.util.ArrayList;

public class IrreducibleNumber {

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

}

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

TopCoder SRM322 Div2 250Pts

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

問題は整数型の数列a[]が与えられたときに、第n階差数列を返すメソッドを作成せよというものである。

私の解答はこちら。

public class DerivativeSequence {

 public int[] derSeq(int[] a, int n) {
  int[] ret = new int[a.length];
  for( int i=0 ; i<ret.length ; i++ ){
   ret[i] = a[i];
  }
  for( int i=0 ; i<n ; i++ ){
   int[] tmp = new int[ret.length-1];
   for( int j=0 ; j<tmp.length ; j++ ){
    tmp[j] = ret[j+1] - ret[j];
   }
   ret = tmp;
  }
  return ret;
 }

}

得点は244.09/250、中央値は約236点。

TopCoder SRM320 Div2 250Pts

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

文字列はいくつかの同一の文字の最大の集まりから構成されると考えられる。"aaabbaacc"は"aaa","bb","aaa","cc"からなると言える。文字列sが与えられたとき、その文字列のセグメントの長さの平均長を返せ。先ほどの例では(3+2+3+2)/4=2.5である。

私の解答はこちら。

public class StringSegment {

 public double average(String s) {
  int nSeg = 1;
  char c = s.charAt(0);
  for( int i=0 ; i<s.length() ; i++){
   if( s.charAt(i) != c){ // これまでと違う文字なら
    nSeg++; // セグメントは1つ増える
    c = s.charAt(i);
   }
  }
  // 文字列をセグメント数で割れば、1セグメント当たりの長さが求まる
  return (double)s.length()/nSeg;
 }

}

得点は241.02/250、中央値は約233点。実は1つ1つのセグメントの長さに関する情報は不要で、いくつのセグメントがあるかをカウントすればよいというだけの話。

TopCoder SRM319 Div2 250Pts

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

歪対称行列というのはt(M)=-Mを満たすMのことである(tは転置の意)。歪対称行列の性質として、対角成分が0になるということが挙げられる。minChangesというメソッドを含むSkewSymmetricというクラスを作成しよう。メソッドminChangesはMという文字列型の配列を引数に取る。Mの各要素は整数が半角の空白1つで区切られたリストである。Mのi番目の要素のj番目の数字が行列の(i,j)成分を表す。行列Mを歪対称行列に変換するのに最低何回変換を行うかを返すようにメソッドを作成せよ。

私の解答はこちら。

public class SkewSymmetric {

 public int minChanges(String[] M) {
  int nRow = M.length;
  int nCol = M.length;
  int[][] im = new int[nRow][nCol];
  // 行列に整数成分を設定
  for( int i=0 ; i<nRow ; i++ ){
   String[] work = M[i].split(" ");
   for( int j=0 ; j<nCol ; j++ ){
    im[i][j] = Integer.parseInt(work[j]);
   }
  }
  int nChange = 0;
  // 歪行列に変換する必要の有無を判定(上三角成分のみ確認)
  for( int i=0 ; i<nRow ; i++ ){
   for( int j=i ; j<nCol ; j++ ){
    if( i == j ){
     if( im[i][j] != 0) nChange++;
     continue;
    }
    if( im[i][j] != -im[j][i] ) nChange++;
   }
  }
  return nChange;
 }

}

得点は238.22/250、中央値は約169点。入力を数値に変換する手法として、Scannerを利用する手もあるようだ。また、対角成分か否かで成分の変換の必要性を判定しているが、対角成分であるときの処理は不要である。対角成分の判定もim[i][j] != -im[j][i]で調べればよいということである。

TopCoder SRM318 Div2 250Pts

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

Joshはいくつかの1インチの棒を見つけた。彼はこの棒を辺とする長方形を作成し、しかもできるだけ面積を大きくしたいと思っている。ただ、棒をくっつけるのはOKだが、棒を折って短い棒を作ることは認めていない。例えば11本の棒があったとき、2*3の長方形を作成するのに10本の棒を使うが、このとき面積が最大になる。Nという棒の本数が与えられたとき、その本数で作成できる長方形の面積の最大値を求めよ。

私の解答はこちら。

public class BiggestRectangleEasy {

 public int findArea(int N) {
  int n = N/2;
  boolean isEven = n%2 == 0;
  if( isEven ){
   return n/2*n/2;
  }else{
   return (n/2)*(n/2+1);
  }
 }

}

得点は237.46/250、中央値もほぼ同じ点数。辺の長さの総和が一定のとき、長方形の面積が最大というのは、縦横の本数が同じになるという性質を利用した(a+bが一定の時、abの最大値を求める問題と同じになる)。次は、縦横の辺の長さの求め方であるが、棒の本数をいったんN以下で最大の偶数に直し、それを2で割る。さらにその値が2で割り切れるか否かで場合分けしている。上の例で考えてみると、11は10になり、縦横1辺ずつの総和は5、したがって、これを5/2=2.5の前後の整数である2、3に割り振ればよいと考えていることになる。点数は高くないが、数学的性質を用いて綺麗に解くことができる問題と思います。

TopCoder SRM317 Div2 250Pts

このTopCoderの問題はPracticeRoomのみでみられるようである。問題についておおまかに説明する。

元の文字列の部分列を最大で1箇所ひっくり返し、角カッコ（[と]のこと）で囲うというものは、暗号化する方法として安全とは言えない。例えば、暗号化された"he[row oll]ld"という文字列は"hello world"になる。sという暗号化された文字列が与えられたとき、元の文字列を返すようなメソッドを作成せよ。

注意点としては、文字列は小文字のアルファベット、スペース、角カッコのみから構成されること、また、角カッコは対になって出現するか、まったく出現しないかのどちらかになる。したがって、角カッコがない場合にも対処が必要になる。

私の解答はこちら。

public class ReversingBrackets {

 public String removeBrackets(String s) {
  String[] ss = s.split("[\\[\\]]"); // [と]を区切り文字にする
  StringBuffer sb = new StringBuffer();
  for( int i=0 ; i<ss.length ; i++ ){
   if( i == 1 ){ // ここに入るのは[]があったときのみ
    StringBuffer tmp = new StringBuffer();
    tmp.append(ss[i]).reverse();
    sb.append(tmp);
   }else{
    sb.append(ss[i]);
   }
  }
  return sb.toString();
 }

}

得点は237.70/250、中央値は約226点。[]があればssの長さは3、なければ1になるという性質を利用。また、区切り文字の有無を判定するには、indexOfを利用する方法も有力だろう。このsplitメソッドを用いた解答は少ない印象でした。

TopCoder SRM316 Div2 250Pts

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

文章の中には隠されたメッセージが含まれていることがある。この問題では、文章の書く単語の先頭の文字を順に並べたものが隠されたメッセージである。textというアルファベットの小文字と空白のみからなる文字列が与えられたとき、隠されたメッセージを返せ。ここでいう単語は連続するアルファベットの最大長である。また、単語の間には複数の空白があることもある。textは空白のみからなることもあることにも注意せよ。

私の解答はこちら。

public class HiddenMessage {

 public String getMessage(String text) {
  StringBuffer sb = new StringBuffer();
  String[] split = text.split(" ");
  for( int i=0 ; i<split.length ; i++ ){
   if( split[i].equals("") ) continue;
   sb.append(split[i].charAt(0));
  }
  return sb.toString();
 }

}

得点は246.34/250、中央値は約243点。以前、""に対し、charAtメソッドを使って嵌っていたような。今回はスムーズに解答。

TopCoder SRM315 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。この問題には画像がついてくるので、解く場合には目を通しておくと良い。では、問題文について説明する。

"Petals Around the Rose"(ばらの周りの花びら)はかなりよく知られた論理ゲームである。ゲームを知っている人が5つのダイスを振り、数字を言う。相手はその数字を得たルールを推測する。このゲームはトリッキーなものであるから、私たちはあなたたちにこのゲームを頼むわけではない。ルールは単に「ばらの周りの花びら」のように、各ダイスの中心にあるドットの周囲にあるドットの総和を求めるというものである。つまり、1、2、4、6の目は花びらは0であり、3の目には2つ、5の目には4つの花びらがあると言える。dice[]という、5つのダイスの目の値が書かれた配列が与えられたとき、上記の設定のよって求められる花びらの数を返せ。

私の解答はこちら。

public class RosePetals {

 public int getScore(int[] dice) {
  int[] petals = {0, 0, 2, 0, 4, 0}; // 花びらの数を入れた配列
  int nPetal = 0;
  for( int i=0 ; i<dice.length ; i++ ){
   nPetal += petals[dice[i]-1];
  }
  return nPetal;
 }

}

得点は246.19/250、中央値は約243点。1発で通過。特に悩む点はない。

TopCoder SRM314 Div2 250Pts

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

Byterlandの牛は騒々しく鳴き、住民に迷惑をかけている。PemberleyのDarcyさんはこの問題を牛1匹だけが鳴くことを許すことによって解決しようと計画している。他の牛にもっとも攻撃的でない牛を1匹選ぶ。Pemberleyの農場はn*mの長方形の草原に分けられる。各区画は何もないか、牛がいるという状態のどちらかである。(x,y)の位置にいる牛が鳴いたとき、(i,j)の位置にいる牛の不満はユークリッド距離の2乗であらわされる。不満の総計はすべての牛の不満の合計で表される。1匹の牛が鳴くことのみを許したとき、牛の不満が最小となるときのその値を返せ。農場はfarmlang[]という文字列型の配列で表され、"."は空の区画、"C"が牛のいる区画を表すものとする。

私の解答はこちら。

import java.util.ArrayList;

public class MooingCows {

 public int dissatisfaction(String[] farmland) {
  ArrayList<Integer> xPos = new ArrayList<Integer>();
  ArrayList<Integer> yPos = new ArrayList<Integer>();
  // 前半で牛のいる位置を全部求める。
  for( int i=0 ; i<farmland.length ; i++ ){
   for( int j=0 ; j<farmland[0].length() ; j++ ){
    if( farmland[i].charAt(j) == 'C' ){
     xPos.add(i);
     yPos.add(j);
    }
   }
  }
  // 後半は各牛が鳴いたと仮定したときの不満の最小値を計算する
  int minDissatisfaction = Integer.MAX_VALUE;
  for( int i=0 ; i<xPos.size() ; i++ ){
   int x = xPos.get(i); // x,yは特定の牛1頭の位置である
   int y = yPos.get(i);
   int curDissatisfaction = 0;
   for( int j=0 ; j<xPos.size() ; j++ ){
    if( i == j ) continue; // この箇所は無くてもOK
    int cx = xPos.get(j);
    int cy = yPos.get(j);
    curDissatisfaction += (x-cx)*(x-cx)+(y-cy)*(y-cy);
   }
   if( curDissatisfaction < minDissatisfaction ) minDissatisfaction = curDissatisfaction;
  }
  return minDissatisfaction;
 }

}

得点は221.44/250、中央値は約196点。

TopCoder SRM313 Div2 250Pts

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

組合せゲームという長方形の盤面で遊ぶソリティアを単純化したゲームがある。盤面はN個の正方形に連続して分けられる。正方形の中には1からNの整数が一つずつ入る。また、それぞれの正方形の位置にも数値が1からNまで左から順に振られている。ゲームは次のようなものである。まず、ある場所を一つ選ぶ。次にその場所に書かれている数字に飛ぶ。これを繰り返し、最初の位置に戻ったら終了とするというものである。ボードはboard[]という整数型の配列で与えられ、i番目の要素はi番目の正方形の位置に書かれている値である(iは1から始まる添え字とする)。ゲームのプレーヤーが正方形をもっとも多く飛んでいくときの、そのとんだ回数を返せ。

同じ場所に飛んで終了した場合は1回として数えることに注意。

私の解答はこちら。

public class CyclesInPermutations {

 public int maxCycle(int[] board) {
  int maxcycle = 0;
  for( int i=0 ; i<board.length ; i++ ){
   int startPos = i; // 初期位置
   int jumpTo = board[i]-1; // 飛んでいく先
   int nStep = 1;
   while( true ){
    maxcycle = Math.max(maxcycle, nStep); // とんだ回数の更新
    if( jumpTo == startPos ){ // 初期位置に戻ってきたら終了
     break;
    }
    jumpTo = board[jumpTo]-1; // 次に飛ぶ位置
    nStep++; // とんだ回数をカウント
   }
  }
  return maxcycle;
 }

}

得点は189.66/250、中央値は約199点。最初の位置に戻れば終了というところで、なぜか途中通った箇所に着いたら終了と考えていたので時間をくってしまいました。

TopCoder SRM312 Div2 250Pts

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

エスペラント語で1から99までの数字を書けというのが問題。命名規則は次の通り。1から10は{"unu", "du", "tri", "kvar", "kvin", "ses", "sep", "ok", "nau", "dek"}で与えられる。11から19は1から9の数字の前に"dek "(空白に注意)を付けたものである。20から29は"dudek "(これも空白に注意)を1から9の数字の前につけたものである。dekの前についているduは2である。30以上は20から29と同様のルールで命名されている。さて1から99までの値の1つを受け取ったとき、その値をエスペラント語にして返せ。

私の解答はこちら。

public class EsperantoNumbers {

 public String nameThisNumber(int x) {
  String[] num = {"", "unu", "du", "tri", "kvar", "kvin", "ses", "sep", "ok", "nau", "dek"};
  if( x >= 1 && x<=10 ){
   return num[x];
  }else if( x <=19 ){
   return "dek" + " " + num[x%10];
  }else if( x <= 99){
   if( x % 10 == 0 ){
    return num[x/10] +"dek";
   }else{
    return num[x/10] +"dek" + " " + num[x%10];
   }
  }
  return null;
 }

}

得点は229.05/250、中央値は約205点。1人撃墜して+50点。先頭に空文字をつける解答は少数派という印象がありました。この方が配列の添え字が単純になるから良いかと思ったのですが。この問題のテストケースは本来99通りしかないのですが、121通りテストケースが用意されていました。なぜでしょうね。

TopCoder SRM311 Div2 250Pts

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

あなたは長方形内部の(x,y)という点にいる。長方形の左下は(0,0)で、右上は(w,h)である。長方形の境界にたどり着くために動かなければならない距離の最小値を返せ。

私の解答はこちら。

public class EscapeFromRectangle {

 public int shortest(int x, int y, int w, int h) {
  int px = Math.min(x, w-x);
  int py = Math.min(y, h-y);
  return Math.min(px, py);
 }

}

得点は249.34/250、中央値は約242点。

TopCoder SRM310 Div2 250Pts

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

1分間に1度温度を測る装置を持っているが、装置のセンサは100%信頼できるわけではなく、豪快に正しくない値を出してくることがある。新しい装置を買うお金もないので、不適切な値を捨てるソフトウェアを作成して問題に対処することにした。値が-273より小さい、または前後2分かの値と比較して2度よりも大きく変化していたら不適切な値を見なすと考える。measuredValues[]という直近の温度が計測された値が含まれた配列が与えられる。この値は時系列順になっている。つまり、i番目の値は計測を始めてからi分後の温度を示している。妥当な計測値の平均値を計算して返せ。どの計測値も妥当な値でない場合、-300を返すようにせよ。

私の解答はこちら。

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

public class MeasuringTemperature {

 public double averageTemperature(int[] measuredValues) {
  ArrayList<Integer> set = new ArrayList<Integer>();
  for( int i=0 ; i<measuredValues.length ; i++ ){
   if( measuredValues[i] < -273 ){
    continue;
   }
   int from = i-2 <= 0 ? 0 : i-2;
   int to = i+2 <= measuredValues.length-1 ? i+2 : measuredValues.length-1;
   for( int j=from ; j<=to ; j++ ){
    if( j == i ){
     continue;
    }
    if( Math.abs(measuredValues[i]-measuredValues[j])<=2 ){
     set.add(measuredValues[i]);
     break;
    }
   }
  }
  if( set.size() == 0 ) return -300.0;
  Iterator<Integer> it = set.iterator();
  double sum = 0.0;
  while (it.hasNext()) {
   sum += it.next();
  }
  return sum/set.size();
 }

}

得点は160.57/250、中央値は約129点。点数が低いのは英語の読解問題だったからです。やっかいだったのは、先頭は後ろ2つの測定を見るだけでOKというようなことが明示されていなかったことだったりします。

TopCoder SRM309 Div2 250Pts

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

あなたはコンテストのコーディネータであり、コンテスト参加者の最終成績を受け取った。あなたにコンテストの質を決める仕事がやってきた。それを実行するために、あなたは上位k人と下位k人のスコアを取り除いた平均点を計算する。kは0以上の整数とし、平均点を最大にするようなkを選ぶとする。最大となる平均スコアを実数型で返せ。なお、すべてのスコアを取り除くことは許されないものとする。

私の解答はこちら。

import java.util.Arrays;

public class ContestCoordinator {

 public double bestAverage(int[] scores) {
  double max = -1.0;
  Arrays.sort(scores);
  for( int i=0 ; i<scores.length ; i++ ){
   // ソートした後に配列の添字がfromからtoまでの範囲の平均を計算する
   int from = i;
   int to = scores.length-1-i;
   if( from > to ) break;
   max = Math.max(max, ave(scores,from,to));
  }
  return max;
 }
 private double ave(int a[],int from, int to){
  double sum = 0.0;
  for( int i=from ; i<=to ; i++ ){
   sum += a[i];
  }
  return sum/(to-from+1);
 }
}

得点は236.42/250、中央値は約193点。すべての要素を取り除いてはいけないということを表現するところがfrom<toになるのがちょっと考えさせられる点かなと思います。

TopCoder SRM308 Div2 450Pts

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

ハフマン符号を使ってテキストをエンコーディングするとき、各文字は0-1のビット表現された文字に置き換えられる。この置き換えはシンボルのビット文字列表現は決して他のシンボルのビット文字列表現の接頭辞にはならない(要は各0-1は1つの文字を表すためにしか利用されないということだ)。この性質によりエンコードされたテキストをデコードする際のあいまいさはなくなる。

問題ではarchiveとdictionary[]という文字列と文字列型配列が与えられる。dictionaryのi番目の要素はアルファベットのi番目の大文字のビット文字列表現である。archiveをdictionary[]を用いてデコードし、その結果を文字列として返すメソッドを作成せよ。

私の解答はこちら。

public class HuffmanDecoding {

 public String decode(String archive, String[] dictionary) {
  int aPos = 0; // デコードしている文字の現在位置
  StringBuffer ret = new StringBuffer();
  while( true ){
   if( aPos >= archive.length() ) break; // 最後まで見たら終了
   StringBuffer sb = new StringBuffer();
   for( int i=aPos ; i<archive.length() ; i++ ){
    sb.append(archive.charAt(i)); // archiveから1文字追加
    int nMatch = 0;
    int idx = 0;
    String comp = sb.toString();
    for( int j=0 ; j<dictionary.length ; j++ ){
     if( comp.equals(dictionary[j]) ){
      nMatch++; // dictionaryで一致した文字の数をカウント
      idx = j; // dicrionaryの何番目と一致したかを記録
     }
    }
    if( nMatch == 1){ // デコードできる文字が1つに定まったら
     char c = (char)(idx + 'A'); // キャストに注意
     ret.append(c); // 文字を解答に追加
     aPos = i+1; // 次の文字から続けて見ていく
     break;
    }
   }
  }
  return ret.toString();
 }

}

得点は379.88/450、中央値は約223点。らしからぬ1発submitでした。問題を解く方針としては、archiveの注目している位置から1文字ずつ追加していき、dictionaryと比較して、候補になる文字が一つに絞られた瞬間にデコードして一つの文字に置き換えるということを実装するものです。

TopCoder SRM308 Div2 250Pts

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

異なる数からなる集合において、中央値Mというのは、Mより大きい数の個数と小さい数の個数が等しくなることを言う。例えば{1, 4, 2, 5, 7}という集合における中央値は4である。この定義により、{1, 4, 2, 5}という集合は中央値は存在しないことになる。numbers[]という異なる数値からなる配列が集合として与えられたとき、中央値を返せ。もし中央値が存在しないのであれば-1を返せ。

私の解答はこちら。

import java.util.Arrays;

public class MedianOfNumbers {

 public int findMedian(int[] numbers) {
  if( numbers.length % 2 == 0 ) return -1; // 要素数が偶数なら中央値は存在しない
  Arrays.sort(numbers); // ソートして
  return numbers[numbers.length/2]; // 中央の添え字の値を返す
 }

}

得点は249.34/250、中央値は約244点。全体的に超高速。

TopCoder SRM307 Div2 250Pts

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

ブーツ屋がN個の左足用ブーツと右足用ブーツの出荷を工場から受け取った。各ブーツは整数の値で同じサイズであるとき、適切なペアになる。各ブーツは1つのペアにしか属することはできない。ブーツ屋の人はN組の適切なペアを作りたいと思っている。ただ、幸いにも工場はサイズの異なるブーツは交換すると言ってくれた。さて、left[]とright[]という左と右足用のブーツのサイズが与えられたとき、交換しなければならないブーツの組の最小数を求めよ。

私の解答はこちら。

import java.util.Arrays;

public class BootsExchange {

 public int leastAmount(int[] left, int[] right) {
  int posL = 0;
  int posR = 0;
  int nMatch = 0;
  Arrays.sort(left);
  Arrays.sort(right);
  while( true ){
   if( posL == left.length || posR == left.length ) break;
   if( left[posL] == right[posR] ){ // 適切な組
    nMatch++;
    posL++;
    posR++;
   }else if( left[posL] < right[posR] ){
    posL++;
   }else{
    posR++;
   }
  }
  return left.length-nMatch;
 }

}

得点は206.98/250、中央値もほぼ同じ約207点。両足のブーツのサイズをソートしたのちに、先頭から探索し、未探索のブーツのサイズが一致すればマッチしたと言えるし、合わなければ小さい方のブーツのサイズを上げる(=ソート済なのでインデックスを1増やす)ようにすればよい。探索の終了条件は左右どちらかの靴が最後まで探索を終えたときである。

JavaのComparableの使い方

前回はComparatorを用いたソートを行ったが、今回はComparableインタフェースを用いたソートを実装してみた。

例題として、絶対値の小さい順にソートするということを考える。もし、絶対値が同じ値が複数現れた場合は、先に現れた方を先に配置するようにする。

import java.util.Arrays;

class comparableTest{
 public static void main(String[] args){
  sortByAbs[] data = new sortByAbs[5];
  data[0] = new sortByAbs(3);
  data[1] = new sortByAbs(-3);
  data[2] = new sortByAbs(0);
  data[3] = new sortByAbs(-10);
  data[4] = new sortByAbs(5);
  Arrays.sort(data);
  for( int i=0 ; i<data.length ; i++ ){
   System.out.println(data[i].val);
  }
 }
}

class sortByAbs implements Comparable<sortByAbs>{
 int val;
 public sortByAbs(int val) {
  // TODO 自動生成されたコンストラクター・スタブ
  this.val = val;
 }
 @Override
 public int compareTo(sortByAbs o) {
  // TODO 自動生成されたメソッド・スタブ
  return Math.abs(val)-Math.abs(o.val);
 }
}

このコードを実行すると次の結果が得られる。0に近い順にソートされていることが分かる。

0
3
-3
5
-10

注目すべき点としては、Arrays.sort()に第2引数は不要であるということである。sortByAbs型のソート方法はcompareToメソッドで既に分かっているからである。Comparatorと比較すると、Comparatorはオブジェクトに対し複数のソート方法を用意できるが、Comparableは1種類しか用意できないという違いがある。

また、当初分からないコンパイルエラーのメッセージがあった。上記のコードは既にエラーを取り除いた結果であるが、記録を兼ねて残しておく。

sortByAbs cannot be cast to java.lang.Integer comparable

このコードはComparableの後にintで比較するからということで<Integer>をつけていたのが原因だった。どのような型のオブジェクトを比較するのかを書く必要があり、<sortByAbs>とするのが正しい。

TopCoder SRM305 Div2 250Pts

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

多くのコンピュータシステムでは、同じクロックサイクルの間、複数のプロセスが同じ資源から読み込みができるが、1サイクルに1つのプロセスしか書き込みができない。読み込みと書き込みは同じクロックに混ぜることはできない。読み込みと書き込みの履歴がtraceという文字列として与えられ、procという計算に利用されたプロセッサの数が与えられたとき、その処理にかかった最小クロック数を返すメソッドを返せ。traceのRという文字が読み込みを、Wという文字は書き込みを表すものとする。

たとえば、"RWWRRR"というtraceと、3というprocが与えらえると、その処理に必要となる最小クロック数は4である。先頭のRで1クロック、W2つで2クロック、R3つは1クロックで処理できるから1+2+1=4ということになる。

私の解答はこちら。

public class MultiRead {

 public int minCycles(String trace, int procs) {
  int nr = 0; // rが連続している回数(procと関連して必要な変数)
  int nCycle = 0; // サイクル数をカウント
  boolean isPrevW = true; // 直前の文字はWか?
  for( int i=0 ; i<trace.length() ; i++ ){
   if( trace.charAt(i) == 'W' ){ 
    nCycle++; // Wはとにかく1クロックと数える。
    nr = 0; // rが連続した回数は0にリセット
    isPrevW = true;
   }else{ // R
    if( isPrevW == true ){
     isPrevW = false;
     nr = 1;
     nCycle++;
    }else{
     nr++;
    }
    // もしRが大量に続いたら、次のクロックに移る
    if( nr > procs ){ 
     nr = 1;
     nCycle++;
    }
   }
  }
  return nCycle;
 }

}

得点は219.53/250、中央値は約200点。1発で通した。Rがprocsを越えて続いた場合の処理を誤らないことがポイント。

TopCoder SRM304 Div2 250Pts

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

いくつかのサイズからなる絨毯が入荷されている。事実、縦と横の長さが同じ偶数でない整数以外の、任意の縦横の長さを持つ絨毯を見かけることができる。例えば4*4の絨毯は見かけられるが、2*4は長さが異なり、かつ偶数なので見つけられないことになる。ある領域が与えられたときに、いくつ絨毯の選択方法があるかということが知りたい。areaという面積を表す整数値が与えられたときに、その面積をきっかり覆う絨毯の選び方が何通りあるかを返すメソッドを作成せよ。なお、同じサイズのものは2回数えてはならない。つまり6*9と9*6は1回として数えよ。

私の解答はこちら。

public class RugSizes {

 public int rugCount(int area) {
  int cnt = 0;
  int mul = 0;
  // sqrtを取ればよいのは対称性を考慮したため
  // 実はfloorでなく、intへのキャストでOK
  for( int i=1 ; i<=Math.floor(Math.sqrt(area)) ; i++ ){
   if( area % i == 0 ){ // 絨毯のサイズは整数*整数に限られる
    mul = area/i; // iが1辺、mulが他辺を表す
    if( i == mul ){ 
     cnt++; // もし両方の辺の長さが等しければ
    }else if( i % 2 != 0 || mul % 2 != 0 ){
     cnt++; // 辺の長さが違い、かつともに偶数でない
    }
   }

  }
  return cnt;
 }

}

得点は235.98/250、中央値は約199点。同じものを数えないようにするために、areaの平方根を切り捨てた値まで検討すれば良いというのがポイント。

JavaのComparatorの使い方

今までTopCoderで利用してきたソートにArrays.sort(配列)というメソッドがあるのだが、実は第2引数を取ることができる。第2引数ではソートの手法を示すメソッドを含むオブジェクトを渡すことになる。C言語のqsort関数と同様の仕組みがJavaにもあるということである。

サンプルとして、短い文字列から長い文字列になるようなソートを行うことにした。長さが同じものについては、文字の大小の区別をなくした上で、辞書順に並ぶようにする。

まず、比較のメソッドを含むオブジェクトに関するクラスをCompTest.javaに書いた。

import java.util.Comparator;

// 次行のStringは比較する2要素の型を示している。
public class CompTest implements Comparator<String>{ 
 @Override // オーバーライドしている場合につける注釈
 // 関数名のcompareは決まりごとである。
 public int compare(String s1, String s2 ){
  // s1がs2より先に来るなら、s1の特徴量がs2のそれより小さくなるような関数を作成する。
  if( s1.length() > s2.length() ){
   return 1;
  }else if( s1.length() < s2.length() ){ // s1の方がs2より短い文字列になっている場合
   return -1;
  }else{
   return s1.compareToIgnoreCase(s2);
  }
 }

}

テスト用のmain関数を含むクラスがあるファイルはtest.javaとした。

import java.util.Arrays;

public class test {
 public static void main(String args[]){

  String[] lang = {"Java","Lisp","Haskell","C","Go"};
  Arrays.sort(lang, new CompTest() ); // 配列のソートの第2引数にCompTestを渡す
  for( int i=0 ; i<lang.length ; i++ ){
   System.out.println(i + ":" + lang[i]);
  }

 }
}

ソートした結果は次の通りである。

0:C
1:Go
2:Java
3:Lisp
4:Haskell

TopCoder SRM302 Div2 250Pts

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

英語では名刺の複数形は多くのややこしい規則からなるが、大部分は4つのルールから複数形が生成される。次のようなルールである。

• s,z,x,ch,shで終わる場合はesを語尾につける
  
• ay,ey,iy,uy,oyで終わる場合はsを語尾につける
  
• yで終わるが上のルールを満たさない場合、最後のyを除いたうえでiesをつける
  
• それ以外はsを語尾につける
  

nouns[]という複数形に変化させる前の文字列が与えられたときに、上の4つのルールに従って複数形に変化させた時の結果を配列で返せ。

私の解答はこちら。

public class NounReform {

 public String[] makePlural(String[] nouns) {
  String[] rule1 = {"s", "z", "x", "ch", "sh"};
  String[] rule2 = {"ay", "ey", "iy", "oy", "uy"};
  String[] ret = new String[nouns.length];
  LOOP : for( int i=0 ; i<nouns.length ; i++ ){
   System.out.println(nouns[i]);
   for( int j=0 ; j<rule1.length ; j++ ){
    if( nouns[i].endsWith(rule1[j]) ){
     ret[i] = nouns[i] + "es";
     continue LOOP;
    }
   }
   for( int j=0 ; j<rule2.length ; j++ ){
    if( nouns[i].endsWith(rule2[j]) ){
     ret[i] = nouns[i] + "s";
     continue LOOP;
    }
   }
   if( nouns[i].endsWith("y") ){ // rule3にしてもよいかな?
    ret[i] = nouns[i].substring(0, nouns[i].length()-1) + "ies";
   }else{
    ret[i] = nouns[i] + "s"; // rule4に該当
   }
  }
  return ret;
 }

}

得点は159.48/250、中央値は約190点。C言語のgotoに相当することがしたくて、調べものをしたら時間がかかってしまった。

TopCoder SRM301 Div2 250Pts

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

すべて値が異なる数列Aを挿入ソートで昇順にソートする。数列Aの先頭から順に挿入先を決めて、途中に挿入することになれば、後ろに要素をずらして値を挿入する。さて、A[]というすべて値が異なる数列が与えられたときに、挿入ソートで数値をずらした回数を返すメソッドを作成せよ。

例えば、A={2,4,3,1}という数列をソートすると4という値が返されることになる。これは2、4を挿入した後に、3を挿入すると、4がずれて1回。さらに1を挿入すると、2、3、4がずれて3回ずらすことになり、全部で4回ずらすからである。

私の解答はこちら。

import java.util.ArrayList;
import java.util.Collections;

public class InsertionSortCount {

 public int countMoves(int[] A) {
  ArrayList<Integer> al = new ArrayList<Integer>();
  int ret = 0;
  for( int i=0 ; i<A.length ; i++ ){
   int n = A[i];
   for( int j=0 ; j<al.size() ; j++ ){
    if( n < al.get(j) ){
     ret += al.size()-j;
     break;
    }
   }
   al.add(n);
   Collections.sort(al);
  }
  return ret;
 }

}

得点は194.01/250、中央値は約219点。毎回Collections.sortを呼ばないで、昇順でソートするTreeSetを使っても良かったかもしれない。

TopCoder SRM300 Div2 250Pts

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

タクシーキャブ距離というのは、軸に平行に移動するという制約下で2点間を移動する距離である(注：普通はマンハッタン距離の方がしっくりくる表現だと思います)。タクシーキャブ距離というのは、通常は二点を直線で結ぶよりも長い距離になる。タクシーキャブ距離と長方形領域の制約が与えられたとき、直線距離(=ユークリッド距離)の最大値を知りたい。maxX、maxYという長方形のX、Y値の最大値とtaxiDisというタクシーキャブ距離が与えられたときに、領域内の2点間でタクシーキャブ距離がtaxiDisになるもののうち、直線距離が最大になるときのその値を返せ。もし、領域内でtaxiDisになる2点の組がないなら-1.0を返せ。なお、長方形領域は0<=X<=maxX、0<=Y<=maxYを満たす領域である。

例えば、maxX=10、maxY=3、taxiDis=3とすると、3.0が解になる。2点間をX軸方向、あるいはY軸方向に平行に3移動するのが直線距離を最大にするからである。

私の解答はこちら。

public class Taxi {

 public double maxDis(int maxX, int maxY, int taxiDis) {
  if( maxX + maxY < taxiDis ) return -1.0; // 収まらない
  if( maxX >= taxiDis || maxY >= taxiDis ){ // 1辺に平行な状態で収まる
   return taxiDis;
  }else{ // XY軸とは平行にならない方向に直線が収まる
   double longer = maxX>=maxY ? maxX : maxY;
   double shorter = taxiDis - longer;
   return Math.sqrt(longer*longer+shorter*shorter);
  }
 }

}

得点は214.37/250、中央値は約149点。この問題のポイントは直線間距離を最大にするというのは、できるだけ1つの軸方向への移動距離を長くして、もう一つの軸に沿った移動は短くするということである。それに気付いたため、中央値より良い点数になったのだと思われる。コードもすっきりしていて読みやすくなった。

2011年12月の学習記録

2011年12月に学習した主な本一覧。TopCoderでJavaプログラミングを中心に学習していたので、座学が疎かになっていました。

高専の数学3(pp.1～70)

偏微分と微分方程式の復習を目的に読書。時間も限られているので、2次微分方程式まで解ければ良しとする予定。

UNIX/Solarisアソシエイツ(pp.1～145)

Solarisの事を学ぶ必要が生じたので、資格の本で基本的なことを勉強。トラブル時の対応ができるようになりたい。

Java言語プログラミングレッスン下(pp.143～読了)

これだけだと、Oracle Java SE6プログラマの試験範囲で出題されたジェネリクスやコンパレータの書き方が分からないので、もう少し他の資料を漁ってみる必要があると思った。内容自体は極めて読みやすい。

TopCoder SRM299 Div2 250Pts

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

歴史的な経緯から、人々は華氏と摂氏のように異なったスケールで温度を測っている。あなたへの課題は、あるスケールで計測された温度を別のスケールの温度に変換することである。どちらのスケールも互いに線形な関係であることが知られている。つまりある温度tに対し、a*t+bで別のスケールに変換できるということである。問題文では5つの整数値が与えられる。f1、b1というあるスケールで水が凍る温度と沸騰する温度、f2、b2という別スケールで水が凍る温度と沸騰する温度、tというf1、b1のスケールにおけるある温度である。返す値はtを2番目のスケールに変換したときの温度である。

私の解答はこちら。

public class TemperatureScales {

 public double convert(int f1, int b1, int f2, int b2, int t) {
  return 1.0*(b2-f2)/(b1-f1)*(t-f1)+f2;
 }

}

得点は246.26/250、中央値は約213点。撃墜1つで+50点。関係は直線で説明できるので、直線の傾きと通る1点が分かればOK。上のコードでは、(f1,f2)という点を通るということを利用しています。実数に変換するところでミスしないように気を付けるだけですね。コーディングより問題文を読むほうがずっと時間がかかってしまうような問題でした。

TopCoder SRM298 Div2 250Pts

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

進捗インジケータの動きを制御するプログラムをシミュレーションする。インジケータは4つの状態(文字)を取る、1つの文字列からなる。文字は|、-、\、/からなる。プログラムでは文字列の出力命令は<instr%gt; <secs>という形式で与えられる。instrは4つの取り得る動き、secsはその動きの継続時間を表している。動きは1秒間に1つである。4つの取り得る動きとは次のことを指す。

• L:左にスピンする。|は\、\は-、-は/、/は|に状態が変化する。
  
• R:右にスピンする。\は|、|は/、/は-、-は\に状態が変化する。
  
• S:そのままで状態は変化しない。
  
• F:バーは90度回転する。\は/、/は\、-は|、|は-になる。
  

つまり、"F03L02"という文字列と初期状態-が与えらえると、"-|-|\-"という文字列が返されることになる。

startStateという初期状態とprogramというプログラムが与えられたときに、その結果生成される文字列を返せ。文字列のi番目の文字はi秒後の状態を表すことになる。すなわち0秒(開始時点)は、初期状態(startState)に一致する。programは3*k(kは整数)の文字数からなる。3文字ごとに見ると、instrが1文字、secsが2文字になっている。secsは2桁になるよう0埋めされることがある。startStateは4つの状態のいずれかである。

私の解答はこちら。

public class IndicatorMotion {

 public String getMotion(String program, char startState) {
  StringBuffer sb = new StringBuffer();
  String indicator = "|\\-/";
  int pos = 0;
  for( int i=0 ; i<indicator.length() ; i++ ){
   if( startState == indicator.charAt(i) ){
    pos = i;
    break;
   }
  }
  sb.append(startState);
  for( int i=0 ; i<program.length()/3 ; i++ ){
   String dir = program.substring(i*3, (i+1)*3);
   char instr = dir.charAt(0);
   int secs = Integer.parseInt(dir.substring(1));
   int nMove = add(instr);
   for( int j=0 ; j<secs ; j++ ){
    pos = (pos+nMove)%(indicator.length()); // (1)
    sb.append(indicator.charAt(pos));
   }
  }
  return sb.toString();
 }
 private int add(char c){
  if( c == 'L' ){
   return 1;
  }else if( c == 'R' ){ 
   return 3; // -1としたら上の(1)はpos+nMove+indicator.lengthになる
  }else if( c == 'S' ){
   return 0;
  }else{
   return 2;
  }
 }
}

得点は163.50/250、中央値は約123点。4つのinstrの位置関係を表すのがポイントかと思います。コードだけでなく、ときには紙も利用するのが良いのでしょう。

TopCoder SRM297 Div2 250Pts

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

箱とパーツの集合が与えられたとき、いくつのパーツが箱に入れられるかということを決められるか尋ねられた。箱には最大で1つのパーツが入れられる。パーツを箱に合わせて入れるには、箱は少なくともパーツ以上のサイズでなければならない。パーツを以下の手続きに従って入れていく。

• まだ箱に入れられてない最小のパーツを選ぶ。
  
• そのパーツが入れられる最小の空箱を見つける。そのような箱がない場合、手続きを終了する。
  
• パーツを箱に入れる。
  
• すべてのパーツが箱に入ったら終了、そうでなければ手順の最初に戻る。
  

partSizes[]というパーツのサイズと、boxSizes[]という箱のサイズを表した整数型の配列がメソッドの引数として与えられる。どちらの配列も昇順で並べられている。以上の手順に従ったとき、箱詰めできるパーツの最大の数を求め、その値を返すメソッドを作成せよ。

私の解答はこちら。

public class PackingParts {

 public int pack(int[] partSizes, int[] boxSizes) {
  int idxPS = partSizes.length-1;
  int idxBS = boxSizes.length-1;
  int nPacked = 0;
  while( true ){
   // 終了条件はすべての箱かパーツをチェックし終えたとき
   if( idxPS < 0 || idxBS < 0 ) break;
   // 箱の方がパーツより大きい
   if( boxSizes[idxBS] >= partSizes[idxPS] ){
    nPacked++;
    idxBS--;
   }
   idxPS--; // 次のパーツを検討する
  }
  return nPacked;
 }

}

得点は227.97/250、中央値は約216点。問題を置き換えると、大きいパーツから順に調べ、残っている箱も大きいほうから見て、入れられるものがあればそれに入れるということになるので、そのような解き方になりました。