TopCoder SRM449 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文についておおまかに説明する。問題文には画像があるので、そちらを参考にしても良いかもしれない。

山登りをする友人がどれだけ山を歩くことになるかを知りたい。簡単のため2次元にして考える。横から見ると、山は直角三角形をしており、斜面が45度、頂上が90度になっているとする。友人は左から右方向に向かって、x軸方向に大きくなる方向に向かって歩いていく。山は必ず連なっており(2つ以上に分かれていない)、i番目の山のふもとの始点はstart[i]、終点はfinish[i]という位置が整数型の配列で与えられている(訳注：つまり、その2つの整数値の真ん中が山の頂上のある水平方向の位置になる)。友人はこれらの山の一番高い所に沿って歩く。山を左端から右端まで歩いたとき、その歩いた距離の合計を返せ。

私の解答はこちら。

import java.util.Arrays;

public class MountainRoad {

 public double findDistance(int[] start, int[] finish) {
  Arrays.sort(start);
  Arrays.sort(finish);
  int diff = start[0]-finish[finish.length-1];
  return Math.abs(diff)*Math.sqrt(2);
 }

}

どの山が一番高いかなんて考える必要はない。山が連なっているという条件から、水平方向に1歩くと45度の斜面を歩いているのだから、必ずルート2だけ歩くのである。従って、startの最小値とfinishの最大値を求めてその距離をルート2倍すればよい。

TopCoder SRM448 Div2 250Pts

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

ブラックジャックのカード集合が与えられたときに、そのカード集合の点数の返せ。なお、1枚のカードは文字列配列cards[]の1要素であり、その文字は強さを表す1文字(2～9とTen、Jack、Queen、King、Aceの頭文字のいずれか)と、スート(Clubs、Diamonds、Hearts、Spadesの頭文字)の1文字を結合したものからなる。エースは11として数える。

私の解答はこちら。

public class TheBlackJackDivTwo {

 public int score(String[] cards) {
  int score = 0;
  for( int i=0 ; i<cards.length ; i++ ){
   char c = cards[i].charAt(0);
   if( c >= '2' && c <= '9'){
    score += c - '0';
   }else if( c == 'T' || c == 'J' || c == 'Q' || c == 'K' ){
    score += 10;
   }else{
    score += 11;
   }
  }
  return score;
 }

}

1回のsubmitでシステムテストクリア。単純な場合分けでお終い。この問題だけだと、何のために文字列が2文字になっているか分からないですね。Div1だと意味のある問題が出るのでしょうか。

TopCoder SRM447 Div2 250Pts

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

Facebookでは、異なるタスクが限られた数のコンピュータで同時に実行されなければならない。あなたにはやってくるタスクの集合が与えられる。各コンピュータは最大で1つのタスクを実行することができ、各タスクは1つのコンピュータで完全に実行されなければならない。complexityとcomputersいう整数型の配列が与えられる。complexityの要素iはi番目のタスクの複雑度を表す。computersのi番目の要素はi番目のコンピュータが扱うことができるタスクの複雑度の最大値である。与えられたcomputersで実行できるタスクの最大の数を返せ。

私の解答はこちら。

import java.util.Arrays;

public class ImportantTasks {

 public int maximalCost(int[] complexity, int[] computers) {
  Arrays.sort(complexity);
  Arrays.sort(computers);
  int idxCompl = complexity.length - 1;
  int idxCompu = computers.length - 1;
  int nExecutable = 0;
  while( idxCompl >=0 && idxCompu >= 0 ){
   if( computers[idxCompu] >= complexity[idxCompl] ){
    nExecutable++;
    idxCompu--;
   }
   idxCompl--;
  }
  return nExecutable;
 }

}

二つの配列をソートして、複雑度とコンピュータの処理能力を比較することを繰り返せばOK。大きい方から探すのが簡単と思います。

TopCoder SRM446 Div2 250Pts

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

トムは小さな男の子で、おもちゃを集めるのが好きである。誕生日にお母さんはトムにおもちゃの兵隊が入った箱をプレゼントとして買った。箱にはn人の兵隊がいて、1からnまで制服に書かれている。数字の先頭に0はついていないものとする。トムは兵隊を数えはじめるが、すべてを数えるのは難しいと気づいた。トムはラベル長がlowerBoundからupperBoundまでの兵隊だけを数えることにした。トムが数える兵隊の数を返せ。

私の解答はこちら。

public class SoldierLabeling {

 public int count(int n, int lowerBound, int upperBound) {
  int from = (int)Math.pow(10, lowerBound-1);
  int to = (int)Math.pow(10, upperBound)-1;
  to = Math.min(n, to);
  int num = to-from+1>=0 ? to - from + 1 : 0;
  return num;
 }

}

得点は243.23/250、1回のsubmitでシステムテストクリア。ラベル長なので10の何乗まで扱うかということになる。

TopCoder SRM445 Div2 300Pts

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

ジョンはセキュリティに関心を示している。彼は友人のブラスに手紙を書いており、他の誰にも読めないようにしたいと思っている。ジョンはメッセージをエンコードするための単純な置換の暗号を使っている。メッセージの各文字は、それに対応する代わりのアルファベットで置き換えられる。置き換えたアルファベットはすべて元のアルファベットの順列の1つである。この問題では、アルファベットは小文字のみからなるものとする。元のメッセージが与えられたとき、辞書順で最も速くなる暗号化された文字列を返せ。例えば、"hello"という文字列は"abccd"になる。これはhをa、eをb、lをc、oをdとすることで得られる。

私の解答はこちら。

import java.util.HashMap;

public class TheEncryptionDivTwo {

 public String encrypt(String message) {
  // HashMapは対応表の作成に用いる。キーが元のアルファベット、値が置換後のアルファベット
  HashMap<Character, Character> hm = new HashMap<Character, Character>();
  StringBuilder sb = new StringBuilder();
  char ch = 'a';
  for( int i=0 ; i<message.length() ; i++ ){
   char current = message.charAt(i);
   if( hm.containsKey(current) == false ){
    hm.put(current, ch);
    sb.append(ch);
    ch++;
   }else{
    sb.append(hm.get(current));
   }
  }
  return sb.toString();
 }

}

得点は289.64/300、1回のsubmitでシステムテストクリア。300点にしては簡単なのではないか。

TopCoder SRM444 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文についておおまかに説明する。画像があるので、必要に応じて本文を見て欲しい。

"4Blocks"は、特別な盤で二人のプレーヤーが協調するゲームである。盤は1*1の正方形のセルからなる格子である。格子は高さが2である。2種類の異なるブロックがある。1と4というブロックである。1は1*1、4は2*2のサイズである。あなたはブロックを辺が格子の辺に沿うように配置し、二つのブロックが重ならないようにしなければならない。最終スコアは各セルにある値の和である。1は1ポイントの価値があり、4は、セルが4つを各セルが4ポイントの価値で覆われることから、16ポイントの価値がある。あなたの友人は自分の番で盤に1のブロックをいくつか置く。現在の設定はgrid[]という文字列型配列で与えられる。i番目の文字列のj番目の要素はi行j列の上京を表しており、"."であれば空、"1"であれば、友人が1をそのセルに置いたということになる。あなたの番がやってきて、1と4のブロックを置くことができるが、既に置かれたブロックは除去できないものとする。 達成可能な点数の最高点を返せ。

私の解答はこちら。

public class FourBlocksEasy {

 public int maxScore(String[] grid) {
  int score = 0;
  int hPos = 0; // 現在注目する位置(ここと下、右、右下に注目する)
  int width = grid[0].length(); // 盤面の横幅
  while( true ){
   if( hPos >= width ) break; // 右端まで見たら終了
   if( grid[0].charAt(hPos) == '.' && grid[1].charAt(hPos) == '.' ){
    if( hPos == width-1 ){ // 右端まで来ていたら1を上下に置いて終了
     score += 2;
     break;
    }
    if( grid[0].charAt(hPos+1) == '.' && grid[1].charAt(hPos+1) == '.' ){
     score += 16; // 2*2のスキマがあるので4のブロックを置ける
     hPos += 2;
    }else{ // そうでなければ、1のブロックを上下において一つ右へ進める
     // 4足して二つ右に進めても良かったですね...
     score += 2;
     hPos++;
    }
   }else{ // 上下のどちらかに1が既に埋まっていた場合
    score += 2;
    hPos++;
   }
  }
  return score;
 }

}

得点は233.05/250、1回のsubmitでシステムテストクリア。左から順に4が置けるかチェックしていくだけでOK。

TopCoder SRM443 Div2 250Pts

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

サッカーでは、すべてのメジャーな国別リーグは次の方法で実施されている:

リーグはいくつかのチームからなる。1年を通して、各チームは別のチームと2試合行う - 1つは自身のスタジアム、1つは相手のスタジアムで行う。チームが自身のスタジアムでプレーするときは"ホームチーム"、相手は"アウェーチーム"と呼ばれる。各試合は3つの結果の1つで終わる: ホームチームの勝利、引き分け、相手チームの勝利である。チームは勝つ度に3ポイントを獲得する。引き分けは両方のチームに1ポイントが与えられる。負けたチームにはポイントは与えられない。全チームのランキングは各チームが受け取ったポイントの合計に基づく。さて、matches[]という文字列型の配列が与えられる。i番目の要素のj番目の文字の試合はチームiのスタジアムでチームiとチームjの間の試合の結果を表す。Wはホームチームの勝利、Dは引き分け、Lはアウェーチームの勝利を表す。主対角線上の試合のすべての文字は自身と戦うことはないので、"-"になる。i番目の要素がi番目のチームが獲得した点数の合計となる整数型の配列を返せ。

私の解答はこちら。

public class SoccerLeagues {

 public int[] points(String[] matches) {
  int[] pts = new int[matches.length];
  for( int i=0 ; i<matches.length ; i++ ){
   for( int j=0 ; j<matches[0].length() ; j++ ){ // 全探索の必要がある
    if( i == j ) continue; // 対角線上は無視
    char c = matches[i].charAt(j);
    if( c == 'W' ){ // cの結果に応じてチームi、jにポイントを振り分ける
     pts[i] += 3;
    }else if( c == 'D'){
     pts[i]++;
     pts[j]++;
    }else{
     pts[j] += 3;
    }
   }
  }
  return pts;
 }

}

得点は241.19/250、1回のsubmitでシステムテストクリア。

TopCoder SRM442 Div2 250Pts

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

Simple Word Gameというのは、プレーヤが与えられた辞書からできるだけ多くの単語を覚えようとするゲームである。プレーヤが覚えていた各単語に対するスコアは単語長さの平方である。player[]という各要素がプレーヤが覚えた単語の文字列型配列である。重複した単語があるかもしれないが、もし同じ単語が複数回出てきたら、それは1度に限って数える。dictionary[]という辞書も与えられ、これは各単語が異なったものからなる文字列型の配列である。プレーヤの合計点を返せ。

私の解答はこちら。

import java.util.Arrays;

public class SimpleWordGame {

 public int points(String[] player, String[] dictionary) {
  int pts = 0; // プレーヤの得点
  // 重複はソートして直前の単語と同じなら点数にしないという方針で作成する
  Arrays.sort(player);
  String prev = ""; // 直前の単語
  for( int i=0 ; i<player.length ; i++ ){
   String playerWord = player[i];
   if( playerWord.equals(prev) ) continue;
   for( int j=0 ; j<dictionary.length ; j++){
    if( dictionary[j].equals(playerWord) ){ // 辞書に覚えていた単語があった
     pts += playerWord.length() * playerWord.length();
     break;
    }
   }
   prev = playerWord; // 直前の単語の単語を更新
  }
  return pts;
 }

}

得点は244.25/250、1回のsubmitでシステムテストクリア。

TopCoder SRM440 Div2 250Pts

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

あなたは"The Incredible Machine"と呼ばれている古いコンピュータゲームを覚えているかも知れない。これはボールが落下すること、レーザーを打つこと、猫がネズミを追いかけることのような簡単な処理をシミュレーションすることができるゲームであった。さらにこれらの観察をさまざまな重力加速度の値で動作させることができた。重力加速度が未知のシステムを想像しよう。N個のボールがあり、最初にそれぞれは地面からある高さに固定されている。height[]というi番目の要素がi番目のボールの高さを表す整数型の配列が与えられる。時刻0において、最初のボールが放たれて落ち始める。それが地面に到達すると、2番目のボールが放たれる。これを時刻Tに最後のボールが落ちるまで続ける。このシステムの重力加速度を返せ。空気抵抗と他の抵抗する要素は無視せよ。初期速度0で、時間t落ち続けた物体の移動した距離dは、重力加速度をg、抵抗を無しとすれば、d=0.5*g*t^2という式に等しくなる。

私の解答はこちら。

public class IncredibleMachineEasy {

 public double gravitationalAcceleration(int[] height, int T) {
  double t = 0.0;
  for( int i=0 ; i<height.length ; i++ ){
   t += Math.sqrt(2*height[i]);
  }
  return t*t/(T*T);
 }

}

得点は230.45/250。それぞれの物体が地面に落ちるまでの時間はt=sqrt(2d/g)であり、これをそれぞれの要素で計算して、すべて足すとTになる。あとはこれをgについて解けばプログラムで計算すべき式が導出できる。

Rで線形判別分析

フィッシャーの線形判別分析(LDA:Linear Discriminant Analysis)と呼ばれる手法についての簡単な紹介。

2群(実際には3つ以上のときもあるが)の線形判別分析というのは、あるデータに対し、それが2群のどちらに属するかを正負により判定する線形式で与えるというものである。正なら群1、負なら群2というように分けられる。今回は、Rのirisデータにある「がく幅、がく長」の2つが与えられたときに、それがSetosa、Versicolorのどちらに属するか判定するという、一番基本的な線形判別のコードを試してみた。

アルゴリズムに関しては、Wikipedia(信頼しすぎてはいけないが)の判別分析の項目に見ることができる。さて、RのMASSパッケージには線形判別のための関数が用意されているので、これを利用することにする。

library(MASS)

set.seed(1)
iris2 <- iris[1:100,c(1,2,5)] # がく長、がく幅列とsetosaとversicolorが含まれる行のみを使う
# 学習用データと検証用データにデータを分ける
mdl.idx <- sample(1:100, 50, rep=F)
# iris2の種類の水準にvirginicaが残っているため警告がでる
mdl <- lda(Species~., data=iris2[mdl.idx,]) # 線形判別モデル
# モデルに検証用データを突っ込む
result <- predict(mdl, iris2[-mdl.idx,])

xr <- range(iris2[,1]) # 描画範囲の設定
yr <- range(iris2[,2])
# 学習用データの描画
plot(iris2[mdl.idx,1], iris2[mdl.idx,2], col=iris2[mdl.idx,3], 
     xlim=xr, ylim=yr, xlab=names(iris)[1], ylab=names(iris)[2])
par(new=T)
# 検証用データの描画
plot(iris2[-mdl.idx,1], iris2[-mdl.idx,2], col=iris2[-mdl.idx,3],
     xlim=xr, ylim=yr, xlab="", ylab="", pch=2)
title("irisデータの線形判別")
# グラフに凡例を追加
leg <- c("train:setosa", "train:versicolor", "test:setosa", "test:versicolor")
legend(6.4, 4.3, leg, pch=c(1,1,2,2), col=c(1,2,1,2))
# 線形判別直線の描画範囲設定
xc <- seq(min(xr), 6.3, length=100)
# 判別直線の定数項は計算が必要(applyの結果が定数に相当する)
yc <- (apply(mdl$means %*% mdl$scaling, 2, mean)/mdl$scaling[2] 
       - mdl$scaling[1]/mdl$scaling[2] * xc )
points(x=xc, y=yc, type="l", col="green", lwd=2) # 判別の境界線描画
par(new=F)

注意しなければいけないのは、線形判別直線を引くところである。単純に実行すると、

y = -apply(mdl$means %*% mdl$scaling, 2, mean) + mdl$scaling[1]*がく長 + mdl$scaling[2]*がく幅

という判別式が作成されるので、がく幅=の形に変形してxc(がく長)からyc(がく幅)を計算している。変形する際は、境界を考えているので、y=0になることにも注意。

上のコードを実行すると次のような結果が得られる。ちょっと際どいデータもあるが、概ね完全な分離ができているといっても良いであろう。

TopCoder SRM439 Div2 250Pts

Eclipse Coderがアップデートされて、ようやくArenaにログインできるようになったようなので演習再開。このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文についておおまかに説明する。

各セルに数値も含む、data[]という文字列型の長方形の格子が与えられる。この格子の中で、4つの角のセルがすべて同じ値を持つ最大の正方形を見つけよ。正方形の辺は格子の辺に平行でなければならないとする。もし、複数最大の正方形があるなら、1つを取り出せ。正方形中のセルの数を返せ。1つのセルも正方形なので、常に答えがあることに注意。

私の解答はこちら。

public class SquareOfDigits {

 public int getMax(String[] data) {
  int maxSize = 0;
  int[][] corner = new int[2][2]; // 正方形の4つの角の値を格納
  int nRow = data.length;
  int nCol = data[0].length();
  int rng = Math.min(nRow, nCol);
  for( int i=0 ; i<nRow ; i++ ){
   for( int j=0 ; j<nCol ; j++ ){ // (i,j)は正方形の左上の座標
    for( int n=0 ; n<rng ; n++ ){ // nは正方形のサイズ
     if( i+n >=nRow || j+n >= nCol ) continue;
     corner[0][0] = data[i].charAt(j);
     corner[0][1] = data[i].charAt(j+n);
     corner[1][0] = data[i+n].charAt(j);
     corner[1][1] = data[i+n].charAt(j+n);
     if( corner[0][0] == corner[0][1] && // 全部の角の値が同じなら
      corner[0][0] == corner[1][0] &&
      corner[0][0] == corner[1][1] ){
      // これまでにみつけた正方形の面積の最大値と比較
      maxSize = Math.max((n+1)*(n+1), maxSize);
     }
    }
   }
  }
  return maxSize;
 }

}

