TopCoder SRM464 Div2 250Pts

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

numRedの赤い箱、numBlueの青い箱、numRedの赤い球、numBlueの青い球を使うゲームをしている。各ボールを箱に入れる。各箱は以下のようにして点数がつけられる。

• 箱が赤で赤い球を含んでいればonlyRed点得る。
• 箱が青で青い球を含んでいればonlyBlue点得る。
• それ以外はbothColors点得る。

合計点はすべての箱の点数の合計である。可能性がある得られる点数の最大値を返せ。

私の解答はこちら。

public class ColorfulBoxesAndBalls {

 public int getMaximum(int numRed, int numBlue, int onlyRed, int onlyBlue, int bothColors) {
  int same = numRed * onlyRed + numBlue * onlyBlue;
  int diff;
  if( numRed < numBlue ){
   diff = bothColors * numRed + bothColors * numRed + onlyBlue * (numBlue - numRed);
  }else{
   diff = bothColors * numBlue + bothColors * numBlue + onlyRed * (numRed - numBlue);
  }
  return Math.max(same, diff);
 }

}

得点は232.88/250、1回のsubmitでシステムテストクリア。可能性があるのは箱と球の色がすべての箱で完全一致した場合と、できるだけ箱と球の色が一致しないようにした場合の2種類のみなので、それらについてのみ点数を検討すればOK。

TopCoder SRM463 Div2 250Pts

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

タロウとハナコはバニーパズルで遊んでいる。1列にウサギが何匹か並んでいて、各ウサギの位置はbunnies[](昇順にソート済)という整数型配列で与えられている。ウサギは次のように1度だけ振る舞う:aとbの位置にいるウサギAとBを選ぶ。AはBを飛び越え2*b-aの位置に飛ぶ。もしその位置にウサギが既にいれば飛ぶことはできない。複数匹のウサギを飛び越えることもできない。以上の条件が成り立つとき、AとBの選び方の総数を返せ。なおAがBを飛び越えるのと、BがAを飛び越えるのは異なるものとする。

私の解答はこちら。

public class BunnyPuzzle {

 public int theCount(int[] bunnies) {
  int n = 0;
  // 左のウサギがその右の位置にいるウサギを飛び越える
  for( int i=0 ; i<bunnies.length ; i++ ){
   if( i == bunnies.length-2 ){ // 一番右の2匹の組は成立するペア
    n++;
    break;
   }
   int cur = bunnies[i];
   int tar = bunnies[i+1];
   int jumpto = bunnies[i] + 2 * (tar - cur);
   if( jumpto < bunnies[i+2] ) n++;
  }
  // 右のウサギがその左の位置にいるウサギを飛び越える
  for( int i=bunnies.length-1 ; i>=1 ; i-- ){
   if( i==1 ){ // 一番左の2匹の組は成立するペア
    n++;
    break;
   }
   int cur = bunnies[i];
   int tar = bunnies[i-1];
   int jumpto = bunnies[i] + 2 * (tar - cur);
   if( jumpto > bunnies[i-2] ) n++;
  }
  return n;
 }

}

得点は166.60/250、1回のsubmitでシステムテストクリア。全部の組を探索する必要はなく、隣り合う2匹に着目するのが簡単と気付くまでちょっと時間がかかりました。

TopCoder SRM462 Div2 250Pts

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

アーチェリーでは、矢を標的に放ち標的の当たった位置によって得点を得る。この問題では、標的はN個の輪と中央の円からなるものとする。輪の幅と中央の円の半径は等しいとする。各目標の位置に割り当てられた得点は整数型の配列ringPoints[]で与えられる。得点は内側から外側へ順に与えられており、添字0は中央の円、添字Nは一番外側の輪の得点である。あなたはアーチェリーを始める。矢を放つたびに標的のランダムな場所に当たり、どの位置にあたる確率も等しいものとする。矢を放ったときの得点の期待値を返せ。

私の解答はこちら。

public class Archery {

