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ページほど読みました。