得点は218.49/250、1回のsubmitでシステムテストクリア。全部のパターンの探索方法の発見がポイントと思います。すぐに3重ループだと気づけば速いのでしょうけれど。

2012年11月の学習記録

2012年11月に学習した主な本一覧。今月は雑用や外出が多く、あまり学習が進まなかった感じがします。

入門・演習 数理統計(演習問題25問)

6章の問題を少し飛ばして7章へ。

カウントデータの統計解析(pp.71～112)

改めて読み返してみると、かなりマニアックな感じがする本です。もうちょっと一般的な内容の本から読めばよかったかなと思いました。

HTML/XHTML&スタイルシートレッスンブック(pp.233～313、読了)

CSSって何ぞ?だった私が1週間で概要をつかめた本です。手で打ち込むことで順番に覚えていけるので、htmlの概要を把握するには良書だと思いました。

JavaScriptワークブック(pp.1～119)

htmlの本を読んだ後にこれを読むと、多少理解がしやすくなりました。

その他、英文ドキュメント翻訳の作業。一月半で1/5ほどの工程を終えたところでしょうか(何をしているかはまだ公開できませんが)。LPIC Level1の小豆本も80ページほど読みました。

ExcelのVLOOKUP関数の紹介

Excelで2つのテーブルをマージして、マージしたテーブルの特定の列がほしいと考えた。Rのmergeを思いついたが、わざわざRを使うのも面倒そうなので、Excelでmergeのような関数はないかと調べてみたら、VLOOKUPという便利な関数があったので紹介しておく。マージというのは、あるテーブルのキーを基準にテーブルを結合するというものである。例えば次のようになる。

名前	身長
Aさん	170
Bさん	165
Cさん	173

名前	体重
Aさん	70
Cさん	65
Bさん	58

これらを名前をキーにしてマージすると以下のようになる。それぞれの体型が1つのテーブルとしてまとめられている。VLOOKUP関数では名前・身長の表から体重を含む表を参照し、体重列を横につけることを実現する。

名前	身長	体重
Aさん	170	70
Bさん	165	58
Cさん	173	65

さて、VLOOKUP関数の定義としては、次のようになる。

VLOOKUP(調べたい対象,範囲,列番号,論理値)

各引数について順に説明する。

• 第1引数の「調べたい対象」は、第2引数の「探索範囲」でどこにあるかを調べたいものを入れる。
• 第2引数の「探索範囲」はマージしたいテーブルと考えて差し支えない。通常、長方形状の範囲が選択されるはず。別シートの範囲を選択する場合は、sheet2!$A$1:$D$100のように!を使ってシート名を明記する必要がある。探索は左端の列から順に行う。
• 第3引数の「列番号」は「探索範囲」で「調べたい対象」があった行の何列目を取り出したいかということを指定する。シートで何列目かではなく、探索範囲の何列目かを指定する必要がある。
• 第4引数の「論理値」は完全一致のデータを探索する場合は、falseを指定すればよい。

上の例について考える。もし二つの表がsheet1とsheet2の「A1:B4の範囲(ヘッダも含めて)」にあったとすれば、sheet1のC2セルは次のように書けば、マージしたときと同等の値が得られる。A2の箇所はAさんを対象にしたものなので、Bさん、Cさんのマージ結果を得たい場合は、A3やA4とすればよい。

=VLOOKUP(A2,sheet2!$A$2:$B$4,2,false)

なお、一致するデータが複数あった場合は、先に見つかった方の結果のみが返ってくることに注意。

JavaScirptの繰り返し、条件分岐

for文とその中で用いられるであろう比較演算子もC言語と同じ。変数変更のためのインクリメント(i++)、デクリメント(i--)は用意されている。while文、switch～case文、break、continueもC言語と同じように使える。

条件分岐はif～else、if～else if～elseで実現する。C言語と同じと思ってよい。

論理演算子もC言語と同じく、&&(and)、||(or)、!(not)を利用することができる。

<SCRIPT language="JavaScript">
<!--
function mysum(from, to){
  var sum = 0;
  /*
    fromから始めてtoまでの整数の総和を計算する。
    to以下というのは比較演算子で実現する。
  */
  for( i=from ; i<=to ; i++ ){
    sum += i;
  }
  alert("合計 = " + sum);
}

/*
  入力された月の値に応じて季節を表示するというもの。
*/
function alert_season(){
  var mnt;
  mnt = prompt("1から12の整数を入力して下さい", "");
  var month = parseInt(mnt); // 整数として解釈させる
  switch(month){
    case 1:
    case 2:
    case 3:
      alert("春");
      break;
    case 4:
    case 5:
    case 6:
      alert("夏");
      break;
    case 7:
    case 8:
    case 9:
      alert("秋");
      break;
    case 10:
    case 11:
    case 12:
      alert("冬");
      break;
    default:
      alert("1～12の月が指定されていません。");
      break;
  }
}

/* 
  ナベアツがnum回アホになるときまでに数えた数を返す(ネタが古い!?)。
  indexOfは引数となる文字列が(""+i)という文字列にあれば、
  0以上の値(正確には位置を表す添字)が返されるようになっている。
  Javaと同じですね。
*/
function nabeatu(num){
  var i = 1;
  var counter = 0;
  while( true ){
    if( i % 3 == 0 || (""+i).indexOf("3") >= 0){ // or演算子の利用
      counter++;
    }
    if( counter >= num ){
      break;
    }
    i++;
  }
  alert(num + "回アホになるのに" + i + "まで数えました");
}

//-->
</SCRIPT>

FancyZoomの使い方

JavaScriptを用いると動きのあるWebページを作成することができます。紹介するFancyZoomというのは、名前から推測できる通り、ズームするという効果を要素に持たせることができるようになるライブラリです。画像に対してズームすることが多いのですが、リンク先をクリックして説明文をズーム画面で表示させることもできます。FancyZoomは非商用に限って無料で使えるそうです。個人的なページではタダということですね。以下、FancyZoomの導入手順について説明します。英語は簡単な説明なので、ここでは細かめに説明します。

1. FancyZoomライブラリをダウンロードしてきます。ダウンロード先はこちらになります。instructionsと書かれた先の下にzipファイルのアイコンがあるので、それをクリックして保存します。
2. ファイルを解凍します。トップディレクトリ(FancyZoom 1.1)の下に2つディレクトリができるのですが、_MACOSXではない方のFancyZoom 1.1というディレクトリを利用します(以下ではこのディレクトリをFZというディレクトリ名で表記します)。
3. FZディレクトリをサーバのトップディレクトリにおきます。ただし、そういう権限が無い中で作業しないといけないかもしれません。そのような時は、ライブラリを使いたいhtmlファイルと同じ位置にFZディレクトリを置きましょう。トップディレクトリに置かない場合は、js-globalディレクトリ以下のFancyZoom.jsの53行目にある、

   var zoomImagesURI   = '/images-global/zoom/';

   をディレクトリの位置に書き換える必要があります。例えば、'./FZ/images-global/zoom/'と変更し、画像の位置を相対パスで表記することにします。これを行わないと、画像を拡大したときに左上にでる×マークの画像が正しい場所を示していないので、見栄えが悪くなります。
4. ライブラリを利用したいhtmlファイルでライブラリが使えるようにしていきます。トップディレクトリにライブラリを置くことができるのであれば、以下のようになりますし、htmlファイルと同じ位置にFZディレクトリを置くのであれば、srcの値は相対パスで記述すればよいことになります。htmlファイルで書き込む場所はheadタグの内部になります。

   <script src="/FZ/js-global/FancyZoom.js" type="text/javascript"></script>
   <script src="/FZ/js-global/FancyZoomHTML.js" type="text/javascript"></script>
   

5. <body>タグにonload="setupZoom()"を追加します。これはhtmlファイルをロードしたときにJavaScriptのsetupZoom()関数を実行せよということを意味しています。
6. <a href="ズーム後に表示したい画像へのリンク"><img src="htmlファイルで表示する画像" /></a>のようにすれば作業完了。

その他、細かい仕様も載っていて、上と同じぐらい重要なことが書いてあります。

1. ズームした画像の下にキャプションをつけるには、hrefと一緒にtitle="～"を追加します。
2. hrefの最初の要素を利用して、位置やズームの表示位置を決めています。
3. ズームしたくない画像があるのであれば、hrefと一緒にrel="nozoom"と書きます。
4. ズーム機能を持たせられる画像はjpg、gif、png、bmp、tiffになります。
5. 画像をクリックして拡大画像を表示するという使い方もありますが、テキストに拡大画像へのリンクを設定するという使い方もできます。

JavaScirptのルール、関数、配列の基本

最近Webページの作成や更新を行うことがあり、動きのあるページを作るニーズがあるかもということで、JavaScriptの学習を始めてみることにした。Webの開発においては、ロジックを書く言語はPython、Ruby、Perl、Javaなど多様な選択肢があるが、データベースはそれより選択肢が少なく、インタフェースに相当するJavaScirptは現状一択の状況らしいので、JavaScriptを学ぶ価値はあるものと考えている。ここでは基本的な注意事項や用語を中心についてメモしておく。

<SCRIPT>～</SCRIPT>の間にコードを記述する。language="JavaScript"として、スクリプトの中身がどのような言語で書かれているかを指定する必要がある。

<SCRIPT>～</SCRIPT>の内側はさらに<!-- ～ -->で挟む必要がある。SCRIPTタグに対応していないブラウザ対策として必要となる。

行末はセミコロン(;)が必要。

JavaScriptに対応していないブラウザとして<SCRIPT>～</SCRIPT>の後ろに<NOSCRIPT>～</NOSCRIPT>を付け加える。

JavaScriptのコードを実行するタイミングを指定するために用いられるのがイベントハンドラである。イベントハンドラ="実行するJavaScript"という形式で指定する。左辺の値の代表的なものには次のようなものがある。

• onClick(要素をクリックしたとき)
• onMouseOver(マウスを要素の上においたとき)
• onLoad(ページが読み込まれたとき)

関数の書式は次の通り。関数名に使える文字は他の言語によくある仕様と同じ。i.e. 予約語を使うな、数字で始めるな、など。関数は<SCRIPT>～</SCRIPT>の間に記述すればよい。変数はvarをつけて宣言するが、省略してもOK。コメントはC言語と同じで、「//」と「/* ～ */」が利用できる。加減乗除、剰余の演算もC言語と同じようにできる。文字列の結合は"+"演算子を使う。

<SCRIPT language="JavaScript">
<!--
/*
複数行に渡るコメントを書いてみたらこんな感じになります。
複数行に渡るコメントを書いてみたらこんな感じになります。
複数行に渡るコメントを書いてみたらこんな感じになります。
*/
var x = 1; // グローバル変数宣言

function myfunc(){
  var s = 'S式'; // ローカル変数宣言
  alert('俺が' + s + 'だ!');
}
//-->
</SCRIPT>

配列の宣言は次のようになる。配列の先頭の添字は0からである。配列の要素に対し配列を入れることで2次元配列を作成することができる。

var ary = new Array(10);// 要素数10の配列
ary[0] = 4;
ary[1] = new Array(3); // 配列の配列の宣言方法
ary[1][0] = "Hello";

R言語のsubset関数の調査

とあるR使いとコードについて話をしたとき、subset関数について話が出た。データ操作でよく使われそうなものなので、どういう挙動か見てみることにする。

subset関数はベクトル、マトリックス、データフレームから条件を満たす行のみを抽出する。

使用方法は次のようになっている。

• subset(x, ...)
• subset(x, subset, ...)
• subset(x, subset, select, drop = FALSE, ...)(マトリックスやデータフレームに対して)

引数は次のような意味をもつ。