 public double expectedPoints(int N, int[] ringPoints) {
  int total = 0;
  for( int i=0 ; i<ringPoints.length ; i++ ){
   // 各位置に当たる割合は内側から順に1, 3, 5, ..., 2N+1となる
   total += ringPoints[i]*(2*i+1); 
  }
  return total*1.0/((N+1)*(N+1)); // 1+3+...+(2N+1)=(N+1)^2で割って正規化
 }

}

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

Rによる統計解析ハンドブック 第8章演習問題解答

This post is solutions of the chapter 8 of `A Handbook of Statistical Analyses Using R, Second Edition'. Chapter 6 and 7 will be posted later.

このポストはRによる統計解析ハンドブック(第2版)の第8章の解答になります。第6, 7章については後日掲載する予定です。

1

Although it is difficult to discern from the histogram, result of which kernel band is 3000 indicates that there are 6 peaks in density function. As kernel band gets lerger, we can't discern all of 6 peaks because they are mixed.

ヒストグラムからは判別しにくいが、カーネル幅が3000のときの結果から、密度関数からは峰が6つあることが示唆される。カーネル幅が大きいと峰が混ざるため、すべて判別できなくなる。

data("galaxies", package="MASS")

oldpar <- par(mfrow=c(2, 2))
do <- function(dat, ker, wid){
  h.info <- hist(dat, plot=FALSE)
  d.info <- density(dat, kernel=ker, width=wid)
  yr <- range(c(0, h.info$density, d.info$y))
  tit <- paste(ker, "kernal width = ", wid, collapse=" ")
  hist(dat, probability=TRUE, ylim=yr, main=tit)
  lines(d.info, lwd=2)
}

do(galaxies, "gaussian", 3000)
do(galaxies, "gaussian", 5000)
do(galaxies, "triangular", 3000)
do(galaxies, "triangular", 5000)
par(oldpar)

2

Data can be seen around (20, 10), and we can see that death rate is constant with birth one.

データは(20, 10)近辺に多く見られ、0.001の等高線からは出生率に関係なく死亡率は一定に近い傾向があることが見て取れる。

library(KernSmooth)
data("birthdeathrates", package="HSAUR2")
bdr.d <- bkde2D(birthdeathrates, bandwidth=sapply(birthdeathrates, dpik))
contour(bdr.d$x1, bdr.d$x2, bdr.d$fhat,
        xlab=names(birthdeathrates)[1], ylab=names(birthdeathrates)[2], 
        main="estimated density of birthdeathrates")

3

Note that plot.Mclust doesn't reflect option such as col and ylim. Graphs show that there is modality for female, and tendency that male develops schizophrenia earlier than female (Note that vertical axis is different between two graphs).

plot.Mclustはcol、ylimなどのオプションを指定しても反映されないことに注意。グラフを見ると、女性は二峰性があり、男性は女性よりも若いころに発症する傾向がある(縦軸の値が異なることに注意)。

library(mclust)
data("schizophrenia", package="HSAUR2")
# previous consideration (事前の考察)
boxplot(age~gender, data=schizophrenia, main="age distribution")
# split data(データの分割)
female <- subset(schizophrenia, gender=="female", select=age)
male <- subset(schizophrenia, gender=="male", select=age)
mc.fem <- Mclust(female)
mc.mal <- Mclust(male)

oldpar <- par(mfrow=c(1, 2))
plot(mc.fem, what="density", xlim=c(0, 70), ylim=c(0, 0.06))
plot(mc.mal, what="density", xlim=c(0, 70), ylim=c(0, 0.06))
par(oldpar)

TopCoder SRM461 Div2 250Pts

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

1000*1000の格子で表された草原がある。最初にウサギは(1, 1)の座標にいる(添字は1から始まる)。ウサギは水平方向と垂直方向の隣り合う地域へ1秒で移動することができ、その方法でのみ動くことができる。さて、あなたはウサギを罠にかけようとしている。そのために、いくつかの罠をしかけた。i番目の罠はtrapX[i]、trapY[i]で与えられ、それぞれ罠のX、Y座標を表している。ウサギが罠にはまる可能性が0とならない経過時間の最小値を返せ(罠にはまるというのは、罠のある位置にウサギが移動することをいう)。

私の解答はこちら。

public class TrappingRabbit {

 public int findMinimumTime(int[] trapX, int[] trapY) {
  int minSum = 2000;
  for( int i=0 ; i<trapX.length ; i++ ){
   minSum = Math.min(minSum, trapX[i]+trapY[i]);
  }
  return minSum-2;
 }

}

得点は246.48/250。1回のsubmitでシステムテストクリア。単純に一番マンハッタン距離の近い罠の座標から2を引くだけです。

TopCoder SRM460 Div2 250Pts

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

あるボリビア人がquestions[]という文字列の内容のインタビューをボリビアで有名なジョンにしたが、インタビューの回答を紛失してしまった。なお、質問の内容はすべてYesまたはNoで答えられるものである。同じ質問をしていることがあるが、ジョンはすべて常に同じ回答をしている。さて、そのボリビア人は質問の内容から回答のパターンをすべて書き出そうとしているのだが、それは全部で何通りになるか計算して返せ。

私の解答はこちら。

import java.util.ArrayList;

public class TheQuestionsAndAnswersDivTwo {

 public int find(String[] questions) {
  ArrayList<String>al = new ArrayList<String>(); // ユニークな質問の文字列をすべて記録
  for( int i=0 ; i<questions.length ; i++ ){
   if( al.contains(questions[i]) == false ) al.add(questions[i]);
  }
  return (int)Math.pow(2, al.size());
 }

}

得点は243.23/250、1回のsubmitでシステムテストクリア。質問の種類数をカウントすればあとは簡単。

TopCoder SRM459 Div2 250Pts

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

平面にsideLengthの長さを持つ正方形を描く、次に円を内接するように描く。その縁の中に内接するように正方形を描く。これを平面にK個の円が現れるまで手続きを繰り返す。各円について他の図に重ならない面積を求め、その面積の合計を返せ。

私の解答はこちら。

public class RecursiveFigures {

 public double getArea(int sideLength, int K) {
  double area = sideLength * sideLength; // 全体の面積
  double currentSideLen = sideLength; // 注目する正方形の辺の長さ
  for( int i=0 ; i<K ; i++ ){
   area -= currentSideLen * currentSideLen; // 正方形の面積を引き
   area += (currentSideLen/2)*(currentSideLen/2) * Math.PI; // 次の円の面積を足す
   currentSideLen = currentSideLen/Math.sqrt(2); // 次の正方形の辺は現時点から1/sqrt(2)倍
  }
  return area;
 }

}

得点は236.29/250、1回のsubmitでシステムテストクリア。ちょっと手順の構成につまりました。もっと単純にできるかもしれないですね。

Rによる統計解析ハンドブック 第5章演習問題解答

This post is solutions of the chapter 5 of `A Handbook of Statistical Analyses Using R, Second Edition'.

