TopCoder SRM181 Div2 250Pts

そろそろ500Ptsの問題にも挑戦したいが、その準備のための勉強も必要なので、とりあえず一番簡単な問題を解いてコードを晒してみる。

本日の問題はこちら(要TopCoder登録 & 問題文は英語)。

問題を大まかに和訳してみる。
2次元横スクロールゲームで、ボスと戦う。ボスは様々な高さに銃を撃ち込むことができる。kilomanは飛ぶことと、立ったままでいることの2種類の行動をとることができる。kilomanが立ったままで、ボスが1-2に銃を撃った場合はヒットとなり、kilomanがジャンプして、ボスが3-7に撃った場合もヒットになる。ボスの攻撃パターンpattern[]と、立ったままか飛んだかを表す文字列jumpsが与えられたときに、何回kilomanはボスの攻撃にヒットしたかを返すメソッドhitsTakenを作成せよ。クラス名はKiloManとする。

私の作成した解答は以下のとおりである。

public class KiloMan {

 public int hitsTaken(int[] pattern, String jumps) {
  int nHits = 0;
  for( int i=0 ; i<pattern.length ; i++){
   if( jumps.charAt(i)=='S' && pattern[i]<=2 ){
    nHits++;
   }else if( jumps.charAt(i)=='J' && pattern[i]>=3){
    nHits++;
   }
  }
  return nHits;
 }

}

得点は226.33/250。毎度ながら文字列の比較ではまってしまう。equalsメソッドを使うと思っていたら、単純な比較で済んでしまうというオチ。charはプリミティブな型だから、equalsではなく、単純比較でよいということなのね。

R言語のtry関数に関する調査

try関数というのは、エラーがあってもとにかく実行して処理を停止させないための仕組みである。もちろん実行後に改めて停止させることもできる。tryよりも柔軟な処理ができるtryCatchという関数も存在するが、使いやすいtry関数について説明する。try関数の呼び出し方は次の通りである。

try(expr, silent = FALSE)

try関数は、まずexprを評価する。exprによりエラーが発生した場合には、options("show.error.messages")がfalseか、silentがTRUEでない限り、エラーメッセージを吐き出す。関数の返り値はエラーが発生しなければ、評価の結果を返し、エラーが発生した場合にはエラーメッセージを含んだ"try-error"というクラスのオブジェクトを返してくる。次の例をご覧いただきたい。2倍した値を表示しようとしているのだが、-1のときにstopを返すので、最後の2が処理できない状態になっている。

twice <- function(x){
 if( x < 0 ) stop("Negative Number")
 return(2*x)
}

for(i in c(3:-1,2)){
 print(twice(i)) # このままでは最後の2は処理できない
}

出力結果

[1] 6
[1] 4
[1] 2
[1] 0
 以下にエラー twice(i) : Negative Number

上の場合は途中で止まってしまうが、tryの返したオブジェクトのクラスを参照して、その結果に応じて処理をすることで、最後まで処理できるようにしたのが以下の例である。ループの最後の要素2を2倍した4も得られていることが確認できる。

for(i in c(3:-1,2)){
 val <- try(twice(i))
 if( class(val) != "try-error" ){
  print(val) # stopしないので、2倍の値が入る
 }
}

出力結果

[1] 6
[1] 4
[1] 2
[1] 0
Error in twice(i) : Negative Number
[1] 4

R言語のwith関数の調査

まずは導入ということで、attach関数について説明する。attach関数を利用すると、detach関数を呼び出すまで、データフレームの列名を書くだけで、列を指定したことと同じになる。

> attach(iris)
> lm.obj <- lm(Sepal.Length~Sepal.Width) # iris[,"Sepal.Length"]などとしなくてもよい
> detach(iris)
> Sepal.Length # エラー
 エラー：  オブジェクト 'Sepal.Length' がありません
> lm.obj

Call:
lm(formula = Sepal.Length ~ Sepal.Width)

Coefficients:
(Intercept)  Sepal.Width  
     6.5262      -0.2234  

次にwith関数の定義を示す。

with(data, expr, ...)

with関数はdataから構成された環境で評価するというものであるが、言い換えると、with関数の内部に限ってexprはattach(data)としたのと同じになるということである。つまり、上の回帰分析のコードは次のように書くこともできる。

> lm.obj2 <- with(iris,lm(Sepal.Length~Sepal.Width))
> all.equal(lm.obj,lm.obj2) # 回帰分析で得られたオブジェクトを比較、一致している
[1] TRUE

どちらを使うべきかという判断は難しいが、attach/detachを利用する場合は、attachしている最中にオブジェクト名を混同しないようにしなければならないことだけは間違いない。