• xは部分集合を求めたいオブジェクト。ここではデータフレームなどのデータと思って差支えない。
• subsetは残しておきたい要素、行の論理値表現。欠損値はfalseとみなされる。
• selectはデータフレーム、マトリックスから抜き出したい列を選ぶ表現を書く。
• dropは添え字オペレータ[で扱えるものにする。例えば1列のマトリックスはtrueに設定すればベクトル化されることになる。
• ...にはさらに渡す引数や他のメソッドからの引数を与える。

subsetは総称的関数であり、マトリックス、データフレーム、ベクトルに対するメソッドが与えられている(リストも含む)。パッケージやユーザはさらにメソッドを追加することもできる。通常のベクトルであれば単にx[subset & !is.na(subset)]とすればよい。データフレームに対しては、引数subsetは行に対して働く。subsetはデータフレームで評価され、列は変数として(名前で)言及されることもある。引数selectはデータフレームとマトリックスに対するメソッドにおいてのみ存在する。最初に列名を対応する列番号に置き換え、得られた整数ベクトルを索引づけるために用いる。これにより、標準的な索引づけの慣習は、例えば列の範囲を簡単に特定するあるいは1列をドロップするといったことができるようにしている。引数dropはマトリックスとデータフレームに対して索引づけのメソッドに移される: マトリックスに対する既定の動作はそのような添字をつけるのとは異なる。因子は部分集合化した後には空の水準があるかもしれない: 使われていない水準は自動的に削除される。

返り値は、ベクトルであれば選ばれた要素を、データフレームやマトリックスでは選ばれた行と列を引数のxに似たオブジェクトで返す。

この関数はインタラクティブな使用を意図した便利な関数である。プログラミングでは"["のような標準的な部分集合化する関数を利用するのがよい。特に普通ではない評価をするような部分集合を求める引数では、思わぬ結果を引き起こすことになるかもしれない。

変動係数

変動係数は標準偏差を平均で割ったものである。標準偏差は不偏分散の平方根である。つまり次のような式で書くことができる。

変動係数は、単位が異なるばらつきを、単位なしに統一して見る指標と言える。例えば、4人の野球のピッチャーが投げた球の球速を130kn/h、136kn/h、140kn/h、150kn/hとしたときの変動係数と、4人のテストの受験結果が65点、68点、70点、75点であったときの変動係数は同じである。なお、変動係数は観測値が0以下の値をとらないことを前提としていることに注意。

2012年10月の学習記録

2012年10月に学習した主な本一覧。

入門・演習 数理統計(演習問題40問)

6章の推定の問題は全体的に難しい。なかなか進まぬ。特にUMVUEの問題が難しい。

カウントデータの統計解析(pp.1～70)

カウントデータというのは、平たくいうと離散型のデータです。例えば2項分布が2つあって、そこから成功確率に差があるか検定するということをしています。この本で学んだことの応用先は製薬の統計になるのかな?

基礎からのMySQL(pp.231～500、読了)

商用ならともかく、組織内でちょっとしたものを動かすという程度であれば、この本で十分なのではないかと。

これなら分かる最適化数学(pp.201～234)

非線形計画、DPなど。学習を終えてほぼ1月経って印象が薄くなってしまった感が。

HTML/XHTML&スタイルシートレッスンブック(pp.1～232)

HTMLのデザインについて。JavaScript無しでもそこそこ綺麗なウェブページが作成できるんですね。基本的なHTMLのお作法やCSSを知らなかったので、よい勉強になっています。

パーフェクトPHP(pp.1～170)

PHPの学習の続きということで少し読んでみたのですが、あまりしっくりこない...オブジェクト指向は別言語で勉強することにしようかと。

JavaScript入門講座(pp.1～228)

Webページの作成の勉強の一環として10月に読んだ本その2。動的なWebページを作る方法について、軽く学んでいます。

その他、英文ドキュメント翻訳、NHK実践ビジネス英語、TopCoderの過去問を解くなど。

TopCoder SRM438 Div2 250Pts

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

luckySetという整数の集合が与えられる。luckySetに属する2つの要素でAがBより大きく、AとBが共に正の整数である区間[A, B]は、もしAとBの間の整数がなければ不幸であると考えられる。luckySetという整数型配列と、nというluckySetの最大値を超えないような整数が与えられたとき、nを含む不幸な区間の数を返すメソッドを作成せよ。

例えば、luckySet={1, 7, 14, 10}、n=2である場合、1と7の間に2があり、2～6の整数を用いて、2を含むような区間を考えてみると、[2, 6]、[2, 5]、[2, 4]、[2, 3]の4つが該当する。

私の解答はこちら。

import java.util.Arrays;

public class UnluckyNumbers {

 public int getCount(int[] luckySet, int n) {
  for( int i=0 ; i<luckySet.length ; i++ ){
   if( luckySet[i] == n ) return 0; // Setの値があったら区間は作れないので0
  }
  Arrays.sort(luckySet); // ソートして、

  int[] between = new int[2]; // どこの間の区間にnがあるか検討する
  for( int i=1 ; i<luckySet.length ; i++ ){
   if( luckySet[i] > n ){
    between[0] = luckySet[i-1] + 1;
    between[1] = luckySet[i] - 1;
    break;
   }
  }
  if( n < luckySet[0] ){ // nがluckySetの最小値よりも小さい場合
   between[0] = 1;
   between[1] = luckySet[0] - 1;
  }
  int nInterval = 0; // 以下で区間の数を数える
  for( int i=between[0] ; i<=between[1] ; i++ ){
   if( i < n ){
    nInterval += between[1] - n + 1;
   }else if( i == n){
    nInterval += between[1] - n;
   }
  }
  return nInterval;
 }

}

得点は153.40/250、2回目のsubmitでシステムテストクリア。1回目の提出では、nがluckySetの最小値を下回る場合の処理を間違えていた。

TopCoder SRM437 Div2 250Pts

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

整数ほど美しいものは無い。整数の美しさは、10進数表記で書いたときに、含まれる異なった桁の数をいう。整数nが与えられたときに、その整数の美しさを返すメソッドを作成せよ。

私の解答はこちら。一旦文字列にして、各桁ごとに分解して集合を作成し、その集合のサイズを求めています。

import java.util.HashSet;

public class TheBeauty {

 public int find(int n) {
  String sn = "" + n;
  HashSet<Character> hs = new HashSet<Character>();
  for( int i=0 ; i<sn.length() ; i++ ){
   hs.add(sn.charAt(i));
  }
  return hs.size();
 }

}

得点は249.01/250、1回のsubmitでシステムテストクリア。問題文も実装も簡単な問題です。集合を作るときに、10で割った余りを集合に入れて、10で割ることを繰り返す方法もあります。

TopCoder SRM436 Div2 250Pts

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

あなたはソーシャルネットワークにおいて、もっとも人気のある人を決めたいと思っている。それをするために、"2-friends"というそれぞれの人が持っている数値を数えることにした。AがBという人と2-friendであるというのは、互いに友人である、あるいはAとBの間に共通の友人Cがいる状態をいう。もっとも人気のある人というのは、2-friendsの値が最大の人物のこととする (2-friendsを最大にする人が複数いることもある)。問題ではfriends[]という文字列型配列が与えられる。i番目の文字列のj番目の要素がYであれば、i番目の人とj番目の人は友人であり、Nでなければ直接の友人ではない。ソーシャルネットワークにおいて、もっとも人気のある人の2-friendsの値を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.HashSet;

public class FriendScore {

 public int highestScore(String[] friends) {
  int max = -1;
  HashSet<Integer> hs = new HashSet<Integer>();
  for( int i=0 ; i<friends.length ; i++ ){ // 各人について2-friendsを探索
   for( int j=0 ; j<friends[i].length() ; j++ ){
    if( friends[i].charAt(j) == 'Y' ){ // jはiの直接の友人か?
     hs.add(j);
     for( int k=0 ; k<friends[j].length() ; k++ ){ // iとjの共通の友人を探索
      if( k == i || k == j ) continue; // iとjは探索済(というか既に友人扱い)
      if( friends[j].charAt(k) == 'Y' ) hs.add(k);
     }
    }
   }
   max = Math.max(max, hs.size());
   hs.clear();
  }
  return max;
 }

}

得点は171.47/250、1回のsubmitでシステムテストクリア。この問題も実装より読解に時間がかかった。要は「友人」と「友人の友人」の数を探索しろと言っているのである。ああ、まぎらわしい。

TopCoder SRM435 Div2 250Pts

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

ケイトは一直線のコースの初めに、スキーの板をつけて立っている。コースはn個の同じ長さの部分からなる。pathFrictionという、コースの摩擦を表す文字列が与えられる。pathFrictionのi文字目は1から9の整数であり、コースのi番目の地域の摩擦を表している(以後、添字は0から始まるとする)。この問題では、ケイトのスキー板を1つの板として扱う。スキー板は同じ長さのm個の部分からなる。スキー板の摩擦はskiFrictionというi番目の文字が1から9という文字列でそれぞれ与えられる。これらはスキー板のi番目の位置を表している。最初に、ケイトはスキー板のi番目の部分がパスのi番目の部分に触れるように立っている。次に、ケイトはスキー板の(m-1)番目の部分がパスの(n-1)番目に触れるまで前に進む。1つの部分だけ前に進むときは、ケイトは一番遅い速度で前に移動する。1つの部分だけ前にすすむのにかかる時間というのは、スキー板の部分の数と現在いるコースの摩擦の合計で表される。ケイトがコースの最後にたどり着くまでにすべる時間の合計を返すメソッドを作成せよ。

例えば、skiFriction="45"、pathFriction="15196"であるとき、返す値は33になる。これは次のようにして計算される。スキー板は4、5という部分を持つ。板はコースは1、5という位置にある。ここで4+1、5+5というそれぞれの位置に対応させるようにして和をとる。すると、最大値は10なので、1つ前に進むのに10秒かかるということになる。次に進むと、コースは5、1になる。4+5、5+1と同様に対応する位置で和をとると最大値は9である。最後のステップでは、4+1と5+9を比較して14秒移動にかかるということになる。次のステップではpathFrictionの最後の文字を使うことになるので、移動は終了となる。以上より10+9+14=33が導出されることになる。

私の解答はこちら。

public class SkiFriction {

 public int bestPosition(String skiFriction, String pathFriction) {
  int n = 0;
  for( int i=0 ; i<pathFriction.length() - skiFriction.length() ; i++ ){
   int max = -1;
   for( int j=0 ; j<skiFriction.length() ; j++ ){
    int s = skiFriction.charAt(j) - '0';
    int p = pathFriction.charAt(i+j) - '0';
    max = Math.max(max, s+p);
   }
   n += max;
  }
  return n;
 }

}

得点は222.02/250、1回のsubmitでシステムテストクリア。私にとっては実装は楽でしたが、読解がしんどい一問でした。問題設定が現実的でなく、想像しづらいためかと思います。

TopCoder SRM434 Div2 250Pts

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

5つの正の整数が与えられたとき、least majority multipleというのは、5つの与えられた数のうち、3つ以上で割り切れる最小の正の整数を指す。a, b, c, d, eという5つの異なる値を取る正の整数が与えられたとき、least majority multipleを返すメソッドを作成せよ。

私の解答はこちら。

public class LeastMajorityMultiple {

 public int leastMajorityMultiple(int a, int b, int c, int d, int e) {
  int num = 1;
  while( true ){
   int divisible = 0;
   if( num % a == 0 ) divisible++;
   if( num % b == 0 ) divisible++;
   if( num % c == 0 ) divisible++;
   if( num % d == 0 ) divisible++;
   if( num % e == 0 ) divisible++;
   if( divisible >= 3) return num;
   num++;
  }
 }

}

1から順にカウントしていけばよいだけなので、工夫の余地はあまりないかな。しいて言うなら、5つの整数がすべて値が異なるという条件から、必ず返す値は3以上になるので、num = 3から探索を開始すればよいのではと思います。

TopCoder SRM433 Div2 250Pts

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

かつて数学がいつも大問題となっている王国があった。王家の会計のポストを充足しなければならいというときに、応募者には以下の問題が与えられた。「AとBという二つのN個の要素を持つ整数型の配列が与えられる。AとBに関する関数SをS = A0*B0 + … + AN-1*BN-1と定義する。Sをできるだけ小さくするようにAを並び替えよ。Bについては並び替えを認めないものとする。問題作成者は応募者の解答が正しいかチェックするようなプログラムを書くことに迫られた。A、Bという配列が与えられたとき、Sの取り得る最小値を返すようなメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class RoyalTreasurer {

 public int minimalArrangement(int[] A, int[] B) {
  Arrays.sort(A);
  Arrays.sort(B);
  for( int i=0 ; i<A.length/2 ; i++ ){
   int tmp = A[i];
   A[i] = A[A.length-i-1];
   A[A.length-i-1] = tmp;
  }
  int sum = 0;
  for( int i=0 ; i<A.length ; i++ ){
   sum += A[i]*B[i];
  }
  return sum;
 }

}

得点は246.01/250、1回のsubmitでシステムテストクリア。Sが最小値を取るのはAを降順、Bを昇順に並び替えて、添字が同じものを順に掛け算したときになります。Bを並べ替えるなと言っても、並べ替えた方が簡単というちょっと意地悪な問題。

TopCoder SRM432 Div2 250Pts

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

単語の各文字について、出現形式が1つの列からなる場合に限り、単語はまとめられているという。言い換えれば、1つ以上の文字が2ヶ所に分かれて出現しないということである。例えば、"code"はまとめられているといえるが、"aabbbccb"はbが2ヶ所に現れているので、まとめられているとは言わない。さて、words[]という文字列型配列が与えられたとき、そのなかでまとめられている文字列の数を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.ArrayList;

public class GroupedWordChecker {

 public int howMany(String[] words) {
  int nGrouped = 0;
  ArrayList<Character> al = new ArrayList<Character>();
  for( int i=0 ; i<words.length ; i++ ){
   char lastChar = words[i].charAt(0); // 直前の文字
   boolean isGrouped = true;
   al.add(lastChar);
   for( int j=0 ; j<words[i].length() ; j++ ){
    char c = words[i].charAt(j); // 現在の文字
    if( lastChar == c ) continue;
    lastChar = c; // 新しい文字が出てきたと判定
    if( al.contains(c) ){ // もし既に登場した文字だったなら「まとめられているとは言えない」
     isGrouped = false;
     break;
    }else{ // 未登場の文字なら出現済み文字として登録
     al.add(c);
    }

   }
   if( isGrouped ) nGrouped++;
   al.clear(); // 次の単語を判定するためにリストの中身を空にする
  }
  return nGrouped;
 }

}

得点は229.71/250、1回のsubmitでシステムテストクリア。

POST送信とGET送信の違い

Webページからテキストボックスなどに入力したデータを別のプログラムに渡す方法は、POST送信とGET送信がある。これらの違いは次のようになっている。

POST送信

• データはURLには付けない
• 送信できるデータはテキスト、バイナリのどちらでもよい

GET送信

• URLにデータを付けて送る
  • つまり、https://www.google.co.jp/search?q=googleのように、?に続けてデータをくっつけているということである。POST送信では?以降がURLに現れることはない。
• テキストのみ送信可能
• FORM宣言時に指定しなければGETが使われる
  • セキュリティのことを考えるとGET送信よりもPOST送信の方が安心できる。FORMタグで作成したフォームで、何も指定しないとGET送信になるので、POST送信にする場合はMETHOD="POST"のように属性を指定する必要がある。

2012年9月の学習記録

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

入門・演習 数理統計(pp.161～222、演習問題74問)

収束の性質や順序統計量、十分統計量、指数型分布族について。復習を兼ねてスライドでまとめて紹介したいところ。この調子だと読み終えるのは11月上旬ぐらいになってしまうかなと予想。UMVUEの節で苦戦中。

基礎からのMySQL(pp.1～231)

ウェブシステムを作ろうとしているので、その一環として読書開始。PHPをテキスト後半で学ぶことになる。新しい構文が出てくるたびに、SQLのコードを考えながら打ち込むことになるので、よい訓練になっている。これは読みやすい。年度末までに、Webアプリを作って公開しよう!と考えている。PHP+Pythonぐらいでアイディアを実装できないかなと(何をするかはまだ内緒)。

これなら分かる最適化数学(pp.97～200)

EMアルゴリズムの導出をはじめて見ました。この辺りに演習があると言う事無しなんですけれどね。

SciPy lecture note(pp.1～130)

Pythonで数値計算の練習を兼ねて日本語版を読んでみた。英語版は定期的にアップデートされているようなので、英語が読めるなら、そちらを読んだ方がよいでしょう。

Webアプリケーション構築入門(pp.1～84)

うーん、ちょっと進み方が唐突すぎるかな。テキストとしては基礎からのMySQLぐらいの進み方の方が楽で読みやすいです。Web開発というと、Apacheやセキュアなプログラミング、データベースなど、覚えることが大量にあって結構キツイです。

その他、NHK実践ビジネス英語、情報セキュリティスペシャリスト試験の過去問題、TopCoderの過去問を解くなど。そろそろサーバのいじり方を学ばないといけないかな...?

TopCoder SRM431 Div2 250Pts

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

ある正の整数がmega cool numberであるというのは、その桁が等差数列を形成しているときにそう呼ばれる。Nを与えたとき、1以上N以下の間の整数でmega cool numberとなる整数の数を返せ。

例えば123は初項1、公差1の等差数列なのでmega cool numberになることを意味している。

私の解答はこちら。

public class MegaCoolNumbersEasy {

 public int count(int N) {
  if( N<=99 ) return N;
  int n = 99;
  for( int i=100 ; i<=N ; i++ ){
   String nstr = "" + i;
   int diff = nstr.charAt(0) - nstr.charAt(1);
   boolean isCool = true;
   for( int j=1 ; j<nstr.length()-1 ; j++ ){
    if( nstr.charAt(j) - nstr.charAt(j+1) != diff ){
     isCool = false;
     break;
    }
   }
   if( isCool ) n++;
  }
  return n;
 }

}

得点は216.90/250、1回のsubmitでシステムテストクリア。問題文を理解する方が実装よりも時間がかかっています。

TopCoder SRM430 Div2 275Pts

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

あなたの語学学校は新しいセメスターを始めていて、各生徒は時間割を決めなければならない。groups[]というi番目の要素がi番目のスケジュールの受講者数を表す整数型の配列が与えられる。学校には各スケジュールに割り当てられる受講生の数はminSize以上maxSize以下でなければならないというルールがある。しかしながら、このルールは登録段階では適切に満たされていない。あなたのやることはルールが満足されるように学生のスケジュールを割り当てなおすことである。再割り当てというのは、ある学生の受講スケジュールを別の時間に振り変えることである。さて、再割り当てしなければならない学生の人数の最小値を返すメソッドを作成せよ。ただし、もしそのようなルールを満たすことができなければ-1を返すこと。スケジュールを新しく加えたり、存在しているスケジュールは削除しないことにも注意。

私の解答はこちら。

public class CreateGroups {

 public int minChanges(int[] groups, int minSize, int maxSize) {
  int[] range = new int[2];
  range[0] = minSize * groups.length;
  range[1] = maxSize * groups.length;
  int total = 0; // 総受講者数
  for( int i=0 ; i<groups.length ; i++ ){
   total += groups[i];
  }
  // -1になるのは受講者数の合計がminSize*授業数未満、あるいは
  // maxSize*授業数より大きいをみたすときである。
  if( total < range[0] || total > range[1] ) return -1;
  int[] diff = new int[2];
  for( int i=0 ; i<groups.length ; i++ ){
   if( groups[i] < minSize ){
    diff[0] += minSize - groups[i];
   }else if( groups[i] > maxSize ){
    diff[1] += groups[i] - maxSize;
   }
  }
  // 最少の再割り当て人数は少ない方に埋めなければならない人数と
  // 多い方で減らさなければならない人数の大きい方になる。
  return Math.max(diff[0], diff[1]);
 }

}

得点は176.84/250、1回のsubmitでシステムテストクリア。最後のコメントにあるアイディアを思いつくのに時間がかかりました。

TopCoder SRM429 Div2 250Pts

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

AAAAとBBというポリオミノ(複数の正方形をつなげた図形)が無限に与えられている。"."あるいは"X"という文字で埋められたregionという文字列が与えられる。あなたはこれに対し、Xという文字を与えられたポリオミノで隙間なく覆わなければならない(ポリノミオが重なってもならない)。残された"."はいじることなく、Xという文字はAあるいはBという文字で覆った結果の文字列を返すようにせよ。もし、そのような結果が返せないようであれば、"impossible"という文字列を返せ。もし、複数の解答があるようであれば、辞書順で値が最も小さくなるような文字列を選ぶようにせよ。

私の解答はこちら。

public class LinearPolyominoCovering {

 public String findCovering(String region) {
  StringBuilder sb = new StringBuilder();
  int nX = 0;
  for( int i=0 ; i<region.length() ; i++ ){
   if( region.charAt(i) == '.' ){
    if( nX % 2 != 0 ) return "impossible";
    while( nX > 0 ){
     if( nX >= 4 ){
      sb.append("AAAA");
      nX -= 4;
     }else if( nX >=2 ){
      sb.append("BB");
      nX -= 2;
     }
    }
    sb.append('.');
    continue;
   }else{
    nX++;
   }
  }

  if( nX % 2 != 0 ) return "impossible";
  while( nX > 0 ){
   if( nX >= 4 ){
    sb.append("AAAA");
    nX -= 4;
   }else if( nX >=2 ){
    sb.append("BB");
    nX -= 2;
   }
  }
  return sb.toString();
 }

}

得点は229.55/250、1回のsubmitでシステムテストクリア。辞書順で値が最小になるというのは、できるだけAでregionを埋めろということに言い換えればOKです。同じコードが繰り返しているので、そこはリファクタリングの余地があるかもしれません(速度を競う競技プログラミングではリファクタリングしている余裕が無いといえば無いのですが)。

TopCoder SRM428 Div2 250Pts

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

ジョンとブラスは文字列の理論について大学で学んでいる。ブラスはパリンドローム(訳注：回文のこと)が大好きである。パリンドロームというのは前からも後ろからも同じように読める単語のことである。ジョンはsという文字列を受け取った時に、0文字以上の文字をsの後ろにつけてパリンドロームを作ることで、ブラスを驚かせたいと思っている。ジョンはパリンドロームはできるだけ短くしたいと考えている。sという文字列が与えられたとき、ジョンが生成できるもっとも短いパリンドロームの文字列の長さを返すメソッドを作成せよ。

私の解答はこちら。

public class ThePalindrome {

 public int find(String s) {
  StringBuilder sb = new StringBuilder(s);
  String rev = sb.reverse().toString(); // sをひっくり返した単語
  for( int i=0 ; i<s.length() ; i++ ){
   String s1 = s.substring(i, s.length()); // sの先頭i文字目以降と
   String s2 = rev.substring(0, rev.length()-i); // ひっくり返した文字列の最後の方を比較して
   if( s1.equals(s2) ) return s.length() + i; // 一致したときの最短パリンドロームの長さを返す
  }
  return s.length()*2-1;
 }

}

得点は243.03/250、1回のsubmitでシステムテストクリア。ひっくり返した文字列との比較の方法がポイント。

TopCoder SRM427 Div2 250Pts

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

女の子が好きな男の子の一人とデートしたいと思っているが、誰を選んでいいか分かっていない。幸いにして、女の子はLove Calculatorという、二人が愛し合っている確率を計算できるものを持っている。Love Calculatorは二人の名前を受け取り、以下のアルゴリズムに沿って、愛し合っている確率を計算する。

• Lは二人の名前に登場する'L'の出現回数
• Oは二人の名前に登場する'O'の出現回数
• Vは二人の名前に登場する'V'の出現回数
• Eは二人の名前に登場する'E'の出現回数

以上のように置いたとき、二人の愛し合っている確率は((L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E))%100で求めることができる。女の子の名前を表すgirlという文字列型変数と、彼女の好きな男の子の名前が含まれるboys[]という配列が与えられたとき、女の子と最も愛し合っている可能性が高い男の子の名前を返すメソッドを作成せよ。もし、複数の男の子が候補にある場合は、アルファベット順に並べたとき最初に来る名前を返すようにすること。

私の解答はこちら。

public class LoveCalculator {

 public String findBoy(String girl, String[] boys) {
  long maxprob = -1;
  int[] freq_girl = new int[4]; // LOVEという文字の出現回数を記録

  String bestBoy = "";
  for( int i=0 ; i<girl.length() ; i++ ){
   if( girl.charAt(i) == 'L' ) freq_girl[0]++;
   if( girl.charAt(i) == 'O' ) freq_girl[1]++;
   if( girl.charAt(i) == 'V' ) freq_girl[2]++;
   if( girl.charAt(i) == 'E' ) freq_girl[3]++;
  }
  for( int i=0 ; i<boys.length ; i++ ){
   int[] freq_boy = new int[4];
   for( int j=0 ; j<[i].length() ; j++){
    if( boys[i].charAt(j) == 'L' ) freq_boy[0]++;
    if( boys[i].charAt(j) == 'O' ) freq_boy[1]++;
    if( boys[i].charAt(j) == 'V' ) freq_boy[2]++;
    if( boys[i].charAt(j) == 'E' ) freq_boy[3]++;
   }
   int[] fr = new int[freq_girl.length];
   for( int j=0 ; j<.length ; j++ ){
    fr[j] = freq_girl[j] + freq_boy[j];
   }
   long prob = ((fr[0]+fr[1])*(fr[0]+fr[2])*(fr[0]+fr[3])*
                (fr[1]+fr[2])*(fr[1]+fr[3])*(fr[2]+fr[3]))%100;
   if( prob > maxprob ){
    bestBoy = boys[i];
    maxprob = prob;
   }else if( prob == maxprob ){
    if( bestBoy.compareTo(boys[i]) > 0 ){
     bestBoy = boys[i];
    }
   }
  }
  return bestBoy;
 }

}

点数は183点台でした。配列よりもハッシュの方が綺麗に書けるんでしょうかね。probを計算するときは、6つの値を順に掛ける度に100で割っておけばオーバーフローを気にしなくてもよさそうです。すべて掛け算すると、最大で40^6まで値を取り得るので、上の実装では念のためlongにしています。

Pythonで独自ソートの実装

Pythonのリストにあるsortメソッドは、自然な順序でソートしてくれるものであるが、そうではないソートを行いたいときがある。そのようなソートを行うには、sortメソッドに比較のための関数を渡してやればよい。まずは、比較によく用いられる関数を見てみよう。

>>> help(cmp)
Help on built-in function cmp in module __builtin__:

cmp(...)
    cmp(x, y) -> integer
    
    Return negative if xy.
>>> help(list.sort)
Help on method_descriptor:

sort(...)
    L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;
    cmp(x, y) -> -1, 0, 1
>>> help(sorted)
Help on built-in function sorted in module __builtin__:

sorted(...)
    sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list

cmp関数は2つの引数を評価した結果を返すというものである。第1引数が第2引数より小さければ負、同じなら0、大きければ正の値を返すようになっている。

リストのsortメソッドには3つの引数を与えることができる。cmpは比較のための関数である。keyはソートの基準となる対象を指定するものである。例えば文字列のソートで2文字目以降でソートしたいという場合にはlambda x:x[1:]とすることになる。この場合、xはソート対象となるオブジェクトに相当する。reverseは昇順・降順を指定するものである。デフォルトでは昇順に並べることになる。

sortedは反復可能なオブジェクトであれば、ソートすることができる。例えば、辞書のvalueで辞書をソートするときにはこれを利用するとよい。cmpなどのオプションはlist.sortと同様の意味を持つ。

これを踏まえて、以前Javaでも書いた文字列の長さ順にソートするということを行ってみる。なお、sortメソッドはstable sort(安定なソート)なので、同じ値(=文字列の長さが同じ)が複数ある場合は、先に出てきたものが先に並べられるようになっている。

# -*- encoding: utf-8 -*-

def cmp_len(s1, s2):
    return cmp(len(s1), len(s2)) # 文字列の長さで比較するための関数

langs = ["Python", "LISP", "Haskell", "C", "Java"]

langs.sort(cmp=cmp_len, reverse=True)
print langs #徐々に文字列の長さが短くなっていくリストになる

dic = {"NumPy":"numerical analysis",
       "sphinx":"documentation generator",
       "django":"web"}

sdic = sorted(dic.items(), cmp=cmp_len, key=lambda x:x[1])
# 説明文が短い順に並べ替えられている
print sdic

表示される結果は次の通り。

['Haskell', 'Python', 'LISP', 'Java', 'C']
[('django', 'web'), ('NumPy', 'numerical analysis'), ('sphinx', 'documentation generator')]

TopCoder SRM425 Div2 250Pts

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

nという正の整数がproper factorであるというのは、nがaの倍数で、かつaが1でもnでもないということを指す。ある数nのproper factorのすべての要素が含まれている、factors[]という2以上の整数が含まれるリストが与えられる。このとき、nを求めて返すメソッドを作成せよ。

私の解答はこちら。

public class InverseFactoring {

 public int getTheNumber(int[] factors) {
  long proper = 1;
  long max = -1;
  long min = Long.MAX_VALUE;
  for( int i=0 ; i<factors.length ; i++ ){
   proper = lcm(proper, factors[i]); // 全部の数の最小公倍数を計算
   max = Math.max(max, factors[i]);
   min = Math.min(min, factors[i]);
  }
  // factorの全要素の最小公倍数が最大値そのものになったら、
  // 最大値はproper factorではないので、最小値だけ掛けてproper factorを求める。
  return proper == max ? (int)proper * (int)min : (int)proper;
 }

 static long gcd(long a, long b){ // 最大公約数
  return b == 0 ? a : gcd(b, a % b);
 }

 static long lcm(long a, long b){  // 最小公倍数
  return a * b / gcd(a, b);
 }
}

得点は200.54/250、2回目のsubmitでシステムテストクリア。仮定としてfactorsは妥当なものしか入らないので、上のような実装は不要で、factorsの最小値*最大値で導出ができるとのこと。

ウォリスの公式

PythonでWallisの公式を書いてみました。Wallisの公式は円周率を多項式を利用して近似するものです。元ネタはPython Scientific lecture noteの英語版(2012年8月リリース)19ページの練習問題になります。実行結果を見てみると、引数の値を大きくするにつれて、円周率に近づいている様子が確認できます。ちなみにnumは数字というよりもnumerator(分子)のつもりです、念のため。

def wallis_formula(n):
    mypi = 1
    for i in range(1, n):
        num = 4*(i**2)
        mypi *= float(num)/(num-1)
    return 2 * mypi

'''
>>> wallis_formula(1000)
3.1408069608284657
>>> wallis_formula(10000)
3.1415141108281714
>>> wallis_formula(100000)
3.141584799578707
>>> wallis_formula(1000000)
3.1415918681913633
'''

TopCoder SRM424 Div2 250Pts

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

古代の呪文を含んだspellという文字列が与えられる。その呪文は暗号化されているいるが、暗号はかなり単純なものである。呪文を解読するために、AとZという文字をすべて見つける必要がある。そして、その順序を判断させるのである。例えば、暗号化された文字列が、"AABZCADZA"であれば、AとZを見つけ出し、それらの順序(A->A->Z->A->Z->A)を反転させて、"AZBACZDAA"という解読結果を得る(AとZの位置だけに注目すると反転していることが分かる)。与えられたspellという文字列に対し、解読した結果得られる文字列を返すようなメソッドを作成せよ。

私の解答はこちら。

import java.util.ArrayList;

public class MagicSpell {

 public String fixTheSpell(String spell) {
  // 出現した文字と出現した位置を記録しておく
  ArrayList<Character> list = new ArrayList<Character>();
  ArrayList<Integer> pos = new ArrayList<Integer>();
  for( int i=0 ; i<spell.length() ; i++ ){
   char c = spell.charAt(i);
   if( c == 'A' || c == 'Z' ){
    list.add(0, c); // 0の位置にcを入れることでAとZの出現順序を反転させている
    pos.add(i);
   }
  }
  StringBuilder sb = new StringBuilder();
  int idx = 0;
  for( int i=0 ; i<spell.length() ; i++ ){
   if( idx == pos.size() ){ // 全部AとZが出てきたら終了
    sb.append(spell.substring(i));
    break;
   }
   if( pos.get(idx) == i ){
    sb.append(list.get(idx));
    idx++;
   }else{
    sb.append(spell.charAt(i));
   }
  }
  return sb.toString();
 }

}

得点は150.26/250、3回目のsubmitでシステムテストクリア。中央値は約229点。idxが最後まで来た時にbreakで終了するように仕向けないと、pos.get(idx)の評価でエラーを起こすことに気付かず嵌る。

Pythonでクイックソート実装

Scipyを学習するためのノートPython Scientific lecture notesというものが公開されています。英語版pdfはこちらの右上にあるDownloadsのところにあるpdfへのリンクを、日本語版pdfはこちらの上部にある印刷用のダウンロード書かれた横のpdfへのリンクをクリックすると読むことができます。ただし、(記事執筆時点では)日本語版は最新版ではないようです。

本日は英語版のノート24ページにある、Wikipediaのクイックソートの説明文(擬似コード)を実際のプログラムに変換せよという問題を解いてみました。以下、私の解答です。

# -*- encoding: utf-8 -*-

def quick_sort(array):
    if len(array) < 2:
        return array
    # 特に指定が無いのでほぼ中央の位置にある値をピボットとする
    pivot = array.pop(len(array)/2)
    less = []
    greater = []
    for x in array:
        if x < pivot + 1:
            less.append(x)
        else:
            greater.append(x)
    return quick_sort(less) + [pivot] + quick_sort(greater)

ピボットの選び方は簡単のため、リストの中央の位置にある値にしていますが、それ以外にも方法があります。例えば、中央の位置と両端の3つの値に対する中央値をピボットにするという方法があります。これは、クイックソートの性能はピボットの選び方に依存するためです。

極端ではありますが、毎回ピボット以下の値になるグループのデータ数が0、ピボットより値が大きいグループのデータが残り全部となった場合に効率が悪くなります。この場合、ソートのオーダはデータ数をnとしたときO(n^2)になります(1個ずつソート済になるため、バブルソートなどのソートと同じ程度の計算量になる)。クイックソートのオーダは平均してO(n*log(n))となるので、nが大きいとき非効率になってしまいます。

データを大きいもの、小さいもので半分ずつに分けられるようなピボットを選ぶのが理想的なのですが、データを大量に利用してピボット選択の計算をすること自体にも時間がかかってしまいます。このようなときは、ソートしたいデータの性質に依存したピボット選択を考えましょう。例えば、ほぼ昇順であるが、数パーセントのノイズが入ってくるデータの場合は、数パーセントのノイズには目をつぶって、中央の位置にある値(=ほぼ中央値と期待される)をピボットにするという方針を選ぶことが考えられます。

2012年9月14日追記

データの破壊はないほうがよいということなので、popメソッドを利用しない方針で書き直してみました。

# -*- encoding: utf-8 -*-

def quick_sort2(array):
    if len(array) < 2:
        return array
    # 特に指定が無いのでほぼ中央の位置にある値をピボットとする
    pivot_pos = len(array)/2
    pivot = array[pivot_pos]
    less = []
    greater = []
    for idx, x in enumerate(array):
        if idx == pivot_pos: continue
        if x < pivot + 1:
            less.append(x)
        else:
            greater.append(x)
    return quick_sort(less) + [pivot] + quick_sort(greater)

Rで実験計画法 後編

4ヶ月ほど前に開かれたTokyo.R #22にて発表に利用した、実験計画法の話題に関する後編のスライドです。ソフトウェアのテストと絡めて、直交表の使い方などについて話をしてきました。前編についてはこちらからご覧ください。

Rで実験計画法 後編 from itoyan110

TopCoder SRM423 Div2 250Pts

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

n*nの盤面とその上にいくつかチェッカーの駒がある。i番目の駒は盤面のx[i]行、y[i]列のセルにある。すべての座標は1から始まるものとする。一つのセルには複数の駒がある可能性もある。一つの駒を動かすことは、駒を座標の上下左右に動かすことからなるものとする。あなたは各駒を盤面の4つの角に置きたいと思っている。その目標を達成するのに必要な最小の移動回数を返すメソッドを作成せよ。

私の解答はこちら。

public class TheSimpleGame {

 public int count(int n, int[] x, int[] y) {
  int nMove = 0;
  for( int i=0 ; i<x.length ; i++ ){
   int xx = x[i]-1 < n-x[i] ? x[i]-1 : n-x[i]; // x座標方向の最小移動量
   int yy = y[i]-1 < n-y[i] ? y[i]-1 : n-y[i]; // y座標方向の最小移動量
   nMove += (xx + yy);
  }
  return nMove;
 }

}

得点は236.60/250、1回のsubmitでシステムテストクリア。中央値は約229点。

TopCoder SRM422 Div2 250Pts

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

ある数字がmulti numberであるというのは、その数字の10進数の表現を2つの数字に分けたときに、二つの数字の各桁の積が等しくなるものがあるということである。例えば、1221という数字は12と21に分ければ、各桁の積は共に2となり、これはmulti numberである。同様に1236もmulti numberとなるが（訳注：123と6に分ければよい）、1234はそうはならない。なお、2つの数に分けるとき、どちらの数も少なくとも1桁以上でなければならないことに注意。つまり12345という数字があれば、1-2345, 12-345, 123-45, 1234-5という4通りの分け方が存在することになる。さて、numberという数字が与えられたとき、multi numberであれば、"YES"、そうでなければ"NO"を返すようなメソッドを作成せよ。

私の実装はこちら。

public class MultiNumber {

 public String check(int number) {
  String snum = "" + number;
  for( int i=1 ; i<snum.length() ; i++ ){
   int left = multiplyDigits(snum.substring(0, i));
   int right = multiplyDigits(snum.substring(i));
   if( left == right ) return "YES";
  }
  return "NO";
 }

 private int multiplyDigits(String s){ // 分けられた数字の各桁の積を計算
  int ret = 1;
  for( int i=0 ; i<s.length() ; i++ ){
   ret *= (s.charAt(i) - '0');
  }
  return ret;
 }
}

得点は241.10/250、1回のsubmitでシステムテストクリア。中央値は約169点。

TopCoder SRM421 Div2 250Pts

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

あなたはジムにおり、トレーニングをしたいと思っている。トレーニングは1分間単位に分けられる。1分間ごとに、運動あるいは休憩のどちらかを取ることができる。もし、トレーニングを1分間することにすれば、心拍数がtrainChangeだけ上昇する。つまり、もし、ある時点での心拍数がXであれば、運動した1分後にはX+trainChangeになｒということである。心拍数はmaxPulseという上限を超えて欲しくはないので、X+trainChangeがmaxPulse以下になるときに限って運動を行うことができる。もし、1分間休憩することにすれば、restChangeだけ心拍数を下げることになる。つまり、ある時点の心拍数がXであれば、休憩を1分した後には心拍数がX-restChangeになるということである。しかしながら、心拍数はminPulseを下回ることはなく。X-restChangeがminPulse未満になるようであれば、心拍数はminPulseになる。初期状態におけるあなたの心拍数をminPulseとする。そして、needToTrainという時間だけ運動を行いたいものとする(連続で行う必要はない)。それだけのトレーニングを行うのに最小限必要となる時間を返すメソッドを作成せよ。なお、needToTrain分間の運動ができないようであれば、-1を代わりに返すようにすること。

私の実装はこちら。

public class GymTraining {

 public int trainingTime(int needToTrain, int minPulse, int maxPulse, int trainChange, int restChange) {
  int currentPulse = minPulse;
  int currentTime = 0;
  int currentTrainTime = 0;

  // 失敗する場合の条件チェック
  if( minPulse + trainChange > maxPulse ) return -1;
  while( true ){
   // 休憩と運動の選択
   // maxPulseを上回らないようであれば、運動を選択することで、時間を最小化できる
   if( currentPulse + trainChange <= maxPulse ){
    currentPulse += trainChange;
    currentTime++;
    currentTrainTime++;
    if( currentTrainTime >= needToTrain ) break;
   }else{
    int next = currentPulse - restChange;
    currentPulse = next >= minPulse ? next : minPulse;
    currentTime++;
   }
  }
  return currentTime;
 }

}

得点は230.67/250、1回のsubmitでシステムテストクリア。中央値は約188点。

TopCoder SRM420 Div2 500Pts

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

あなたは大みそかをとても楽しみにしている。次の大みそかはそんなに遠くなく、あなたはそれを楽しみにしている。そして、ある日、ある疑問で目が覚めることになる。「待てよ、大みそかはどのぐらい離れているんだ?」

この質問に答えるため、今年がどの程度終わったかを示すプログレスバーという、簡単なアプリケーションを作成することにした。この問題においては、目標はこのアプリケーションのもっとも重要なパートを実装することである。つまり、現在時刻を示すcurrentDateという文字列を受け取ったときに、百分率でその年の進捗状況を返すというものである。currentDateという変数は"Month DD, YYYY HH:MM"という文字列で与えられる。ここで、Monthは月の名前を表し、YYYYは西暦、DD、HH、MMは日、時間、分を二桁の数値で表したものである。なお、0埋めされる可能性がある(訳注：例えば5月の場合MMは05ということになる)。

私の実装はこちら。

public class YearProgressbar {

 public double percentage(String currentDate) {
  int[] days = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  // 現在時刻の解釈
  String[] date = currentDate.split(" ");
  int year = Integer.parseInt(date[2]);
  int month = monthInt(date[0]);
  int day = Integer.parseInt(date[1].substring(0, 2));
  int hour = Integer.parseInt(date[3].substring(0, 2));
  int minutes = Integer.parseInt(date[3].substring(3));
  boolean leap = isLeap(year); // 今年はうるう年か?
  int daysInYear = leap ? 366 : 365;
  int secondsInYear = daysInYear * 24 * 3600; // 1年間の秒数

  int alreadyPassedDays = 0;
  for( int i=0 ; ilt;month ; i++ ){
   alreadyPassedDays += days[i];
   if( leap && i == 1 ) alreadyPassedDays++; // 経過した日数を計算
  }
  int alreadyPassedSeconds = minutes * 60 + hour * 3600 +
          (day - 1 + alreadyPassedDays) * 24 * 3600 ; // 今年の経過秒数を求めている
  return alreadyPassedSeconds * 1.0 / secondsInYear * 100;
 }

 private boolean isLeap(int year){
  if( year % 400 == 0 || (year % 4 == 0 && year % 100 != 0) ){
   return true;
  }
  return false;
 }

 private int monthInt(String month){ // monthという文字列から月の値を返す。失敗すれば-1。
  String[] monthString = {"January", "February", "March", "April", "May", "June",
            "July", "August", "September", "October", "November", "December"};
  for( int i=0 ; i<monthString.length ; i++ ){
   if( month.equals(monthString[i]) ){
    return i;
   }
  }
  return -1;
 }
}

得点は315.02/500、1回のsubmitでシステムテストクリア。中央値は150点。愚直な実装ではありますが、これで問題なし。分単位までで良かったので、秒単位に変換する必要はありませんでしたね。

2012年8月の学習記録

2012年8月に学習した主な本一覧。

情報セキュリティスペシャリスト試験のテキスト(pp.89～211、249～284)

10月の試験に向けて、テキストを読書中。気になったことを気軽に実験しやすい分野であれば、もう少し学びやすくもなりそうなものですが。攻撃を実際に試すというわけにもいかないですし(苦笑)。

入門・演習 数理統計(pp.97～161、演習問題74問)

確率変数の分布に関する性質について学ぶ。前章の確率変数変換の知識を利用して分布関数を導出する方法が頻出。負の二項分布、超幾何分布など、あまり聞きなれない分布がどのようなものか理解できた。また、それぞれの分布がどのような関係にあるかということについて、代表的なものについて知ることができた。

テキストデータの統計科学入門(pp.135～233、読了)

後半はちょっと詰め込みすぎかな?あまり手の動かしようがなかった。

これなら分かる最適化数学(pp.1～97)

ヘッセ行列が今まで天下り式に与えられていたのを利用していたが、この本でなぜヘッセ行列で極値判定ができるかを理解できた。順を追って理解させるようにしている。一からやるなら、なかなかの良書。

統計解析入門（pp.148～192)