このポストはRによる統計解析ハンドブック(第2版)の第5章の解答になります。

1

Estimated values are larger than actual ones for pair of beef and low or that of cereal and high. Otherwise these are lower than that. B, C, L, H in the below graph stand for Beef, Cereal, Low and High.

牛肉で低たんぱく質、穀物で高たんぱく質は推定値が大きめになり、それ以外は推定値が低めに出ている。グラフ中のB、C、LとHはそれぞれBeef、Cereal、LowとHighの頭文字をとったものであることに注意。

data("weightgain", package="HSAUR2")
resid <- weightgain$weightgain - aov(weightgain ~ source + type, data=weightgain)$fitted.values
plot(resid, type="n", main="residuals")
lab <- paste(abbreviate(weightgain[,1],minlength=1),
             abbreviate(weightgain[,2],minlength=1), sep="")
text(resid, label=lab)

2

The result of plot.design shows no effect on gender and learner. So I conducted anova only with race and school. Race is only affects absent days in conclusion. Note that if anova is conducted with all vatiable, f-value of learner is smaller than 1 and it should be pooled.

plot.designからgender、learnerは関係なさそうとなる。そこで、人種、学年のみを使って分散分析を行った。結論としては欠席日数に効いているのは人種であると言える。なお、全変数で分散分析をかけると、learnerのF値が1より小さくプーリングすべきと考えられる。

