TopCoder SRM274 Div2 250Pts

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

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

私の解答はこちら。

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

public class SimpleDuplicateRemover {

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

}

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

TopCoder SRM273 Div2 250Pts

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

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

私の解答はこちら。

public class AimToTen {

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

}

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

TopCoder SRM272 Div2 250Pts

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

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

私の解答はこちら。

public class HammingDistance {

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

}

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

TopCoder SRM271 Div2 250Pts

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

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

私の解答はこちら。

public class CheckFunction {

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

}

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

RのapplyとrowSumsの比較

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

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

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

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

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

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

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

2011年11月の学習記録

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

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

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

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

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

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

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

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

TopCoder SRM270 Div2 250Pts

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

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

私の解答はこちら。

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

public class BuyingCheap {

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

}

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