推定、検定の手法について。

入門自然言語処理(pp.111～186、演習問題34問)

第3章では正規表現の他、トークン化、生テキストの文分割などの手法について学んだ。第4章は一般的なプログラミングの技法に関しての内容で、プログラムの基本的な話題が多め。

初めてのPython(第27章)

例外について。with～as構文は初見でした。

その他、NHK実践ビジネス英語を聞く、情報セキュリティスペシャリスト試験の過去問題を解くなどした。プログラミングに関しては、PythonでMecab(形態素解析ソフト)を動かす方法の調査の他、Project Euler、TopCoderの過去問を解いている。

TopCoder SRM420 Div2 250Pts

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

カードのデッキがある。それぞれのカードは黒ないしは赤である。以後、Bという文字を黒のカード、Rという文字を赤のカードとする。デッキの上から下に向かってカードを並べることによって、deckという文字列を生成する(訳注：つまり、deckの中身はRとBという文字列を利用して構成する)。次に、deckのすべてのカードを挿入して新しいデッキを作成したい。まず始めに、新しいデッキは空であるとする。次に古いデッキの上から下に向かってカードを処理していく。deckのi文字目に対応するカードを処理するというのは、古いデッキからカードを取り出し、新しいデッキにabove[i]だけ上にカードがある位置にカードを挿入するということになる。