data("schooldays", package="HSAUR2")
plot.design(schooldays)
aov.res <- aov(absent ~ race * school,  data=schooldays)
anova(aov.res)
interaction.plot(schooldays$race, schooldays$school, schooldays$absent)

> anova(aov.res)
Analysis of Variance Table

Response: absent
             Df  Sum Sq Mean Sq F value    Pr(>F)    
race          1  2645.7 2645.65 12.4615 0.0005561 ***
school        3  1325.5  441.85  2.0812 0.1052455    
race:school   3  3738.2 1246.08  5.8693 0.0008221 ***
Residuals   146 30996.7  212.31                      
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1 

3

By executing below code, we find that the hypothesis of the uniformity of mean values are rejected between any two groups.

以下のコードを実行すると、任意の2グループ間で、平均値の同等性の仮定は棄却されることが分かる。

data("students", package="HSAUR2")
students.manova <- manova(cbind(low, high) ~ treatment, data=students)
summary(students.manova, test="Hotelling-Lawley") # p-value is very small!
summary.aov(students.manova)

summary(manova(cbind(low, high) ~ treatment, data=students, 
        subset = treatment %in% c("AA", "C")))
summary(manova(cbind(low, high) ~ treatment, data=students, 
        subset = treatment %in% c("C", "NC")))
summary(manova(cbind(low, high) ~ treatment, data=students, 
        subset = treatment %in% c("NC", "AA")))

TopCoder SRM458 Div2 250Pts

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

砂漠化がボブの島では深刻な問題である。ボブの島はセルの格子が長方形になっている。island[]というボブの島の状態が与えられる。i番目の要素のj番目の文字が島のi行j列の土地の状態を表し、Dが砂漠、Fが森を表す。砂漠の広がり方は1年後に砂漠が上下左右のセルに広がるというものである。砂漠はつねに砂漠でありつづける。T年後の砂漠のセル数を返すメソッドを作成せよ。

私の解答はこちら。

public class Desertification {

 public int desertArea(String[] island, int T) {
  int nRow = island.length;
  int nCol = island[0].length();
  int S = nRow * nCol; // セルの総数
  boolean[][] isDesert = new boolean[nRow][nCol]; // 今年砂漠かを記録
  boolean[][] nextDesert = new boolean[nRow][nCol]; // 翌年砂漠かを記録

  for( int i=0 ; i<nRow ; i++ ){ // 砂漠の位置を記録
   for( int j=0 ; j<nCol ; j++ ){
    if( island[i].charAt(j) == 'D' ) isDesert[i][j] = true;
   }
  }
  if( countTrueGrid(isDesert) == 0 ) return 0; // 砂漠がなければ砂漠はできないので0で終了

  for( int t=0 ; t<T ; t++ ){ // 砂漠の位置を拡散する
   for( int i=0 ; i<nRow ; i++ ){
    for( int j=0 ; j<nCol ; j++ ){
     if( isDesert[i][j] == true ){
      nextDesert[i][j] = true;
      if( i-1 >= 0 ) nextDesert[i-1][j] = true;
      if( j-1 >= 0 ) nextDesert[i][j-1] = true;
      if( j+1 < nCol ) nextDesert[i][j+1] = true;
      if( i+1 < nRow ) nextDesert[i+1][j] = true;
     }
    }
   }
   for( int i=0 ; i<nRow ; i++ ){
    for( int j=0 ; j<nCol ; j++ ){
     isDesert[i][j] = nextDesert[i][j];
    }
   }
   if( countTrueGrid(isDesert) == S ) return S; // 全部砂漠になったら終了
  }

  int nTrue = 0;
  for( int i=0 ; i<nRow ; i++ ){ // 最後の砂漠のセル数を数える
   for( int j=0 ; j<nCol ; j++ ){
    if( isDesert[i][j] ) nTrue++;
   }
  }
  return nTrue;
 }

