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を触ってみたいと思うのですが、近いうちに次のバージョンが出るので、そのときに出版された書籍を買って読みたいかなと思います。