deckという古いデッキと、above[]という新しいデッキへの挿入位置が与えられたとき、deckと同様な形式の文字列に変換された新しいデッキを表す文字列を返すメソッドを作成せよ。

例えばdeck="BRBRR"、above={0, 0, 1, 0, 3}であれば、"RRBRB"となる。これは初めにBを挿入(状態：B)、次に上に0枚がある位置にRを挿入(状態：RB)、次に上に1枚ある位置にBを挿入(状態：RBB)、...とすることによって得られる結果である。

私の実装はこちら。

public class DeckRearranging {

 public String rearrange(String deck, int[] above) {
  String ret = "";
  for( int i=0 ; i<above.length ; i++ ){
   String first = ret.substring(0, above[i]); // 新しいdeckを分けたときに上にあるカード群
   String second = ret.substring(above[i]); // 新しいdeckを分けたときに下にあるカード群
   ret = first + deck.charAt(i) + second; // 新しいdeckにカードを挟み込む
  }
  return ret;
 }

}

得点は221.63/250、1回のsubmitでシステムテストクリア。中央値は約212点。StringBufferのinsertを利用するのもいいかもしれません。

ニュートン法による極値計算

テキスト「これなら分かる最適化数学」の86ページにあるニュートン法をPythonで実装した。通常のニュートン法は関数f(x)に対し、f(x)=0なるxを求める反復計算を行うものであるが、反復の式を少し変更するだけで、極値(f'(x)=0なるx)を求めることができる。詳しい理論はテキストに譲るが、x <- x - f'(x)/f''(x)とし、収束するまで繰り返せば、極値にたどり着くことができる。

ニュートン法で極値を求めるにあたり、注意しなければならないのは、コードの更新式からも見当がつくが、途中で2回微分が0にならないようにすることである。

以下、f(x)=x^3-2*x^2+x+3に対して、極値が求まるか試してみた。なお、f(x)が極値をとるxの値は解析的に解くこともでき、x=1、1/3の2つとなる。

# -*- encoding: utf-8 -*-

'''
ニュートン法による極値の計算
2回微分が存在する場合、勾配法よりも効率よく極値を計算できる
'''

from sympy import * # 微分操作のために必要
import itertools as it # mapで複数の引数を与えたいので利用する

def newton(init, vari, func, delta=10**-6):
    '''
    funcは極値を探す対象の関数、variは微分する変数、deltaは収束判定のための定数
    返す値は見つかった極値の1つである
    '''
    df = diff(func, vari)
    d2f = diff(df, vari)
    x = init
    while True:
        xvar = x
        # 2回微分の微分係数が0にならないように注意が必要
        x = xvar - float(limit(df, vari, xvar)) / float(limit(d2f, vari, xvar))
        if abs(x - xvar) < delta:
            break
    return round(x, 5) # deltaの値によって有効桁数が変わるが、簡単のため5で決めうち

x = Symbol('x')
f = x**3 - 2*x**2 + x + 3
start_num = range(-5, 5) # 初期値を複数設定しておく
print map(newton, start_num, it.repeat(x, len(start_num)),
          it.repeat(f, len(start_num)))

最後のmapを利用することで、一度に複数の結果を実行、表示することができるようになる。mapに与える引数については、繰り返し実行できる形式にしておく必要がある。

実行結果は、[0.33333, 0.33333, 0.33333, 0.33333, 0.33333, 0.33333, 1.0, 1.0, 1.0, 1.0]となる。それぞれ初期値を-5、-4、...、4に変更しながら実行した結果である。すべて1/3と1のうち、近いほうの極値に収束していることが確認できる。

勾配法を用いた最適化計算

テキスト「これなら分かる最適化数学」の81ページにある勾配法(gradient method)アルゴリズムをpythonで実装した。勾配法とは、関数f(x)を最大にするxの値に近いと思われる値を初期値とし、必ず関数値f(x)が増加するようにし、かつステップ幅をなるべく大きくなるようその幅を調整することにより、できるだけ高速に関数を最大にするxを求めるというものである。

なお、今回扱う勾配法においては、変数の値がとりうる範囲について、関数の微分係数が0になるのは1箇所であると仮定する(複数極値があると、どこに向かうか分からないため)。また、微分できない箇所がある関数では不都合が生じるので、これも考えないことにする(例えばf(x)=|x|のx=0の点のように、尖っている状況下などがある)。

関数の最大値を求めるにあたっては、微分係数が0になるという性質を利用している。このため、微分という操作を行う必要であるが、この問題はsympyモジュールを利用することによって解決できる。sympyモジュールはこちらからダウンロードできる。なお、記事執筆時点のsympyのバージョンは0.7.1である。

以下、「2次関数f(x)」と「正規分布の確率変数と関係がある部分のみ取り出した関数g(x)」の2つの例を用いて、勾配法で正しく関数を最大化するようなxを推定できるか試してみた。結果としては、(制約が強いこともあるが)ほぼ正確に推定できているということになった。

# -*- encoding: utf-8 -*-

from sympy import *

# 符号関数
def sign(value):
    if value > 0: return 1
    if value < 0: return -1
    return 0

# 勾配法を計算するメインルーチン
# initは初期推定値、funcは最大値を求めたい関数、stepは初期移動量、
# epsは収束した(ほぼf'(x)が0となった)と判定する閾値である。
# 返り値は最大値となるxの値に相当する。
def gradient_method(init, func, step = 10**-7, eps = 10**-6):
    # diffは微分の関数、これで第一引数の関数をxで微分したことになる
    # 事前にxをSymbol関数でシンボル化しておく必要がある
    df = diff(func, x)
    xx, h = init, step
    while True:
        h = sign(limit(df, x, xx)) * abs(h)
        X, Xdash = xx, xx + h
        # 関数に値を入れるという方法が見つからないので
        # 極限の値を求めている
        if limit(func, x, X) < limit(func, x, Xdash):
            while limit(func, x, X) < limit(func, x, Xdash):
                h *= 2.0
                X, Xdash = Xdash, X + h
            xx, h = X, h / 2.0
        else:
            while limit(func, x, X) > limit(func, x, Xdash):
                h /= 2.0
                Xdash -= h
            xx, h = Xdash, 2.0 * h
        if abs(limit(df, x, xx)) <= eps:
            break
    return xx

x = Symbol('x') # xを記号として扱う
f = -x**2 + 2*x + 3
g = exp(-(x-2)**2)
print gradient_method(0, f) # 1.0000002、なお正解は1である
print gradient_method(0.5, g) # 2.0000002、なお正解は2である

TopCoder SRM419 Div2 250Pts

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

柱状図(訳注：棒グラフと思って差し支え無いです)とは水平方向にn個の柱が配置されたものである。各柱は幅が1であり、各柱はx軸にくっついている。柱の高さはa[]という整数型の配列で与えられる。a[i]はi番目の柱の高さを表している(訳注：より詳しくはリンク先の画像をご確認ください。隣合う柱はくっついている図です)。与えられた柱状図の周囲の長さを返すメソッドを作成せよ。なお、a[i]は1以上50以下の整数になるものとする。例えば、aが{3, 2, 1}であれば、x軸に水平な方向の周囲の長さは柱の上側、下側を合わせて3*2=6、側面の長さは左から順に3+1+1+1で合計6なので、それらを合わせて12になる。

私の解答はこちら。

public class ColumnDiagramPerimeter {

 public int getPerimiter(int[] a) {
  int perimiter = 0;
  int prev = 0;
  for( int i=0 ; i<a.length ; i++ ){
   perimiter += Math.abs(a[i] - prev);
   prev = a[i];
  }
  perimiter += (a[a.length-1] + a.length * 2);
  return perimiter;
 }

}

得点は207.19、2回目のsubmitでシステムテストクリア。途中で提出のページに接続できなくなり、提出が遅れたのが残念。

TopCoder SRM418 Div2 250Pts

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

あなたは真剣に戦略ゲームをするプレーヤーなので、敵の防御塔を攻撃するという、もっとも一般的な問題を解くことにした。攻撃をする前にはmyUnitsという数の兵士を得る。各兵士は1回のラウンドにおいて、1つの塔に1のダメージを与えることができる。敵は兵士を持たない。しかしながら、体力がhpTの塔をnumT所持している。各塔は1回のラウンドにおいて、attackTだけの兵士を殺すことができる。1つのラウンドは次の順で行われる。

1. 自軍の各兵士は塔を1つ選び、塔に1のダメージを与える。塔がすべての体力を失うと、塔は破壊される。各兵士ごとに独立して攻撃する塔を選べるものとする。
2. 敵の攻撃になる。敵はk*attackTだけの自軍の兵士を殺すことになる。ここで、kは残っている塔の数である。

あなたの課題はすべての塔を破壊することである。もしそれが可能であれば、それを実行するのに必要な最小限のラウンド数を返せ。もし不可能ならば-1を返すようなメソッドを作成せよ。

私の解答はこちら。

public class Towers {

 public int attack(int myUnits, int hpT, int attackT, int numT) {
  int nTurn = 1; // 攻防を行った回数
  int totalHP = numT * hpT; // 塔の合計体力
  int remainT = numT; // 残っている塔の数
  int remainU = myUnits; // 残っている自軍の兵士数
  while( true ){
   totalHP -= remainU; // 塔の体力を減らす
   if( totalHP <= 0 ) return nTurn; // 塔の体力の合計が0以下なら全部破壊されたことになる
   remainT = (int)Math.ceil(totalHP*1.0/hpT); // 残っている塔の数を計算
   remainU -= remainT * attackT; // 自軍の兵士の数を減らす
   if( remainU <= 0 ) return -1; // もし自軍の兵士が全滅したら-1を返す
   nTurn++;
  }
 }

}

得点は196.74/250、1回のsubmitでシステムテストクリア。中央値は約135点。すべての塔を破壊するにはできるだけ塔を集中的に攻撃するというのが最善になることを利用します。タワーの残り体力を計算する際に、totalHPに1.0を掛けていなかったことに気付くのに少し時間がかかりました。

TopCoder SRM417 Div2 250Pts

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

与えられたXという整数に対し、Rev(X)というXの桁を反転させた整数を得ることができる。例えばRev(123)=321、Rev(100)=1である。xとyという二つの正の整数が与えられたとき、Rev(Rev(x) + Rev(y))を返すメソッドを作成せよ。

私の解答はこちら。

public class ReversedSum {

 public int getReversedSum(int x, int y) {
  StringBuffer xx = new StringBuffer("" + x);
  StringBuffer yy = new StringBuffer("" + y);
  int s = Integer.parseInt(xx.reverse().toString()) +
                        Integer.parseInt(yy.reverse().toString());
  StringBuffer ss = new StringBuffer("" + s);
  return Integer.parseInt(ss.reverse().toString());
 }

}

得点は243.24/250、1回のsubmitでシステムテストクリア。中央値は約233点。エレガントさを求めるのであればRev(X)という関数を定義するのが良さそうです。

TopCoder SRM416 Div2 250Pts

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

英語の典型的なテキストについて、いくつかの文字が他の文字よりも頻繁に現れるということが一般的に知られている。例えば、英語の長文においては、約12.31%の文字がeになる。言語学部の友人が、与えられたテキストの中で最も頻繁に現れる文字が知りたいということで、手伝ってくれるよう頼んできた。テキストはtext[]という文字列型の配列で与えられる。このとき、テキストでもっとも頻繁に現れる文字を返すメソッドを作成せよ。もし一番頻繁に現れる文字が複数ある場合、それらをアルファベット順で返すようにせよ。なお、文字列は小文字のアルファベットと空白しかないものとする。

私の解答はこちら。

public class MostCommonLetters {

 public String listMostCommon(String[] text) {
  int[] times = new int[26];
  for( int i=0 ; i<text.length ; i++ ){ // ここで文字の頻度集計
   for( int j=0 ; j<text[i].length() ; j++ ){
    char c = text[i].charAt(j);
    if( c != ' ' ){
     times[c-'a']++;
    }
   }
  }
  int maxTimes = -1;
  for( int i=0 ; i<times.length ; i++ ){ // 最大出現回数を調べる
   maxTimes = Math.max(maxTimes, times[i]);
  }
  String ret = "";
  for( int i=0 ; i<times.length ; i++ ){ // 出現回数が最大となる文字を集める
   if( times[i] == maxTimes ){
    char c = (char)('a'+i);
    ret += c;
   }
  }
  return ret;
 }

}

得点は241.25/250、1回のsubmitでシステムテストクリア。中央値は約186点。素直な集計の問題です。

TopCoder SRM415 Div2 250Pts

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

あなたの趣味は郵便消印を集めることである。N個の異なる消印があり、0からN-1まで番号が付けられている。それらの価値はprices[]という整数型の配列で与えられており、添字iが消印iの価値を表すものとする。あなたの目標はできるだけ異なる種類の消印を集めることである。既に持っている消印はhave[]という整数型配列で与えられている。また、初期状態では所持金0の状態とする。消印を売り、お金を得て異なる消印を買うということができる。集められる消印の種類数の最大値を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class CollectingUsualPostmarks {

 public int numberOfPostmarks(int[] prices, int[] have) {
  int value = 0;
  for( int i=0 ; i<have.length ; i++ ){
   value += prices[have[i]];
  }
  Arrays.sort(prices);
  int count = 0;
  int current = 0;
  for( int i=0 ; i<prices.length ; i++ ){
   current += prices[i];
   if( current > value ) break;
   count++;
  }
  return count;
 }

}

得点は191.82/250、問題文を読み替えて、全部売って安い方から買っていくと問題を置き換える発想の転換すると非常に見通しが良くなります。

一様分布から標準正規乱数を発生させる

標準正規分布に従う乱数を発生させる簡単な方法として、一様乱数をいくつか発生させてその和をとり、期待値で引き算するという方法がある。そこで、得られた値が本当に標準正規分布といって差し支えないか調べてみることにした。以下のコードでは、6つの一様乱数(取りうる値の範囲は[0,1])とし、それらの和の期待値3を引いたものを大量に発生させ、値の分布が一様乱数であるか検定したものである。6としているのは、とりうる値を[-3, 3]とするためである。標準正規分布であれば、多くの場合、そこから発生する乱数は[-3, 3]の範囲に収まるためである。

# 一様乱数から正規乱数を生成するプログラム

set.seed(1)
pts <- 6 # 一つの標準正規乱数を発生させるのに用いる一様乱数の数
N <- 5000 # 発生させる正規乱数
num.data <- N*pts
rn <- runif(num.data)
rnd.mat <- matrix(rn,nrow=N) # 一様乱数の行列
num <- rowSums(rnd.mat)-pts/2

hist(num,breaks=20,xlim=c(-4,4),xlab="",ylab="freq",main="")
oldpar <- par(new=T)
curve(dnorm,-4,4,xlab="",ylab="",axes=FALSE)
par <- oldpar

# コルモゴロフ・スミルノフ(KS)検定
# 標準正規分布 N(0, 1)とデータを比較している
ks.test(num, "pnorm", mean=0, sd=1)

コルモゴロフ・スミルノフ検定は、データがある分布に従っているかを検定するというものである。上のコードは1標本KS検定に相当する。帰無仮説はデータは分布から発生したものではない、対立仮説はデータは分布から発生したものとなる。統計量は従うと想定される分布の累積分布関数と、データのそれを比較した結果から得られる差の値に基づく。統計量が小さくなると、帰無仮説が棄却されるということになる。結論は、KS検定ではp値はほぼ0となり、帰無仮説は標準正規分布ではないということになった。ただし、中心極限定理からデータ数を6から増やせば、標準正規分布に従うことが想定される。そこで、pts<-12としてみると標準正規乱数といえるようなp値となった（有意水準5%で帰無仮説を棄却できる）。必要なptsのサイズは標準化する分布(今回は一様分布)の対称の程度に依存していることに注意。今回利用した一様分布U(0,1)は0.5で対称なので、比較的少ないデータ数で標準正規分布が生成できるのである。

TopCoder SRM414 Div2 250Pts

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

あなたはレストランのサービス部門のマネージャである。夕方のコースでは、顧客のグループがやってきて、その人たちをテーブルに配置しなければならない。レストランのテーブルは異なった人数の客に対応するために、さまざまなサイズのテーブルを用意している。テーブルへの客の配置は次のような手順で行う。客が現れたとき、まだ客で埋まっていないテーブルの内、そのグループ以上の人数を収められる最小のテーブルを客のために確保する。もし適切なテーブルが複数あれば、その中から任意に一つ割り当てる。もし適切なテーブルが一つもない場合は、顧客は即座に踵を返してその日の夕方は二度と現れない。グループが食事を終え、離れるとき、テーブルは利用できるようになり、新しい顧客を配置することができるようになる。

あなたはこの方法でテーブルに客を割り当てたとき、何人の顧客に逃げられるか知りたい。テーブルのサイズはtable[]という整数型配列で、各要素は収容可能な人数を表す。グループの人数、グループの到着時刻、出発時刻はそれぞれgroupSizes[i]、arrivals[i]、departures[i]である。i番目の要素はすべてグループiに関する情報である。グループは到着時刻順に並べられており、どのグループも同時に来ることはないものとする。もし、あるグループの出発時刻と別のグループの到着時刻が一致した場合は、出発するグループのテーブルは利用可能になっているものとする。逃げられた顧客の総数を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class RestaurantManager {

 public int allocateTables(int[] tables, int[] groupSizes, int[] arrivals, int[] departures) {
  Arrays.sort(tables);
  boolean[] isOccupied = new boolean[tables.length];
  // テーブルにいるグループの出発時刻。
  // i番目の要素がテーブルiを表す。値0はそのテーブルに誰も座ってないことを意味する
  int[] depTime = new int[tables.length];
  int nTurnedAway = 0;
  for( int i=0 ; i<arrivals.length ; i++ ){
   for( int j=0 ; j<tables.length ; j++ ){ // 来た人の時刻により、埋まっていたテーブルを解放
    if( arrivals[i] >= depTime[j] && depTime[j] > 0 ){
     isOccupied[j] = false;
     depTime[j] = 0;
    }
   }
   boolean caught = false;
   for( int j=0 ; j<tables.length ; j++ ){ // 空いているテーブルの探索
    // 最初に見つかったところに顧客を割り当てる(事前にテーブルサイズでソートしておくのがキモ)
    if( isOccupied[j] == false && tables[j] >= groupSizes[i] ){
     isOccupied[j] = true;
     depTime[j] = departures[i];
     caught = true;
     break;
    }
   }
   if( caught == false ){
    nTurnedAway += groupSizes[i];
   }
  }
  return nTurnedAway;
 }

}

得点は201.97/250、1回のsubmitでシステムテストクリア。中央値は約125点。テーブルを小さい順に並び替えておくことで、空いている必要最上限のテーブルサイズを探索するのが容易になります。

TopCoder SRM413 Div2 250Pts

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

地下鉄の電車は人々をある駅から隣の駅へ高速に動かすことができる。二つの隣り合う駅について、lengthメートルであることが知られている。安全のため、電車はmaxVelocityメートル/秒よりも速く移動することは許されない。また、快適さのため、加速度の絶対値はmaxAccelerationメートル/秒^2を超えてはならないものとする。電車は0メートル/秒から動きだし、隣の駅で停車する(つまり駅に到着したときに0メートル/秒の速度になる)。隣の駅へ到着するのに必要な時間の最小値を返すようなメソッドを作成せよ。

私の解答はこちら。

public class Subway2 {

 public double minTime(int length, int maxAcceleration, int maxVelocity) {
  double toMax = maxVelocity * 1.0 / maxAcceleration;
  double s = maxVelocity * toMax;
  if( length < s ){
   double half = length / 2.0;
   return Math.sqrt(half * 2 / maxAcceleration)*2;
  }else{
   return toMax * 2 + (length - s) / maxVelocity;
  }
 }

}

209.07/250、1回のsubmitでシステムテストクリア。高校の物理学に出てくる運動の問題ですね。最高速に達する(コード中の分岐では後半)か、達しない(コード中の分岐では前半)かで場合分けすると簡単です。

2012年7月の学習記録

2012年7月に学習した主な本一覧。

入門・演習 数理統計(pp.68～97、65問)

積率母関数や条件付き期待値の問題などを解く。

マスタリングTCP/IP(pp.231～338読了)

この本の範囲はエンジニアなら知っておいて損はないように思いました。とりあえず自分の周囲半径3メートル程度で発生したネットワークトラブルは自分の力で原因究明できるようになりたいものです。

テキストデータの統計科学入門(pp.13～134)

テキストをうまく指標に落として検定等に持ち込む方法について学習中。個人的にはRでネットワークを作るパッケージの紹介が参考になりました。

統計解析入門（pp.130～148)