R言語のouter関数で3次元plot

R言語のouter関数を使うと、3次元plotが簡単にできるので、その方法について紹介。まずはouter関数の呼び出し方は以下の通りである。

outer(X, Y, FUN="*", ...)

XとYの組み合わせに対してFUNを適用するようになっている。関数の返り値はX、Yがベクトル(ベクトル以外でも利用できるが、ベクトルで十分な場合が多い)であれば、2次元で表されるマトリックスになる。

> x <- 1:3
> y <- 1:5
> outer(x,y) # FUNを省略すると掛け算になる
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    2    3    4    5
[2,]    2    4    6    8   10
[3,]    3    6    9   12   15

これを用いると、(x,y)であらわされる座標に対しFUNを適用することでz=FUN(x,y)が得られ、x,y,zで3次元のグラフが描けるということが理解していただけると思う。試しに2次元標準正規分布を描いてみることにしよう。2次元分布生成のコードは舟尾暢男氏のR-Tipsにあるものを参考にさせていただいた。

x <- seq(-3,3,length=100)
y <- x
rho <- 0.9
gaussDist <- function(x,y,rho) {
  1/(2*pi*sqrt(1-rho^2))*exp(-(x^2-2*rho*x*y+y^2) / (2*(1-rho^2)))
}
z <- outer(x,y,gaussDist,rho)
filled.contour(x,y,z)

最後のfilled.contourによって、連続的な色で表現される等高線を描くようにしている。グラデーションを用いず、線だけでよいという場合にはcontour関数でよい。contour関数では、標高を表す数値はグラフの外でなく、よくある地図のように、数値が内部に書かれるようになる。

図を見れば明らかであるが、相関が強いため、確率密度の高い箇所が直線状に現れている。無相関になるにつれて、確率密度の等高線は直線から円に変化する。

R言語のby関数の調査

以前から気になっていたR言語のbyという関数についての調査。呼び出し方は以下の通り。

by(data, INDICES, FUN, ..., simplify = TRUE)

ヘルプによると、by関数はdataをINDICESごとにグループごとに区切り、FUNを適用するということになるらしい。また、返り値はsimplifyがTRUEで、かつ関数FUNが返す値がスカラーの場合はスカラー、それ以外はリスト形式になるようである。
試しにexample(by)としてみると、INDICESにリストを指定している場合がある。

by(warpbreaks[, 1], list(wool = wool, tension = tension), summary)

2番目の引数であるlistによって、複数の列をキーにしてdataを分けるということが可能である。ただし、注意しなければならないのは、listで指定した各列の直積をとってくるので、存在しない組み合わせに対してFUNを実行してしまう可能性がある。そういったことを避ける場合には、例えば複数列をpaste関数で一つの文字列にしてしまうといった操作が考えられる。以下のようにlistの内容を変更するのである。

by(warpbreaks[, 1], list(paste(wool,tension,sep="_"), summary)

過去にはグループごとに複数の統計量を返す方法の検討という記事を書いた。こちらではby関数を用いない場合の処理方法を紹介している。

TopCoder SRM180 Div2 250Pts

本日の問題はこちら(要TopCoder登録 & 問題文は英語)。

問題のおおまかに説明する。問題文に登場するDinkyFishというのは小魚という意味である。

小魚を水槽で飼う。オスとメスを水槽に入れておくと必ずつがいができ、毎月カップルにはオスとメスが1匹ずつ生まれる。ただし、水槽で飼うに当たり1匹あたり少なくとも0.5リットルの水が必要である。小魚は混んだ場所では生活できないのである。水槽の容量tankVolume(単位:リットル)、初期のオス、メスの投入量maleNum、femaleNumが与えられたときに混んだ状態になる直前になるまで何か月かかるかを計算して返すメソッドmonthsUntilCrowdedを作成せよ。

気を付ける点としては、0ヶ月目から飼える数の上限を超えてないかという判定を行うこと、1匹につき0.5リットルの水なので、2*tankVolumeが飼える小魚の数の上限を表すということぐらい。易問。

public class DinkyFish {
 public int monthsUntilCrowded(int tankVolume, int maleNum, int femaleNum) {
  int maxNum = 2*tankVolume;
  int minNum = 0;
  int i;
  for( i=0 ; (maleNum+femaleNum)<=maxNum ; i++){
   minNum = Math.min(maleNum, femaleNum);
   maleNum += minNum;
   femaleNum += minNum;
  }
  return i;
 }
}

得点は232.62/250と比較的高速。単純なので特にコメントはない。