 private int countTrueGrid(boolean[][] bl){ // 現在の砂漠のセル数をカウントする関数
  int n = 0;
  for( int i=0 ; i<bl.length; i++ ){
   for( int j=0 ; j<bl[i].length ; j++ ){
    if( bl[i][j] ) n++;
   }
  }
  return n;
 }

}

得点は203.52、1回のsubmitでシステムテストクリア。Tが10億まで取れるので、Tが大きい値になったときの対処が必要です。

TopCoder SRM457 Div2 250Pts

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

ジョンとブラスはパズルが好きである。彼らは正方形の盤面にチェッカーを置く新しいゲームをしている。盤面は格子状で同じ数の行と列を持つ。ゲームはジョンがチェッカーを盤面のセルに置くことから始まる。つぎにR[i]が各行iに対して計算される。R[i]はi番目の行にあるチェッカーの数である。盤面のi列目のチェッカーの数がR[i]になるようにブラスはチェッカーを動かさなければならない。R[i]はチェッカーの初期配置から計算され、途中で修正されないことに注意。1回のターンでブラスはチェッカーを上下左右の空いているセルに動かすことができる。目標に届くまで必要なターンを使うであろう。board[]という文字列型配列が与えられる。i番目の要素のj番目が'C'であれば盤面のi行j列のセルにチェッカーがあり、そうでなければ'.'となっている。最後の配置の状態を入力と同じ形式を使って返せ。配収的な配置は多い可能性があるので、辞書順で最も早くなるものを返せ。

私の解答はこちら。

public class TheSquareDivTwo {

 public String[] solve(String[] board) {
  int size = board.length; // 行、列のサイズ
  char[][] cells = new char[size][size]; // i行j列のセルに入る値を記録
  int[] nC = new int[size]; // 各列方向にいくつ置くかを記録する
  for( int i=0 ; i<board.length ; i++ ){
   for( int j=0 ; j<size ; j++ ){
    if( board[i].charAt(j) == 'C' ) nC[i]++;
   }
  }
  // 列ごとに配置。辞書順で最初に来る物ということなので、上に'.'、下に'C'が
  // 来るようにする必要がある。'C'の数はnC[i]を参照すればよい。
  for( int j=0 ; j<size ; j++ ){
   for( int i=0 ; i<size ; i++ ){
    if( size - nC[j] - i > 0 ){
     cells[i][j] = '.';
    }else{
     cells[i][j] = 'C';
    }
   }
  }
  for( int i=0 ; i<size ; i++ ){ // 文字型配列を文字列に変換
   board[i] = String.valueOf(cells[i]);
  }
  return board;
 }

}

得点は169.41、1回のsubmitでシステムテストクリア。本文は分かりにくかったのですが、出力例を見てアルゴリズムをようやく理解。

2013年1月の学習記録

2013年1月に学習した主な本一覧。今年度も終盤に差し掛かってきました。

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

とりあえずdone。次はHoggの本でも読もうかな?

カウントデータの統計解析(pp.153～189読了)

統計検定1級と同じデータが出てきてて、著者が出題者でもあったので、あーなどと思いながら最後まで読みました。

Beautiful Visualization(pp.26～読了)

データ可視化のためのTips集。まだこの分野は未開な感じがしました。芸術の側面もあるので、これ!と言い切れる手法が確立されて無いのかなと思います。

Rによる統計解析ハンドブック(pp.1～100)

少しでも統計の本を読み終えてから読みましょう。解答がないので、自作中。

詳解C言語 ポインタ完全攻略(pp.1～260)

思い出すために読書中。相変わらずポインタは紛らわしいですね。

はじめての集合と位相(pp.1～12)

とりあえず1章だけ。章末の問題に解答があると親切なのですがね...

その他、TopCoderの過去問を6問解く。線形空間の本を読もうかとも思ったが、まだ知らない位相を学ぶ本を読む方針に変更した。英文ドキュメント翻訳の作業は約65%まで到達。Ruby on Railsを触ってみたいと思うのですが、近いうちに次のバージョンが出るので、そのときに出版された書籍を買って読みたいかなと思います。