信頼区間は区間が最小になるように選んでいると知ってナルホドと思いました。

入門自然言語処理(pp.62～110)

もう少し深く読みたいです。個人的には演習問題の解答を一通り作ってしまいたい。

初めてのPython(第13～16、22～23章)

どちらかというとリファレンス的な本なので、実践的なテキストを読んだ方が楽しそう。

その他、実践ビジネス英語、入門ソーシャルデータなどを少々掻い摘む。

TopCoder SRM412 Div2 250Pts

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

ファイルシステムには、使用したディスク容量がかならずしもファイルサイズに一致しないことがある。これはディスクが等しいサイズのクラスタに分けられており、各クラスタは1つのファイルしか利用できないためである。例えば、クラスタサイズが512バイトの場合、ファイルが600バイトであれば、2つのクラスタでファイルを保存することになる。これら2つのクラスタは他のファイルと領域を分け合うことはなく、全体として1024バイトのディスク容量を使用することになる。sizes[]という1つのファイルサイズを表す整数型配列と、clusterSizeというファイルシステムのクラスタサイズが与えられたとき、与えられたファイルで使用することになるディスク容量の合計値を返すメソッドを作成せよ。

私の解答はこちら。

public class TrueSpace {

 public long calculateSpace(int[] sizes, int clusterSize) {
  long nSpace = 0;
  for( int i=0 ; i<sizes.length ; i++ ){
   long spaceNeeded = (int)Math.ceil(sizes[i]*1.0/clusterSize);
   nSpace += spaceNeeded;
  }
  return nSpace*clusterSize;
 }

}

得点は246.05/250、1回のsubmitでシステムテストクリア。

TopCoder SRM411 Div2 250Pts

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

ボニーは好きな数学の授業で、非負の整数には、二つの非負の整数の2乗和で表されるものがあるということを習った。例えば、13=2*2+3*3という具合である。ボニーはのちに、そのような数が2通り以上の分割方法があるということを発見した。例えば25=0*0+5*5=3*3+4*4ということである。ボニーは整数に対し、異なる非負の整数の二乗和で表されるパターンの数を得点と定義することにした。二つの二乗の数を足す順序は異なっても同じものと扱う。これにより、25のスコアは2、2のスコアは1となる(2=1*1+1*1)。また、1のスコアは1、0のスコアは1となる。ボニーは以下の問題を解くのにあなたの手伝いを必要としている。ボニーはlowerBound以上、upperbound以下の整数でスコアが最大となる整数を見つけたいというのである。もし、複数の整数が最高スコアになった場合は、それらの数の中で最大になるようなものを求めるようにせよ。

私の解答はこちら。

public class MaximumScoredNumber {

 public int getNumber(int lowerBound, int upperBound) {
  int largest = lowerBound; // スコアが最大になる整数
  int maxscore = 0; // スコアの最大値
  for( int num=lowerBound ; num <= upperBound ; num++ ){
   int score = 0;
   int range = (int)Math.sqrt(num) + 1;
   for( int i=0 ; i<range ; i++ ){
    for( int j=i ; j<range ; j++ ){ // j=iからにすることで、順序が違うだけの計算を省ける
     if( i*i + j*j == num ) score++;
    }
   }
   if( score >= maxscore ){ // スコアが現在の値に並ぶか超えたら更新
    maxscore = score;
    largest = num;
   }
  }
  return largest;
 }

}

得点は238.06/250、1回のsubmitでシステムテストクリア。中央値は約151点。

TopCoder SRM407 Div2 500Pts

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

あなたは巨大な会社の人事部で働いている。各労働者は、、直属の上司と直属の部下のどちらかが常にいる(両方いることもある)。もちろん、部下は部下を持つこともあるし、上司はさらに上司を持つ頃もある。XがYのボスであるとは、雇用者A、B、...、Dがおり、XがAの上司、AがBの上司、...、DがYの上司であることをいう。もちろん、XがYの直属の上司である場合もXはYのボスになる。もし、AがBのボスである場合、BはAのボスにはなれないものとする。新しい会社の方針によると、部下のいない労働者の給与は1である。もし、部下を持つ労働者がいれば、その人の給与は直属の部下の給与の合計になる。

relations[]というi番目の文字列のj番目の要素がYであれば、iがjの直属の上司であることを表すというような文字列が与えられたとき、全労働者の給与を返すようなメソッドを作成せよ。なお、Yでない位置の文字列の内容はNになる。自身は自身の上司にならないので、i番目の文字列のi番目の要素は必ずNになる。

私の解答はこちら。再帰を用い、各労働者が何人の部下を持つかを見つけるようにしています。

public class CorporationSalary {

 public long totalSalary(String[] relations) {
  long total = 0;
  long[] salary = new long[relations.length]; // 給与は0で初期化しておく
  for( int i=0 ; i<relations.length ; i++ ){
   total += calc_salary(relations, i, salary);
  }
  return total;
 }
 // i番目の人の給与を計算する関数
 // salary[]は給与を記録するためのテーブルと思ってよい
 private long calc_salary(String[] relations, int i, long[] salary){
  if( relations[i].indexOf("Y") < 0 ){
   return 1; // 部下がいない場合
  }
  long total = 0;
  long ret = 0;
  for( int j=0 ; j<relations[i].length() ; j++ ){
   if( relations[i].charAt(j) == 'Y' ){ // 部下がいた場合
    // 0でないということは給料が分かっている場合、その人の給与は計算済み、既知である
    if( salary[j] > 0 ){
     total += salary[j];
    }else{
     ret = calc_salary(relations, j, salary); // 再帰処理
     total += ret;
     salary[j] = ret; // j番目の人の給料をセット
    }
   }
  }
  return total;
 }
}

得点は150.0/500、何度もトライしました。再帰で時間がかかりすぎるというのが問題の原因だったので、計算結果を途中で入れるようにして解決。これにより2秒で処理が終わらなかったテストケースが、4msecで終わるようになりました。

TopCoder SRM410 Div2 250Pts

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

最新のマイクロコントローラーをできるだけ安くするため、ACMEウィジェットカンパニーはとても単純なキャッシュのデザインを行った。プロセッサはnバイトからなる遅いメモリシステムにつながっており、そのnバイトは0～n-1と値をつけられている。速いアクセスが可能なキャッシュは一度にkバイト保持することができる。キャッシュはベースアドレス（後程説明する）を持っており、base～base+k-1まで値がついたバイトのコピーを保持する。プログラムが1バイトを読み込んだとき、キャッシュコントローラーは以下のアルゴリズムを実行する。

• 現在のベースアドレスと新しいベースアドレスが最小になるよう、要求されたバイトを含む新しいkバイトの範囲を見つける。もし、要求されたバイトがキャッシュの中にあれば、ベースアドレスの変更は必要ない。
• 新しい範囲にあるバイトの内容をメモリシステムから読み込み、キャッシュを新しい内容に更新する。古いメモリ範囲で、新しいメモリ範囲に含まれない範囲は捨てるものとする。
• プログラムに要求されたバイトを返す。

プログラムのパフォーマンスを分析するために、メモリシステムから何バイトが読まれたかを知りたい。プログラムが読むバイトはaddresses[]という整数型配列で与えられる。これはメモリから読みだされる順序で値が格納されている。また、プログラムが始まるとき、ベースアドレスは0にあるものとする。addresses[]で指定されたアドレスをすべてキャッシュに順に取り込んだとき、全部でメモリから何バイトを読み込んだかを返すメソッドを作成せよ(訳注：この文章は元の問題文にはありませんが、実行例に具体的に書いているので、こちらで補足しておきます)。

私の解答はこちら。

public class ContiguousCacheEasy {

 public int bytesRead(int n, int k, int[] addresses) {
  int[] range = new int[2];
  int nRead = 0;
  range[0] = 0;
  range[1] = k-1;

  for( int i=0 ; i<addresses.length ; i++ ){
   if( range[0] <= addresses[i] && addresses[i] <= range[1] ) continue;
   if( addresses[i] < range[0] ){
    int readBytes = range[0] - addresses[i] < k ? range[0] - addresses[i] : k;
    nRead += readBytes;
    range[0] = addresses[i];
    range[1] = addresses[i] + k - 1;
   }else if( addresses[i] > range[1] ){
    int readBytes = addresses[i] - range[1] < k ? addresses[i] - range[1] : k;
    nRead += readBytes;
    range[0] = addresses[i] - k + 1;
    range[1] = addresses[i];
   }
  }
  return nRead;
 }

}

得点は190.64/250、1回のsubmitでシステムテストクリア。中央値は約114点。難しいのは実装よりも文章でした。

TopCoder SRM409 Div2 250Pts

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

ジョニーは64センチメートルの棒を持っていて、これをxセンチメートルにすれば棒を使った遊びがもっとたのしくなるであろうと考えた。ジョニーは元の棒を小さい棒に分け、ちょうどxセンチメートルになるようにそれらをくっつけることにした。棒を分割するもっとも単純な方法は半分に分けることなので、ジョニーは以下の手順を利用することにする。

• 全部の棒の長さの総和を取る。これがxよりも大きいうちは次の手順を取る。
  • 一番短い長さの棒を半分にする
  • もし半分にしたものの一つを捨てても、残りの棒の長さがxを下回らないようであれば、それを捨てる。
• 最後に、ちょうどxセンチメートルの棒になるように、残った棒をくっつけていく。

ジョニーが上の手順を行ったときに、くっつけなければならない棒の数を返すメソッドを作成せよ。もし、最後のステップで1つの棒しか必要がないようであれば1を返すようにすること。

私の解答はこちら。

public class Stick {

 public int pieces(int x) {
  int ret = 0;
  while( x > 0){
   ret += x % 2;
   x /= 2;
  }
  return ret;
 }

}

得点は204.91/250、1回のsubmitでシステムテストクリア。

TopCoder SRM408 Div2 250Pts

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

思考チャレンジオリンピックの審判として雇われた。仕事は、一連の種目における競技者のパフォーマンスに基づいて合計点を計算することである。各種目で、競技者の生のスコアが与えられる。合計点は各種目に対して調整したスコアの和になる。各種目の調整スコアを計算するために、生のスコアを換算係数で割り、その値に最も近い整数に丸めるということを行う(小数点第一位で四捨五入する)。rawScores[]という一人の競技者の生のスコアと、conversionFactor[]という換算係数が与えられる。それぞれのi番目がi番目の種目のスコアと換算係数に対応している。競技者の合計点を返すメソッドを作成せよ。

私の解答はこちら。

public class TournamentJudging {

 public int getPoints(int[] rawScores, int[] conversionFactor) {
  int pts = 0;
  for( int i=0 ; i<rawScores.length ; i++ ){
   pts += Math.round(rawScores[i]*1.0 / conversionFactor[i]);
  }
  return pts;
 }

}

得点は248.13/250、1回のsubmitでシステムテストクリア。ひっかかるとすれば、割り算するときに実数に一旦変換するために1.0を掛けるのを忘れないことぐらいでしょうか。おそらく問題文を解読することの方が、コーディングよりも時間がかかっています。

TopCoder SRM407 Div2 250Pts

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

長方形のセルを左上から右上、右下、左下の方向へ順に、ぐるぐると渦を巻くように回る。全部のマスを回ったところで動きは止まる。既に通ったマス、あるいはセルの範囲を飛び出す場合は先に進めないので向きを時計回りに90度変える。進む向きを変えた位置にあるセルを除いて、通過したセルに書かれている数値の合計を計算して返すメソッドを作成せよ。最初と止まった位置も合計に加えることを忘れないこと。なお、セルは文字列型配列で管理されており、i番目の要素のj番目の文字がセル(i, j)とその位置に書かれている値を表している。

