TopCoder SRM471 Div2 250Pts

このTopCoderの問題は検索にかけても現れないのですが、簡単に説明してみます。

エリーは"2で割る"問題が大好きである。これにより彼女は2で割らなければならない問題を意味している。エリーはそれ自身が素数を含む数があることに気づいた。数XがYという数字を持つというのは、Y=X/2^k(非負の整数kで割って、切り捨てられたもの)を満たしているときをいう。エリーはすべての正の整数を"prime container"と呼び、その数が含む素数の数をprime containerの大きさと定義した。例えば、7の大きさは2である。これは7/1=7、7/2=3がともに素数だからである(訳注：これを続けると7/2^2=1なので素数にならない)。同様に47は5、959は6が得られる。正の整数Nが与えられたとき、その数のprime containerの大きさを求めることでエレノラを手伝え。

私の解答はこちら。

public class PrimeContainers {

 public int containerSize(int N) {
  int ans = 0;
  for( int i=1 ; i<=N ; i=i*2 ){
   int target = N / i;
   if( isPrime(target) && target >= 2 ){
    ans++;
   }
  }
  return ans;
 }

 boolean isPrime(int n){ // 素数か判定するプログラム
  int end = (int)Math.sqrt(n);
  for( int i=2 ; i<=end ; i++ ){
   if( n % i == 0 ) return false;
  }
  return true;
 }
}

得点は218.65/250、1回のsubmitでシステムテストクリア。後半の英文の意味が拾いにくかったので、意訳してしまいました。

Rでノンパラメトリック法 1

Nagoya.R #10にて、「Rでノンパラメトリック法 1」と題して発表してきました。1冊の本が終わるか私が納得するまでシリーズとして続ける予定なので、2回目以降もきっとあるはずということで1とスライドの題名につけました。今回はノンパラメトリックな手法として符号検定とウィルコクソンの符号付き順位和検定を取り上げています。手計算とRでの実行結果が一致することを確認しながら、理屈を知ろうという内容になっております。

Rでノンパラメトリック法 1 from itoyan110

TopCoder SRM470 Div2 250Pts

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

巡回しているセールスマンはLinear王国で製品を売ろうとしている。Linear王国は座標系にNの街がある。各街は点であり、i番目の街は(x[i], y[i])にある。Linear王国のすべての街は共線性がある、すなわちすべての街を通るまっすぐの線が存在することを意味する。巡回セールスマンはすべての街を訪問しようとしている。2つの街を移動するのに必要な距離はマンハッタン距離に等しい。任意の街から移動し、任意の街で移動を終えるとしたとき、セールスマンが移動しなければならない距離の最小値を返せ。

私の解答はこちら。

public class LinearTravellingSalesman {

 public int findMinimumDistance(int[] x, int[] y) {
  int[] minDist = {0, 0};
  boolean isStart = true;
  int[] prev = {0, 0};
  boolean[] isUsed = new boolean[x.length];
  for( int i=0 ; i<x.length ; i++ ){
   int target = -1;
   int minx = 10001;
   for( int j=0 ; j<x.length ; j++ ){
    if( isUsed[j] == false && x[j] < minx ){
     target = j;
     minx = x[j];
    }
   }
   if( !isStart ){
    minDist[0] += ( Math.abs(x[target] - prev[0]) +  Math.abs(y[target] - prev[1]));
   }
   prev[0] = x[target];
   prev[1] = y[target];
   isStart = false;
   isUsed[target] = true;
  }

  for( int i=0 ; i<x.length ; i++ ){
   isUsed[i] = false;
   isStart = true;
  }
  prev[0] = 0; prev[1] = 0;
  
  for( int i=0 ; i<x.length ; i++ ){
   int target = -1;
   int minx = 10001;
   for( int j=0 ; j<x.length ; j++ ){
    if( isUsed[j] == false && y[j] < minx ){
     target = j;
     minx = y[j];
    }
   }
   if( !isStart ){
    minDist[1] += ( Math.abs(x[target] - prev[0]) +  Math.abs(y[target] - prev[1]));
   }
   prev[0] = x[target];
   prev[1] = y[target];
   isStart = false;
   isUsed[target] = true;
  }
  
  return minDist[0] < minDist[1] ? minDist[0] : minDist[1];
 }

}

得点は183.36/250、1回のsubmitでシステムテストクリア。PCが壊れる前に解き、コメントがないので解き方の方針は忘れてしまいました(苦笑)

TopCoder SRM469 Div2 250Pts

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

ジョンとブラスはとても面白い映画を見に行こうとしている。彼らは同じ並びの隣り合った席に座りたいと思っている。映画館はn行m列のシートからなる。行方向は先頭から最後尾へ向けて1からnと番号づけられ、左から右に1からmと順に番号づけられている。いくつかのシートは既に埋まっており、ジョンとブラスは任意の空いている席を予約することができる。row、seatという整数型の配列が与えられ、そのi番目の要素row[i]、seat[i]は予約された席の位置を示している。すべての残りの席は空いている。ジョンとブラスが同じ並びで隣り合って座ることができる場合の数を返せ。なお、ジョンとブラスの位置までは考慮しないものとする。つまりジョンとブラスが逆に座っても同じ席の予約なので1通りとしてカウントするということである。