私の解答はこちら。

public class SpiralWalking {

 public int totalPoints(String[] levelMap) {
  int nrow = levelMap.length;
  int ncol = levelMap[0].length();
  boolean[][] isVisited = new boolean[nrow][ncol]; // 通過したセルを管理するフラグ
  int dir = 0; // 向いている方向(0～3)
  int[] xdir = {0, 1, 0, -1}; // 順に右、下、左、上方向に動く量を表している
  int[] ydir = {1, 0, -1, 0}; // 上に同じ。なお、xdirは行方向、ydirは列方向の移動量である。
  int total = 0; // 返す値の合計を管理
  int xpos = 0; // 現在の位置(行方向)
  int ypos = 0; // 現在の位置(列方向)
  boolean turned = false; // 向きを変えたか否かを管理するフラグ
  while( true ){
   int val = levelMap[xpos].charAt(ypos) - '0'; // 値を計算して
   total += val; // 追加
   isVisited[xpos][ypos] = true; // 訪問済に変更
   int currentdir = dir; // 現在の向きを記憶
   turned = false; // 向きを変えていない
   // もし、その向きで進んだらセルを飛び出す、あるいは訪問済みのセルに進むのであれば、
   // 向きを90度変える
   while( xpos+xdir[dir] >= nrow || xpos+xdir[dir] < 0 ||
    ypos+ydir[dir] >= ncol || ypos+ydir[dir] < 0 ||
    isVisited[xpos+xdir[dir]][ypos+ydir[dir]] ){
    dir = (dir+1) % xdir.length;
    turned = true;
    if( dir == currentdir ) return total; // 結局向きが1周したら、訪問するセルは残っていない
   }
   if( turned ) total -= val; // 向きを変えていたなら、値の加算はなかったことにする
   xpos += xdir[dir]; // 次のセルの位置へ進む
   ypos += ydir[dir];
  }
 }

}

得点は117.42/250、1回のsubmitでシステムテストクリア。中央値は75点。規則性があるので、上手く書けば実はループが不要にできるのではないかと思うのですが...

TopCoder SRM406 Div2 250Pts

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

grid[]という文字列型配列による長方形型のセルについて考える。"X"という文字が入ったセルは埋まっていることを示し、"."という文字はそのセルが空いていることを示している。二つのセルが同じ辺を共有しているとき、二つのセルは直交に隣合っている(orthogonal neighbors)といい、互いに斜めの位置にある場合、二つのセルは対角に隣り合っている(adjacent neighbors)という。もし、あるセルが空白で、かつ直交に隣り合うセルと斜めに隣り合うセルがすべて埋まっているのであれば、そのセルを1-happyということにする。あるセルが空白で、直交に隣り合うセルがすべて埋まっていて、斜めに隣あうセルが1つ以上空白であるとき、そのセルを2-happyという。あるセルが空白で、斜めに隣り合うセルがすべて埋まっているが、1つ以上直交に隣り合うセルに空白があるとき、そのセルは3-happyという。1-happyに該当するセル、2-happyに該当するセル、3-happyに該当するセルの数を求め、それらの3つの要素からなる整数型の配列を返すメソッドを作成せよ。

私の解答はこちら。

public class HappyCells {

 public int[] getHappy(String[] grid) {
  int[] happy = new int[3];
  int nrow = grid.length;
  int ncol = grid[0].length();
  // 自身を含む周囲9マスの相対的な位置、xは上下方向、yは左右方向
  // 添え字は左上から右下に向かって大きくなる。注目しているセルは5番目になる
  int[] x = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
  int[] y = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
  for( int i=0 ; i<nrow ; i++ ){
   for( int j=0 ; j<ncol ; j++ ){
    int diag = 0; // 直交に隣り合うセルの.の数
    int orth = 0; // 斜めに隣り合うセルの.の数
    if( grid[i].charAt(j) != '.') continue; // .のセル以外は考えなくて良い
    for( int k=0 ; k<x.length ; k++ ){
     if( k == 4 ) continue; // 5番目のセル(つまり周囲を注目すべきセル)は考慮しない
     int xpos = i+x[k];
     int ypos = j+y[k];
     // 長方形の範囲を超える箇所では考える必要はない
     if( xpos < 0 || xpos >= nrow || ypos < 0 || ypos >= ncol ) continue;
     if( grid[xpos].charAt(ypos) == '.' && k % 2 == 0 ){
      diag++;
     }else if( grid[xpos].charAt(ypos) == '.' && k % 2 == 1 ){
      orth++;
     }
    }
    // 得られた周囲の.の数から、加算すべき配列の添字を決める
    if( diag == 0 && orth == 0 ){
     happy[0]++;
    }else if( diag > 0 && orth == 0 ){
     happy[1]++;
    }else if( diag == 0 && orth > 0 ){
     happy[2]++;
    }
   }
  }
  return happy;
 }

}

196.97/250、1回のsubmitでシステムテストクリア。変数の書き換えなどしていたので、1点ぐらいは下げたのではなかろうか...

TopCoder SRM405 Div2 250Pts

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

下降階乗をnからk個取るとき、その値はn*(n-1)*...*(n-k+1)と定義される。これをn^^kと表記することにする。例えば7^^3=7*6*5=210であるし、n^^1=nである。次にこの定義を非正の整数kに対して拡張する。そのために(n-k)*(n^^k)=n^^(k+1)という事実を用いる。つまり、n^^k=(n^^(k+1))/(n-k)となる。これにより、以下のことが分かる。

• n^^0=n^^1/(n-0)=1
• n^^(-1)=n^^0/(n+1)=1/(n+1)
• n^^(-2)=1/(n+1)/(n+2)
• より一般にはn^^(-k)=1/(n+1)/(n+2)/.../(n+k)

例えば3^^(-1)=1/4=0.25などとなる。nとkが与えられたとき、下降階乗をnからk個を取ったときの値を返すメソッドを作成せよ。

私の解答はこちら。kの値で分岐して計算しています。

public class FallingFactorialPower {

 public double compute(int n, int k) {
  if( k==0 ){
   return 1.0;
  }else if( k>0 ){
   double ret = 1.0;
   for( int i=0 ; i<k ; i++ ){
    ret *= (n-i);
   }
   return ret;
  }else{
   double ret = 1.0;
   for( int i=0 ; i<Math.abs(k) ; i++ ){
    ret /= (n+i+1);
   }
   return ret;
  }
 }

}

得点は237.85/250、1回のsubmitでシステムテストクリア。中央値は約205点。

TopCoder SRM404 Div2 250Pts

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

introduction、story、edificationの3つのパートからなる本がある。ある人は本の元へ向かい、本の様々な部分を読んでいく。その人は、本を読み終える度に、リストに読み終えたパート名を付け加えていく。各本の0以上のパートを読む。どの順序で読むことができるが、各パートは1度しか読むことができないものとする。新しい本を読み始める度に、以前に見ていた本を読むことはできなくなる。readParts[]という読んだパートを示したリストが与えられたときに、3つのパートすべてを読んだ可能性がある本の数の最大値を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class ReadingBooks {

 public int countBooks(String[] readParts) {
  int[] times = new int[2];
  int nRead = 0;
  for( int i=0 ; i<readParts.length-2 ; ){
   // 以下の条件がtrueのとき、3パートは1つの本を構成しない
   if( readParts[i].equals(readParts[i+1]) ||
    readParts[i].equals(readParts[i+2]) ||
    readParts[i+1].equals(readParts[i+2]) ){
    i++;
   }else{
    nRead++;
    i += 3;
   }
  }
  return nRead;
 }

}

得点は103.62/250、2回目のsubmitでシステムテストクリア。中央値は約143点。誤訳して間違った実装をしていました、ハイ。

TopCoder SRM403 Div2 250Pts

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

ジョンは4と7はラッキーな桁であり、その他の桁はラッキーでないと考えている。ラッキーナンバーは10進数記法で書いたときにラッキーな桁のみからなる数値のことである。nという整数が与えられたとき、n以下で最大のラッキーナンバーを返すメソッドを作成せよ。なお、nは4以上の整数である。

私の解答はこちら。

public class TheLargestLuckyNumber {

 public int find(int n) {
  while( n > 0 ){
   String tmp = "" + n;
   boolean isLucky = true;
   for( int i=0 ; i<tmp.length() ; i++ ){
    if( tmp.charAt(i) != '4' && tmp.charAt(i) != '7' ){
     isLucky = false;
     break;
    }
   }
   if( isLucky ) return n;
   n--;
  }
  return 0;
 }

}

得点は247.97/250、1回のsubmitでシステムテストクリア。4と7以外を含むという判定を繰り返し数を10で割って余りで判別するといった手法もありそうですね。

2012年6月の学習記録

2012年6月に学習した主な本一覧。

入門・演習 数理統計(18問)

X/Yの分布を求める問題など、確率変数変換の問題を理解するために解き始めた。統計ではありますが、解析の話がちょこちょこ出てきます。

マスタリングTCP/IP(pp.99～230)

TCPのヘッダの中身など、結構マニアックな話が増えてきたかな。情報セキュリティスペシャリスト試験を受けるのであれば、要らない箇所も多いだろうなと思いつつ、ネットワークスペシャリスト目指すなら必須だよなとも思って読んでいます。3分間ネットワーク基礎講座は一通り読了。

編入数学徹底演習(109問、9～14章)

確率・統計、線形代数の高専生の編入試験のための問題群。やり直しにはこのぐらいでもよい。

テキストデータの統計科学入門(pp.1～12)

テキストマイニングや自然言語処理を今年の学習テーマにしているので、早めに読んでしまいたい。

統計解析入門（pp.114～130)

クラメル・ラオの不等式の辺りが山場。理解のためにもうちょっと演習をやっておきたい。入門・演習 数理統計と章末問題で補強する予定。

入門自然言語処理(pp.41～62)

NLTKに付属するコーパスの呼び出し方などの学習。もう少しペースを上げて読みたい。

初めてのコンピュータサイエンス(pp.245～読了)

初めてのGUI作成、および初めてのデータベース操作をしました。Pythonの強力さというのが分かる1冊。

初めてのPython(第6～12章)

Python2冊目はこれ。初めてのコンピュータサイエンスのおかげで軽く読めている。後半のオブジェクト指向などが山場になりそう。

その他の勉強はPythonの無料講座(講師として約4時間の指導)、NHKラジオの実践ビジネス英語、TopCoder過去問演習など。

TopCoder SRM402 Div2 250Pts

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

words[]という1つの要素が1つの単語からなる文字列型配列が与えられる。i番目の要素がi番目の単語を省略したものを返せ。単語の省略したものというのは、他の単語の接頭辞にならない、かつ空文字ではないという条件を満たす、もっとも短い接頭辞である。この制約により、すべての与えられた単語の省略した形があるということが保証される。

私の解答はこちら。

public class WordAbbreviation {

 public String[] getAbbreviations(String[] words) {
  String[] ret = new String[words.length];
  StringBuffer sb = new StringBuffer();
  for( int i=0 ; i<words.length ; i++ ){ // 各単語について
   for( int j=0 ; j<words[i].length() ; j++ ){ // 先頭からj番目の文字まででユニークか判定
    sb.append(words[i].charAt(j)); // 1文字増やす
    boolean isUnique = true;
    String tmp = sb.toString();
    for( int k=0 ; k<words.length ; k++ ){
     if( i==k ) continue;
     if( words[k].startsWith(tmp) ){ // 接頭辞で単語の特定ができない場合
      isUnique = false;
      break;
     }
    }
    if( isUnique ){
     ret[i] = tmp;
     break;
    }
   }
   sb.delete(0, sb.length());
  }
  return ret;
 }

}

得点は225.45/250、1回のsubmitでシステムテストクリア。中央値は約158点。

TopCoder SRM401 Div2 250Pts

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

ジョンはフィールドテックという会社で働いている。そして今日、ジョンは仕事後にとても疲れていたので、家に帰るとすぐに眠ってしまった。不幸なことに、寝ている時でさえもジョンは仕事のことが忘れられなかった。夢の中で、ジョンは人参栽培を行っている会社から以下の問題に対処するように頼まれた。2つの人参を結ぶ直線状に何本の人参が育てられるだろうか?ただし端点の人参は除くものとして考える。これはかなり変な問題であるが、さらに問題を変なものにしていることとして、会社の代表はすべての人参は無限の広さを持つ平面で育ち、1つの格子点(訳注：座標が整数の箇所のこと)に1つの人参だけ育てられるということを述べた。あなたはこの問題に対処する疲れ切ったジョンを助けなければならない。

2本の端点の人参の座標を(x1, y1), (x2, y2)としたときに、これらの位置を結ぶ線分上で育てられる人参の数を返すメソッドを作成せよ。

public class DreamingAboutCarrots {

 public int carrotsBetweenCarrots(int x1, int y1, int x2, int y2) {
  int num = Math.abs(y2 - y1);
  int denom = Math.abs(x2 - x1);
  int step = gcd(num, denom);
  return step-1;
 }
 private static int gcd(int a, int b){
     return b == 0 ? a : gcd(b, a % b);
 }
}

得点は191.09/250、1回のsubmitでシステムテストクリア。中央値は約142点。結局x、y方向の座標の差を計算し、その値の最大公約数-1が答えになる。短いコードでかける気持ちのいい問題。当日の正解率は34%台と難しめ。

初めてのコンピュータサイエンス解答まとめ

章ごとに解答の記事があるので、以下にリンクでまとめました。1章、13章は問題がないので、解答はありません。英語版テキストはこちらをご覧ください。日本語版のpdfはありませんので、必要があれば購入しましょう。なお、英語版と日本語版では一部の問題が異なっていますのでご注意ください。

• 第2章解答
• 第3章解答
• 第4章解答
• 第5章解答
• 第6章解答
• 第7章解答
• 第8章解答
• 第9章解答
• 第10章解答
• 第11章解答
• 第12章前半(1～10)解答
• 第12章後半(11～20)解答
• 第14章解答
• 第15章解答

TopCoder SRM400 Div2 250Pts

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

あなたは休日に街の中を歩いている。すると突然、上司から携帯電話でできるだけ速く職場に来いという命令が届いた。街の大きさは無限であり、南北方向に道路がXの間隔で並んでおり、東西方向に道路がYの間隔で並んでいると仮定する。いま、あなたは(0, 0)という座標におり、職場は(gX, gY)という位置にある。街にはタクシーが数台あり、(tXs[i], tYs[i])という位置にいる(訳注：配列になっているのは複数台あることを意味する)。職場へは徒歩、あるいは留まっているタクシーへ徒歩で向かい、タクシーで職場へ行くという方法がある。東西方向、あるいは南北方向の隣合う交差点へ向かうのにwalkTime分、タクシーが同様の移動をするのにtaxiTime分かかるとする。このとき、職場へ向かうのに最低限必要となる時間を求めて返すメソッドを作成せよ。

私の解答はこちら。

public class GrabbingTaxi {

 public int minTime(int[] tXs, int[] tYs, int gX, int gY, int walkTime, int taxiTime) {
  // 最初の基準は徒歩のみでかかる移動時間
  int min = (Math.abs(gX) + Math.abs(gY)) * walkTime;
  for( int i=0 ; i<tXs.length ; i++ ){
   // タクシーiを利用した場合について検討する
   // タクシーiでの移動時間
   int taxi_time = (Math.abs(gX - tXs[i]) + Math.abs(gY - tYs[i])) * taxiTime;
   // タクシーiの位置まで徒歩で移動するのにかかる時間
   int walk_time = (Math.abs(tXs[i]) + Math.abs(tYs[i])) * walkTime;
   min = Math.min(min, taxi_time + walk_time); // 最小値を更新したか検討
  }
  return min;
 }

}

得点は239.07/250、1回のsubmitでシステムテストクリア。中央値は約179点。

初めてのコンピュータサイエンス第15章解答

いよいよ最終章、第15章練習問題の解答です。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず(英語版はpdfで公開されている模様)。日本語版が必要なら買いましょう。その前にこの章の個人的なメモ。

• Pythonの標準ライブラリにはSQLite3というSQLiteというDBを操作するためのライブラリがある。SQLiteは大規模なものには向かないが、小規模なものであれば十分利用に耐えうる。
• データベースにプログラムが直接手を加えるということはなく、DBMSが操作の仲介の役割を果たす。
• データベースのキーにID(つまり整数)を持たせることには重要な意味がある。整数の方がソートが高速であるということ、同じ名前の物、人物の区別に便利だからである。
• NULLの取り扱いはデータベースによって異なる。データベースはSQLite以外にもMySQL、OrableDB、Accessなどがある。
• クエリーはネストできる。特定の条件Aに合うものだけ抽出し、その抽出したものに対し、別の条件Bに合うものだけを抽出するといったことができる。

SQLの基本的な決まり文句の一覧には以下のようなものがある。

コマンド	意味
CREATE TABLE Men(Name TEXT, Age INTEGER)	Name(人物名)という文字列型の列、Age(年齢)という整数型の列からなるMenというデータベースを作成する
INSERT INTO Men VALUES("Taro", 30)	MenというDBに("Taro", 30)という値のレコードを挿入する
SELECT Name FROM Men WHERE Age >= 25	年齢が25歳以上の人物の名前を抽出する
SELECT Name FROM Men WHERE Age >= 25 AND Age <=40	年齢が25歳以上40歳以下の人物の名前を抽出する
SELECT * FROM Men WHERE Name="Taro"	名前が"Taro"という人をすべて抽出する
UPDATE Men SET Age=31 WHERE Name="Taro"	TaroのAgeを31に更新する
DELETE FROM Men WHERE Name="Taro"	NameがTaroというレコードを削除する。TaroというNameのものがすべて消える
CREATE TABLE Men(Name TEXT NOT NULL, Age INTEGER)	NameがNULLのレコードを認めないデータベースを作成する。
INNER JOIN	直積を作成する(クエリー間で比較するときに使える)
PRIMARY KEY	一意になるキー列を設定する(キーを複数入れないようにするエラーチェックに使える)
SELECT AVG(Age) FROM Men	平均年齢を計算する
SELECT MAX(Age) FROM Men GROUP BY Name	Nameごとに年齢の最大値を計算する
SELECT DISTINCT Name FROM Men	Nameの重複を排除してNameを抽出

では解答に移ることにする。

1

a)～c)の解答。DBへのデータの挿入はFor文とタプルを利用した方法でもよいでしょう。

# -*- encoding: utf8 -*-
import sqlite3 as dbapi

con = dbapi.connect('census.db')
cur = con.cursor()

cur.execute('CREATE TABLE Density(State TEXT, Population INTEGER, Area REAL)')

cur.execute('INSERT INTO Density VALUES("Newfoundland and Labrador", 512930, 370501.69)')
cur.execute('INSERT INTO Density VALUES("Prince Edward Island", 135294, 5684.39)')
cur.execute('INSERT INTO Density VALUES("Nova Scotia", 908007, 52917.43)')
cur.execute('INSERT INTO Density VALUES("New Brunswick", 729498, 71355.67)')
cur.execute('INSERT INTO Density VALUES("Quebec", 7237479, 1357743.08)')
cur.execute('INSERT INTO Density VALUES("Ontario", 11410046, 907655.59)')
cur.execute('INSERT INTO Density VALUES("Manitoba", 1119583, 551937.87)')
cur.execute('INSERT INTO Density VALUES("Saskatchewan", 978933, 586561.35)')
cur.execute('INSERT INTO Density VALUES("Alberta", 2974807, 639987.12)')
cur.execute('INSERT INTO Density VALUES("British Columbia", 3907738, 926492.48)')
cur.execute('INSERT INTO Density VALUES("Yukon Territory", 28674, 474706.97)')
cur.execute('INSERT INTO Density VALUES("Northwest Territories", 37360, 1141108.37)')
cur.execute('INSERT INTO Density VALUES("Nunavut", 26745, 1925460.18)')

con.commit()

d)～j)の解答はこちら。基本的なSQL文の練習問題です。j)の計算結果を列として並べて表示するという方法は調べて納得。

# -*- encoding: utf8 -*-

import sqlite3 as dbapi

con = dbapi.connect('census.db')
cur = con.cursor()

con.text_factory = str

# d)の解答
cur.execute('SELECT * FROM Density')
ans_d = cur.fetchall()
print ans_d

# e)の解答
cur.execute('SELECT Population FROM Density')
ans_e = cur.fetchall()
print ans_e # リストの中身は要素1のタプルである

# f)の解答
cur.execute('SELECT State FROM Density WHERE Population < 1000000')
ans_f = cur.fetchall()
print ans_f

# g)の解答
cur.execute('SELECT State FROM Density WHERE \
             Population < 1000000 OR Population > 5000000')
ans_g = cur.fetchall()
print ans_g

# h)の解答
cur.execute('SELECT State FROM Density WHERE \
             NOT(Population < 1000000 OR Population > 5000000)')
ans_h = cur.fetchall()
print ans_h

# i)の解答
cur.execute('SELECT Population FROM Density WHERE Area > 200000')
ans_i = cur.fetchall()
print ans_i

# j)の解答 州の名前と人口密度を表示
cur.execute('SELECT State, Population / Area FROM Density')
ans_j = cur.fetchall()
print ans_j

2

1のDBも使って解答します。まずは次のコードで、データを挿入します。

# -*- encoding: utf8 -*-

import sqlite3 as dbapi

con = dbapi.connect('census.db')
cur = con.cursor()

con.text_factory = str

cur.execute('CREATE TABLE Capitals(State TEXT, Capital TEXT, Population INTEGER)')

# Province/Territory Capital Population
data =(
("Newfoundland and Labrador", "St. John’s", 172918),
("Prince Edward Island", "Charlottetown", 58358),
("Nova Scotia", "Halifax", 359183),
("New Brunswick", "Fredericton", 81346),
("Quebec", "Quebec", 682757),
("Ontario", "Toronto", 4682897),
("Manitoba", "Winnipeg", 671274),
("Saskatchewan", "Regina", 192800),
("Alberta", "Edmonton", 937845),
("British Columbia", "Victoria", 311902),
("Yukon Territory", "Whitehorse", 21405),
("Northwest Territories", "Yellowknife", 16541),
("Nunavut", "Iqaluit", 5236)
)

for d in data:
    cur.execute('INSERT INTO Capitals VALUES(?, ?, ?)', (d[0], d[1], d[2]))

con.commit()

以下、a)～i)までの解答です。

# -*- encoding: utf8 -*-

import sqlite3 as dbapi

con = dbapi.connect('census.db')
cur = con.cursor()

con.text_factory = str

cur.execute('SELECT * FROM Capitals')
ans_a = cur.fetchall()
print ans_a

cur.execute('SELECT Density.Population, Capitals.Population \
FROM Density INNER JOIN Capitals WHERE Density.State = Capitals.State')
ans_b = cur.fetchall()
print ans_b

cur.execute('SELECT Density.Area FROM Density INNER JOIN Capitals \
WHERE Capitals.Population > 100000 AND Density.State = Capitals.State')
ans_c = cur.fetchall()
print ans_c

cur.execute('SELECT Density.Area FROM Density INNER JOIN Capitals \
WHERE Capitals.Population > 500000 AND \
Density.Population *1.0 / Density.Area < 2.0 AND \
Density.State = Capitals.State')
ans_d = cur.fetchall()
print ans_d

cur.execute('SELECT SUM(Area) FROM Density')
ans_e = cur.fetchall()
print ans_e

cur.execute('SELECT AVG(Population) FROM Capitals')
ans_f = cur.fetchall()
print ans_f

cur.execute('SELECT MIN(Capitals.Population) FROM Capitals')
ans_g = cur.fetchall()
print ans_g

# 著者による解答は間違ってそうな気がします。著者はもっとも多い人口の値を求めていますが、
# 求める必要があるのは、人口最大の州の名前です。
cur.execute('SELECT Density.State FROM Density \
WHERE Density.Population IN \
    (SELECT MAX(Population) FROM Density)')
ans_h = cur.fetchall()
print ans_h

cur.execute('SELECT A.State, B.State FROM \
Density A INNER JOIN Density B WHERE \
ABS(A.Population * 1.0 / A.Area - B.Population * 1.0 / B.Area) < 0.5 \
AND A.State < B.State')
ans_i = cur.fetchall()
print ans_i

3

SELECT文の結果を表示すると、空のリストになる。Pythonで1/0を含めるとZeroDivisionErrorになる。

>>> 1/0
Traceback (most recent call last):
  File "<interactive input>"line 1, in <module>
ZeroDivisionError: integer division or modulo by zero
>>> 1 > 0 and 1 / 0
Traceback (most recent call last):
  File "<interactive input>"line 1, in <module>
ZeroDivisionError: integer division or modulo by zero
>>> 1 / 0 and 1 > 0
Traceback (most recent call last):
  File "<interactive input>"line 1, in <module>
ZeroDivisionError: integer division or modulo by zero

4

デフォルト引数を利用することで、外部からパラメータを渡すことができるようになる。もっとチェックするのであれば、query中の?の数とタプルの要素数が一致していることを確認するということが挙げられます。問題文の趣旨から外れていきそうなので、そこまではしませんが。

# -*- encoding: utf8 -*-

def run_query(db, query, param=None):
    '''データベースdbに対してqueryを実行して結果を返す '''

    con = sqlite.connect()
    cur = con.cursor()
    if param != None:
        cur.execute(query)
    else:
        if type(param) == tuple: # タプルのみを受け付ける
            cur.execute(query, param)
    data = cur.fetchall()
    cur.close()
    con.close()
    return data

# example
run_query(db, 'SELECT * FROM Precipitation')
run_query(db, 'SELECT City, Temp FROM Precipitation \
    WHERE Snow >= (?) and Temp > (?)', (s, t))

TopCoder SRM399 Div2 250Pts

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

0からn-1まで番号をつけられた、環状の地下鉄の路線がある。駅0を出て、駅1に到着するのにt[0]という時間がかかる。同様に、駅1を出て駅2に到着するのにt[1]という時間がかかるし、駅n-1を出て駅0に到着するのにはt[n-1]という時間がかかる。駅と駅の間はどちらかの方向に向かってくことができる(訳注：時計回りと反時計回りをイメージしよう)。つまり、ある駅からある駅へ向かうのに、同じ駅を2回以上通らないで向かう方法は2通りあることになる。例えば4つ駅があるものとし、1から3へ向かうのであれば、1-2-3、あるいは1-0-3という向かい方があることになる。前者では移動時間の合計はt[1]+t[2]であり、後者はt[0]+t[3]になる。ある人が別の駅へ向かいたいと思っているとき、その人はいつも速く到着できる方を選ぶ。さて、t[]という移動時間の一覧が与えられたとき、2駅間の移動でどんなに速く動いても最も時間がかかってしまう駅のペアを求め、その移動にかかる時間を返すメソッドを作成せよ。

私の解答はこちら。

public class CircularLine {

 public int longestTravel(int[] t) {
  int[][] dist = new int[t.length][t.length];
  int[] tt = new int[t.length*2];
  for( int i=0 ; i<tt.length ; i++ ){
   tt[i] = t[i % t.length]; // tを2回繰り返したもの
  }
  for( int i=0 ; i<t.length ; i++ ){
   for( int j=0 ; j<t.length ; j++ ){
    // iからjへ向かう距離を計算
    int from = i;
    int to = j;
    if( j<i ){
     from = i;
     to = j + t.length;
    }
    for( int k=from ; k<to ; k++ ){
     dist[i][j] += tt[k];
    }
   }
  }

  int max = 0; // 2駅間の移動でもっともかかる時間
  for( int i=0 ; i<t.length ; i++ ){
   for( int j=i+1 ; j<t.length ; j++ ){
    int minDist = Math.min(dist[i][j], dist[j][i]); // 駅i～j間で最速の移動をしても
    max = Math.max(max, minDist); // 移動にかかる時間の最大値を更新してしまうか?を検討
   }
  }
  return max;
 }

}

得点は147.55/250、1回のsubmitでシステムテストクリア。中央値は約156点。2駅の移動は2次元配列で管理しています。dist[i][j]、dist[j][i]が駅iから駅jへ向かうという意味であり、それぞれ添え字の増える方向に向かった場合、減った方向に向かった場合の2種類の経路でかかる時間になります。したがってdist[i][j]とdist[j][i]のうち、小さい方がある人が選択するルートになります。添字操作が面倒なので、tを2回繰り返すことで、添え字が小さくなる方向への探索を簡単に置き換えることにしています。

TopCoder SRM398 Div2 250Pts

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

A0、X、Y、Mとnという整数が与えられる。以下のルールに従って、数列Aを作成する。

• A[0] = A0
• A[i] = (A[i - 1] * X + Y) % M (0 < i < n)

できあがった数列Aの、2要素の絶対値誤差が最小になる組を求め、その絶対値誤差を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class MinDifference {

 public int closestElements(int A0, int X, int Y, int M, int n) {
  int[] A = new int[n];
  A[0] = A0;
  for( int i=1 ; i<n ; i++ ){
   A[i] = (A[i-1] * X + Y) % M;
  }
  Arrays.sort(A);
  int min = Math.abs(A[1] - A[0]);
  for( int i=1 ; i<n ; i++ ){
   min = Math.min(min, Math.abs(A[i] - A[i-1]));
  }
  return min;
 }

}

得点は246.56/250、1回のsubmitでシステムテストクリア。中央値は約217点。工夫したのは数列Aに対し、ソートするという点で、これにより、絶対値誤差の最小値の候補が隣合う要素のみになるということが挙げられます。

初めてのコンピュータサイエンス第14章解答

第14章練習問題の前半の解答です。以下ネタバレなので、読みたくない方は立ち去りましょう。問題文は載せませんので悪しからず(英語版はpdfで公開されている模様)。日本語版が必要なら買いましょう。

1

このコードは実行すると、ボタンが出てきます。ボタンを押すとアプリケーションが終了するようになっています。

import Tkinter as tk

class Goodbye:
    def __init__(self, parent):
        self.parent = parent
        self.frame = tk.Frame()
        self.frame.pack()

        self.bye = tk.Button(self.frame, text='Good-bye', command=self.byebye)
        self.bye.pack()

    def byebye(self):
        self.parent.destroy()


if __name__ == '__main__':
    window = tk.Tk()
    myapp = Goodbye(window)
    window.mainloop()

2

このコードを実行すると数字が入ったボタンが出てきます。ボタンをクリックすると、表示される値が1ずつ大きくなります。

import Tkinter as tk

class CountUp:
    def __init__(self, parent):
        self.parent = parent
        self.frame = tk.Frame(parent)
        self.frame.pack()

        self.state = tk.IntVar()
        self.state.set(0)

        self.button = tk.Button(parent, text=self.state.get(),
                                command=self.count)
        self.button.pack()

    def count(self):
        self.state.set(self.state.get() + 1)
        self.button.config(text=self.state.get())

if __name__ == '__main__':
    window = tk.Tk()
    app = CountUp(window)
    window.mainloop()

3

x = lambda(): 3を読みやすくせよということなのですが、このコードを実行するとエラーになります。読みやすくする以前の問題で、何がしたいのでしょうか?

4

# -*- encoding: utf8 -*-

import Tkinter as tk

class CountDNA:
    def __init__(self, parent):
        self.parent = parent
        self.frame = tk.Frame()
        self.frame.pack()

        # モデルはATGCの数
        self.dic = {'A' : 0, 'T' : 0, 'G' : 0, 'C' : 0}
        self.message = tk.StringVar()

        # DNAの文字列を表示する
        self.textbox = tk.Text(self.frame, width=30, height=10)
        self.textbox.pack()

        # 数えるボタンを表示する
        self.bt = tk.Button(self.frame, text="数える",
                  command=lambda: self.countATGC(self.dic, self.message))
        self.bt.pack()

        # 数えた結果を表示する
        self.label = tk.Label(self.frame, textvariable=self.message)
        self.label.pack()


    # 出現回数を計算する
    def countATGC(self, dic, msg):
        for (key, value) in dic.iteritems():
            dic[key] = 0

        for c in self.textbox.get('0.0', tk.END):
            if c in dic.keys():
                dic[c] = dic.get(c, 0) + 1
        # print dic
        msg.set(self.printATGC(dic))

    def printATGC(self, dic):
        msg =  u'Aの数:%d Tの数:%d Cの数:%d Gの数:%d' % \
               (dic['A'], dic['T'], dic['C'], dic['G'])
        return msg

if __name__ == '__main__':
    window = tk.Tk()
    app = CountDNA(window)
    window.mainloop()

5

練習ということで、敢えてクラスを使わないで書いてみました。ちなみにこのコードをとあるWebエンジニアに見せたところ、__init__に何もかも押し込むのは、Cで言うところのmainに1000行書くようなものだということで、あまり良い作法でないということを教わりました。機能自体は実現できましたが、更によい書き方を知る必要もありそうです。

# -*- encoding: utf8 -*-

import Tkinter as tk

window = tk.Tk()
frame = tk.Frame(window)
frame.pack()
label = tk.Label(frame, text="華氏表現の温度")
label.pack()

var = tk.DoubleVar()

entry = tk.Entry(frame, textvariable=var) # 数値入力部
entry.pack()

svar = tk.StringVar()

msg = tk.Label(frame, textvariable=svar)
msg.pack()

bt_trans = tk.Button(frame, text="変換", command=lambda: click_trans(var,svar))
bt_trans.pack()

bt_end = tk.Button(frame, text="終了", command=lambda: click_end(window))
bt_end.pack()

def to_celsius(t):
    return (t - 32.0) * 5.0 / 9.0

def click_trans(var,svar):
    try:
        # var.get()が文字列だと例外が発生する
        s_temp = "%.10f" % to_celsius(var.get())
        svar.set(s_temp)
    except:
        svar.set("???")

def click_end(window):
    window.destroy()

window.mainloop()

TopCoder SRM397 Div2 250Pts

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

あなたは敵の暗号を解読しなければならない秘密の任務を負った。既に敵が以下の方法によってメッセージを暗号化しているということをつかんでいる。

• 各文字は'a'から'z'の間の値だけからなり、アルファベットには01～26までの二桁の数字が割り当てられている。メッセージは文字を割り当てられた数字で単に置き換えただけのものである。
• 例えば、tが20、eが05、sが19という数字を割り当てられていたとすれば、"test"という文字列は"20051920"と暗号化される。

codeという数字を文字に対応させたものが与えられる。codeの先頭の文字は01、2番目の文字は02などのように数字が割り当てられている。また、messageという暗号化後あるいは暗号化前の文字列が与えられる。暗号化前であれば暗号化したメッセージを、暗号化後の文字列が与えられているなら暗号化前の元のメッセージを返すようなメソッドを作成せよ。

私の解答はこちら。

public class BreakingTheCode {

 public String decodingEncoding(String code, String message) {
  StringBuilder sb = new StringBuilder();
  // 先頭の文字を見て処理のパターンを変えている
  if( message.charAt(0) >= '0' && message.charAt(0) <= '9'){ 
   for( int i=0 ; i<message.length()/2 ; i++ ){
    // 数字は2桁なので2文字取り出して整数にしておく
    int num = Integer.parseInt(message.substring(i*2, (i+1)*2));
    sb.append(code.charAt(num-1));
   }
  }else{
   for( int i=0 ; i<message.length() ; i++ ){
    char c = message.charAt(i);
    int num = code.indexOf(c) + 1; // 先頭は01から始まることに注意
    String snum = String.format("%02d", num);
    sb.append(snum);
   }
  }
  return sb.toString();
 }

}

得点は231.19/250、1回のsubmitでシステムテストクリア。先頭の文字が数値か否かを判別するには、asciiで'0'以上'9'以下とするよりも、Character.isDigit(0)を使うと良いでしょう。