私の解答はこちら。

public class TheMoviesLevelOneDivTwo {

 public int find(int n, int m, int[] row, int[] seat) {
  boolean[][] isReserved = new boolean[n][m];
  for( int i=0 ; i<row.length ; i++ ){
   isReserved[row[i]-1][seat[i]-1] = true;
  }
  int nSeat = 0;
  boolean isPrevReserved = true;
  int nFree = 0;
  for( int i=0 ; i<n ; i++ ){
   nFree = 0;
   isPrevReserved = true;
   for( int j=0 ; j<m ; j++ ){
    if( isReserved[i][j] ) {
     isPrevReserved = true;
     nFree = 0;
    }else{
     isPrevReserved = false;
     nFree++;
    }
    if( nFree >= 2 ) nSeat++;
   }
  }
  return nSeat;
 }

}

得点は220.85/250、1回のsubmitでシステムテストクリア。「並び」、「行」と訳したのですが、まとめた方がよかったですかねぇ。

TopCoder SRM468 Div2 250Pts

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

王は長いこと外におり、妃の元へできるだけ早く戻りたいと思っている。王は街0におり、妃は街Nにいる。0からN-1の間の値をとる各iにおいて、街iと街i+1を結ぶ道と空路が存在する。i番目の要素がiからi+1へ向かうのに陸路でかかる時間を表すroadTime[]と、空路でかかる時間flightTime[]が与えられる。しかし、空路を選ぶことは王国における技術的な制限により王の命に危険がある。したがって、妃は王に最大でK回のフライトにするように頼んでいる。王が妃のもとにたどり着くまでにかかる最小の時刻を計算して返せ。

私の解答はこちら。

import java.util.Arrays;

public class RoadOrFlightEasy {

 public int minTime(int N, int[] roadTime, int[] flightTime, int K) {
  int[] diff = new int[N];
  int time = 0;
  for( int i=0 ; i<N ; i++ ){
   diff[i] = roadTime[i] - flightTime[i];
  }
  for( int i=0 ; i<N ; i++ ){
   time += roadTime[i];
  }
  Arrays.sort(diff);
  if( diff[N-1] <= 0 ) return time;
  int k = 0;
  for( int i=N-1 ; i>=0 ; i-- ){
   if( k >= K || diff[i] <= 0 ) break;
   time -= diff[i];
   k++;
  }
  
  return time;
 }

}

得点は201.00/250、2回目のsubmitでシステムテストクリア。最後に「|| diff[i] <= 0」を付け忘れての失敗。方針としては、iからi+1へ陸路と空路で向かった時にかかる時間の差をとり、空路の方が速いものから、最大K個とるというものである(実際の計算では陸路で全部向かったと仮定して、差分だけ引き算するようにしている)。ただし、速い方からK個とるうちに、陸路の方が速く到着するようであれば、それ以上は空路を選択せずに終了とする。

TopCoder SRM467 Div2 250Pts

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

SuperSumは次のように定義される関数である:

• すべての正数nに対して、SuperSum(0, n) = n
• 任意の正数n, kに対しSuperSum(k, n) = SuperSum(k-1, 1) + SuperSum(k-1, 2) + ... + SuperSum(k-1, n)

さて、kとnが与えられたとき、SuperSum(k , n)の値を求めよ。

私の解答はこちら。

public class ShorterSuperSum {

 public int calculate(int k, int n) {
  return SuperSum(k, n);
 }
 
 private int SuperSum(int k, int n){
  int num = 0;
  if( k <= 0 ) return n;
  for( int i=1 ; i<=n ; i++ ){
   num += SuperSum(k-1, i);
  }
  return num;
 }

}

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

2013年6月の学習記録

ようやくWindows機を購入。これでやる気が回復するか!?そして積読候補をまた増やしてしまいました。実務に関連しそうなので、ついでにやってしまおうと思っているのですが、どこまでできることやら。

CentOS 6で作るネットワークサーバ構築ガイド

メールサーバ、メーリングリストサーバの調査で50ページほど読みました。

ノンパラメトリック統計入門(pp.137〜210)

適合度検定について。Rで使えば一発で結論は出るが、その裏のアイディアを知ることができます。適合度検定は定番の分析手法で基本的なテキストなら大概出てくるのですが、どの本にも自由度の説明がないんですよね。具体的にはカテゴリ数がrとcだけある場合に、適合度検定を行うと自由度が(r-1)*(c-1)のカイ二乗分布に従うということなのですが、この証明があるテキストは何処？

その他、「統計学が最強の学問である」を半分ほど。適用範囲の広さだけなら最強かも。