TopCoder SRM412 Div2 250Pts

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

ファイルシステムには、使用したディスク容量がかならずしもファイルサイズに一致しないことがある。これはディスクが等しいサイズのクラスタに分けられており、各クラスタは1つのファイルしか利用できないためである。例えば、クラスタサイズが512バイトの場合、ファイルが600バイトであれば、2つのクラスタでファイルを保存することになる。これら2つのクラスタは他のファイルと領域を分け合うことはなく、全体として1024バイトのディスク容量を使用することになる。sizes[]という1つのファイルサイズを表す整数型配列と、clusterSizeというファイルシステムのクラスタサイズが与えられたとき、与えられたファイルで使用することになるディスク容量の合計値を返すメソッドを作成せよ。

私の解答はこちら。

public class TrueSpace {

 public long calculateSpace(int[] sizes, int clusterSize) {
  long nSpace = 0;
  for( int i=0 ; i<sizes.length ; i++ ){
   long spaceNeeded = (int)Math.ceil(sizes[i]*1.0/clusterSize);
   nSpace += spaceNeeded;
  }
  return nSpace*clusterSize;
 }

}

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

TopCoder SRM411 Div2 250Pts

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

ボニーは好きな数学の授業で、非負の整数には、二つの非負の整数の2乗和で表されるものがあるということを習った。例えば、13=2*2+3*3という具合である。ボニーはのちに、そのような数が2通り以上の分割方法があるということを発見した。例えば25=0*0+5*5=3*3+4*4ということである。ボニーは整数に対し、異なる非負の整数の二乗和で表されるパターンの数を得点と定義することにした。二つの二乗の数を足す順序は異なっても同じものと扱う。これにより、25のスコアは2、2のスコアは1となる(2=1*1+1*1)。また、1のスコアは1、0のスコアは1となる。ボニーは以下の問題を解くのにあなたの手伝いを必要としている。ボニーはlowerBound以上、upperbound以下の整数でスコアが最大となる整数を見つけたいというのである。もし、複数の整数が最高スコアになった場合は、それらの数の中で最大になるようなものを求めるようにせよ。

私の解答はこちら。

public class MaximumScoredNumber {

 public int getNumber(int lowerBound, int upperBound) {
  int largest = lowerBound; // スコアが最大になる整数
  int maxscore = 0; // スコアの最大値
  for( int num=lowerBound ; num <= upperBound ; num++ ){
   int score = 0;
   int range = (int)Math.sqrt(num) + 1;
   for( int i=0 ; i<range ; i++ ){
    for( int j=i ; j<range ; j++ ){ // j=iからにすることで、順序が違うだけの計算を省ける
     if( i*i + j*j == num ) score++;
    }
   }
   if( score >= maxscore ){ // スコアが現在の値に並ぶか超えたら更新
    maxscore = score;
    largest = num;
   }
  }
  return largest;
 }

}

得点は238.06/250、1回のsubmitでシステムテストクリア。中央値は約151点。

TopCoder SRM407 Div2 500Pts

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

あなたは巨大な会社の人事部で働いている。各労働者は、、直属の上司と直属の部下のどちらかが常にいる(両方いることもある)。もちろん、部下は部下を持つこともあるし、上司はさらに上司を持つ頃もある。XがYのボスであるとは、雇用者A、B、...、Dがおり、XがAの上司、AがBの上司、...、DがYの上司であることをいう。もちろん、XがYの直属の上司である場合もXはYのボスになる。もし、AがBのボスである場合、BはAのボスにはなれないものとする。新しい会社の方針によると、部下のいない労働者の給与は1である。もし、部下を持つ労働者がいれば、その人の給与は直属の部下の給与の合計になる。

relations[]というi番目の文字列のj番目の要素がYであれば、iがjの直属の上司であることを表すというような文字列が与えられたとき、全労働者の給与を返すようなメソッドを作成せよ。なお、Yでない位置の文字列の内容はNになる。自身は自身の上司にならないので、i番目の文字列のi番目の要素は必ずNになる。

私の解答はこちら。再帰を用い、各労働者が何人の部下を持つかを見つけるようにしています。

public class CorporationSalary {

 public long totalSalary(String[] relations) {
  long total = 0;
  long[] salary = new long[relations.length]; // 給与は0で初期化しておく
  for( int i=0 ; i<relations.length ; i++ ){
   total += calc_salary(relations, i, salary);
  }
  return total;
 }
 // i番目の人の給与を計算する関数
 // salary[]は給与を記録するためのテーブルと思ってよい
 private long calc_salary(String[] relations, int i, long[] salary){
  if( relations[i].indexOf("Y") < 0 ){
   return 1; // 部下がいない場合
  }
  long total = 0;
  long ret = 0;
  for( int j=0 ; j<relations[i].length() ; j++ ){
   if( relations[i].charAt(j) == 'Y' ){ // 部下がいた場合
    // 0でないということは給料が分かっている場合、その人の給与は計算済み、既知である
    if( salary[j] > 0 ){
     total += salary[j];
    }else{
     ret = calc_salary(relations, j, salary); // 再帰処理
     total += ret;
     salary[j] = ret; // j番目の人の給料をセット
    }
   }
  }
  return total;
 }
}

得点は150.0/500、何度もトライしました。再帰で時間がかかりすぎるというのが問題の原因だったので、計算結果を途中で入れるようにして解決。これにより2秒で処理が終わらなかったテストケースが、4msecで終わるようになりました。

TopCoder SRM410 Div2 250Pts

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

最新のマイクロコントローラーをできるだけ安くするため、ACMEウィジェットカンパニーはとても単純なキャッシュのデザインを行った。プロセッサはnバイトからなる遅いメモリシステムにつながっており、そのnバイトは0～n-1と値をつけられている。速いアクセスが可能なキャッシュは一度にkバイト保持することができる。キャッシュはベースアドレス（後程説明する）を持っており、base～base+k-1まで値がついたバイトのコピーを保持する。プログラムが1バイトを読み込んだとき、キャッシュコントローラーは以下のアルゴリズムを実行する。

• 現在のベースアドレスと新しいベースアドレスが最小になるよう、要求されたバイトを含む新しいkバイトの範囲を見つける。もし、要求されたバイトがキャッシュの中にあれば、ベースアドレスの変更は必要ない。
• 新しい範囲にあるバイトの内容をメモリシステムから読み込み、キャッシュを新しい内容に更新する。古いメモリ範囲で、新しいメモリ範囲に含まれない範囲は捨てるものとする。
• プログラムに要求されたバイトを返す。

プログラムのパフォーマンスを分析するために、メモリシステムから何バイトが読まれたかを知りたい。プログラムが読むバイトはaddresses[]という整数型配列で与えられる。これはメモリから読みだされる順序で値が格納されている。また、プログラムが始まるとき、ベースアドレスは0にあるものとする。addresses[]で指定されたアドレスをすべてキャッシュに順に取り込んだとき、全部でメモリから何バイトを読み込んだかを返すメソッドを作成せよ(訳注：この文章は元の問題文にはありませんが、実行例に具体的に書いているので、こちらで補足しておきます)。

私の解答はこちら。

public class ContiguousCacheEasy {

 public int bytesRead(int n, int k, int[] addresses) {
  int[] range = new int[2];
  int nRead = 0;
  range[0] = 0;
  range[1] = k-1;

  for( int i=0 ; i<addresses.length ; i++ ){
   if( range[0] <= addresses[i] && addresses[i] <= range[1] ) continue;
   if( addresses[i] < range[0] ){
    int readBytes = range[0] - addresses[i] < k ? range[0] - addresses[i] : k;
    nRead += readBytes;
    range[0] = addresses[i];
    range[1] = addresses[i] + k - 1;
   }else if( addresses[i] > range[1] ){
    int readBytes = addresses[i] - range[1] < k ? addresses[i] - range[1] : k;
    nRead += readBytes;
    range[0] = addresses[i] - k + 1;
    range[1] = addresses[i];
   }
  }
  return nRead;
 }

}

得点は190.64/250、1回のsubmitでシステムテストクリア。中央値は約114点。難しいのは実装よりも文章でした。

TopCoder SRM409 Div2 250Pts

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

ジョニーは64センチメートルの棒を持っていて、これをxセンチメートルにすれば棒を使った遊びがもっとたのしくなるであろうと考えた。ジョニーは元の棒を小さい棒に分け、ちょうどxセンチメートルになるようにそれらをくっつけることにした。棒を分割するもっとも単純な方法は半分に分けることなので、ジョニーは以下の手順を利用することにする。

• 全部の棒の長さの総和を取る。これがxよりも大きいうちは次の手順を取る。
  • 一番短い長さの棒を半分にする
  • もし半分にしたものの一つを捨てても、残りの棒の長さがxを下回らないようであれば、それを捨てる。
• 最後に、ちょうどxセンチメートルの棒になるように、残った棒をくっつけていく。

ジョニーが上の手順を行ったときに、くっつけなければならない棒の数を返すメソッドを作成せよ。もし、最後のステップで1つの棒しか必要がないようであれば1を返すようにすること。

私の解答はこちら。

public class Stick {

 public int pieces(int x) {
  int ret = 0;
  while( x > 0){
   ret += x % 2;
   x /= 2;
  }
  return ret;
 }

}

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

TopCoder SRM408 Div2 250Pts

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

思考チャレンジオリンピックの審判として雇われた。仕事は、一連の種目における競技者のパフォーマンスに基づいて合計点を計算することである。各種目で、競技者の生のスコアが与えられる。合計点は各種目に対して調整したスコアの和になる。各種目の調整スコアを計算するために、生のスコアを換算係数で割り、その値に最も近い整数に丸めるということを行う(小数点第一位で四捨五入する)。rawScores[]という一人の競技者の生のスコアと、conversionFactor[]という換算係数が与えられる。それぞれのi番目がi番目の種目のスコアと換算係数に対応している。競技者の合計点を返すメソッドを作成せよ。

私の解答はこちら。

public class TournamentJudging {

 public int getPoints(int[] rawScores, int[] conversionFactor) {
  int pts = 0;
  for( int i=0 ; i<rawScores.length ; i++ ){
   pts += Math.round(rawScores[i]*1.0 / conversionFactor[i]);
  }
  return pts;
 }

}

得点は248.13/250、1回のsubmitでシステムテストクリア。ひっかかるとすれば、割り算するときに実数に一旦変換するために1.0を掛けるのを忘れないことぐらいでしょうか。おそらく問題文を解読することの方が、コーディングよりも時間がかかっています。

TopCoder SRM407 Div2 250Pts

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

長方形のセルを左上から右上、右下、左下の方向へ順に、ぐるぐると渦を巻くように回る。全部のマスを回ったところで動きは止まる。既に通ったマス、あるいはセルの範囲を飛び出す場合は先に進めないので向きを時計回りに90度変える。進む向きを変えた位置にあるセルを除いて、通過したセルに書かれている数値の合計を計算して返すメソッドを作成せよ。最初と止まった位置も合計に加えることを忘れないこと。なお、セルは文字列型配列で管理されており、i番目の要素のj番目の文字がセル(i, j)とその位置に書かれている値を表している。

私の解答はこちら。

public class SpiralWalking {

 public int totalPoints(String[] levelMap) {
  int nrow = levelMap.length;
  int ncol = levelMap[0].length();
  boolean[][] isVisited = new boolean[nrow][ncol]; // 通過したセルを管理するフラグ
  int dir = 0; // 向いている方向(0～3)
  int[] xdir = {0, 1, 0, -1}; // 順に右、下、左、上方向に動く量を表している
  int[] ydir = {1, 0, -1, 0}; // 上に同じ。なお、xdirは行方向、ydirは列方向の移動量である。
  int total = 0; // 返す値の合計を管理
  int xpos = 0; // 現在の位置(行方向)
  int ypos = 0; // 現在の位置(列方向)
  boolean turned = false; // 向きを変えたか否かを管理するフラグ
  while( true ){
   int val = levelMap[xpos].charAt(ypos) - '0'; // 値を計算して
   total += val; // 追加
   isVisited[xpos][ypos] = true; // 訪問済に変更
   int currentdir = dir; // 現在の向きを記憶
   turned = false; // 向きを変えていない
   // もし、その向きで進んだらセルを飛び出す、あるいは訪問済みのセルに進むのであれば、
   // 向きを90度変える
   while( xpos+xdir[dir] >= nrow || xpos+xdir[dir] < 0 ||
    ypos+ydir[dir] >= ncol || ypos+ydir[dir] < 0 ||
    isVisited[xpos+xdir[dir]][ypos+ydir[dir]] ){
    dir = (dir+1) % xdir.length;
    turned = true;
    if( dir == currentdir ) return total; // 結局向きが1周したら、訪問するセルは残っていない
   }
   if( turned ) total -= val; // 向きを変えていたなら、値の加算はなかったことにする
   xpos += xdir[dir]; // 次のセルの位置へ進む
   ypos += ydir[dir];
  }
 }

}

得点は117.42/250、1回のsubmitでシステムテストクリア。中央値は75点。規則性があるので、上手く書けば実はループが不要にできるのではないかと思うのですが...

TopCoder SRM406 Div2 250Pts

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

grid[]という文字列型配列による長方形型のセルについて考える。"X"という文字が入ったセルは埋まっていることを示し、"."という文字はそのセルが空いていることを示している。二つのセルが同じ辺を共有しているとき、二つのセルは直交に隣合っている(orthogonal neighbors)といい、互いに斜めの位置にある場合、二つのセルは対角に隣り合っている(adjacent neighbors)という。もし、あるセルが空白で、かつ直交に隣り合うセルと斜めに隣り合うセルがすべて埋まっているのであれば、そのセルを1-happyということにする。あるセルが空白で、直交に隣り合うセルがすべて埋まっていて、斜めに隣あうセルが1つ以上空白であるとき、そのセルを2-happyという。あるセルが空白で、斜めに隣り合うセルがすべて埋まっているが、1つ以上直交に隣り合うセルに空白があるとき、そのセルは3-happyという。1-happyに該当するセル、2-happyに該当するセル、3-happyに該当するセルの数を求め、それらの3つの要素からなる整数型の配列を返すメソッドを作成せよ。

私の解答はこちら。

public class HappyCells {

 public int[] getHappy(String[] grid) {
  int[] happy = new int[3];
  int nrow = grid.length;
  int ncol = grid[0].length();
  // 自身を含む周囲9マスの相対的な位置、xは上下方向、yは左右方向
  // 添え字は左上から右下に向かって大きくなる。注目しているセルは5番目になる
  int[] x = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
  int[] y = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
  for( int i=0 ; i<nrow ; i++ ){
   for( int j=0 ; j<ncol ; j++ ){
    int diag = 0; // 直交に隣り合うセルの.の数
    int orth = 0; // 斜めに隣り合うセルの.の数
    if( grid[i].charAt(j) != '.') continue; // .のセル以外は考えなくて良い
    for( int k=0 ; k<x.length ; k++ ){
     if( k == 4 ) continue; // 5番目のセル(つまり周囲を注目すべきセル)は考慮しない
     int xpos = i+x[k];
     int ypos = j+y[k];
     // 長方形の範囲を超える箇所では考える必要はない
     if( xpos < 0 || xpos >= nrow || ypos < 0 || ypos >= ncol ) continue;
     if( grid[xpos].charAt(ypos) == '.' && k % 2 == 0 ){
      diag++;
     }else if( grid[xpos].charAt(ypos) == '.' && k % 2 == 1 ){
      orth++;
     }
    }
    // 得られた周囲の.の数から、加算すべき配列の添字を決める
    if( diag == 0 && orth == 0 ){
     happy[0]++;
    }else if( diag > 0 && orth == 0 ){
     happy[1]++;
    }else if( diag == 0 && orth > 0 ){
     happy[2]++;
    }
   }
  }
  return happy;
 }

}

196.97/250、1回のsubmitでシステムテストクリア。変数の書き換えなどしていたので、1点ぐらいは下げたのではなかろうか...

TopCoder SRM405 Div2 250Pts

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

下降階乗をnからk個取るとき、その値はn*(n-1)*...*(n-k+1)と定義される。これをn^^kと表記することにする。例えば7^^3=7*6*5=210であるし、n^^1=nである。次にこの定義を非正の整数kに対して拡張する。そのために(n-k)*(n^^k)=n^^(k+1)という事実を用いる。つまり、n^^k=(n^^(k+1))/(n-k)となる。これにより、以下のことが分かる。

• n^^0=n^^1/(n-0)=1
• n^^(-1)=n^^0/(n+1)=1/(n+1)
• n^^(-2)=1/(n+1)/(n+2)
• より一般にはn^^(-k)=1/(n+1)/(n+2)/.../(n+k)

例えば3^^(-1)=1/4=0.25などとなる。nとkが与えられたとき、下降階乗をnからk個を取ったときの値を返すメソッドを作成せよ。

私の解答はこちら。kの値で分岐して計算しています。

public class FallingFactorialPower {

 public double compute(int n, int k) {
  if( k==0 ){
   return 1.0;
  }else if( k>0 ){
   double ret = 1.0;
   for( int i=0 ; i<k ; i++ ){
    ret *= (n-i);
   }
   return ret;
  }else{
   double ret = 1.0;
   for( int i=0 ; i<Math.abs(k) ; i++ ){
    ret /= (n+i+1);
   }
   return ret;
  }
 }

}

得点は237.85/250、1回のsubmitでシステムテストクリア。中央値は約205点。

TopCoder SRM404 Div2 250Pts

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

introduction、story、edificationの3つのパートからなる本がある。ある人は本の元へ向かい、本の様々な部分を読んでいく。その人は、本を読み終える度に、リストに読み終えたパート名を付け加えていく。各本の0以上のパートを読む。どの順序で読むことができるが、各パートは1度しか読むことができないものとする。新しい本を読み始める度に、以前に見ていた本を読むことはできなくなる。readParts[]という読んだパートを示したリストが与えられたときに、3つのパートすべてを読んだ可能性がある本の数の最大値を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class ReadingBooks {

 public int countBooks(String[] readParts) {
  int[] times = new int[2];
  int nRead = 0;
  for( int i=0 ; i<readParts.length-2 ; ){
   // 以下の条件がtrueのとき、3パートは1つの本を構成しない
   if( readParts[i].equals(readParts[i+1]) ||
    readParts[i].equals(readParts[i+2]) ||
    readParts[i+1].equals(readParts[i+2]) ){
    i++;
   }else{
    nRead++;
    i += 3;
   }
  }
  return nRead;
 }

}

得点は103.62/250、2回目のsubmitでシステムテストクリア。中央値は約143点。誤訳して間違った実装をしていました、ハイ。

TopCoder SRM403 Div2 250Pts

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

ジョンは4と7はラッキーな桁であり、その他の桁はラッキーでないと考えている。ラッキーナンバーは10進数記法で書いたときにラッキーな桁のみからなる数値のことである。nという整数が与えられたとき、n以下で最大のラッキーナンバーを返すメソッドを作成せよ。なお、nは4以上の整数である。

私の解答はこちら。

public class TheLargestLuckyNumber {

 public int find(int n) {
  while( n > 0 ){
   String tmp = "" + n;
   boolean isLucky = true;
   for( int i=0 ; i<tmp.length() ; i++ ){
    if( tmp.charAt(i) != '4' && tmp.charAt(i) != '7' ){
     isLucky = false;
     break;
    }
   }
   if( isLucky ) return n;
   n--;
  }
  return 0;
 }

}

得点は247.97/250、1回のsubmitでシステムテストクリア。4と7以外を含むという判定を繰り返し数を10で割って余りで判別するといった手法もありそうですね。

2012年6月の学習記録

2012年6月に学習した主な本一覧。

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

X/Yの分布を求める問題など、確率変数変換の問題を理解するために解き始めた。統計ではありますが、解析の話がちょこちょこ出てきます。

マスタリングTCP/IP(pp.99～230)

TCPのヘッダの中身など、結構マニアックな話が増えてきたかな。情報セキュリティスペシャリスト試験を受けるのであれば、要らない箇所も多いだろうなと思いつつ、ネットワークスペシャリスト目指すなら必須だよなとも思って読んでいます。3分間ネットワーク基礎講座は一通り読了。

編入数学徹底演習(109問、9～14章)

確率・統計、線形代数の高専生の編入試験のための問題群。やり直しにはこのぐらいでもよい。

テキストデータの統計科学入門(pp.1～12)

テキストマイニングや自然言語処理を今年の学習テーマにしているので、早めに読んでしまいたい。

統計解析入門（pp.114～130)

クラメル・ラオの不等式の辺りが山場。理解のためにもうちょっと演習をやっておきたい。入門・演習 数理統計と章末問題で補強する予定。

入門自然言語処理(pp.41～62)

NLTKに付属するコーパスの呼び出し方などの学習。もう少しペースを上げて読みたい。

初めてのコンピュータサイエンス(pp.245～読了)

初めてのGUI作成、および初めてのデータベース操作をしました。Pythonの強力さというのが分かる1冊。

初めてのPython(第6～12章)

Python2冊目はこれ。初めてのコンピュータサイエンスのおかげで軽く読めている。後半のオブジェクト指向などが山場になりそう。

その他の勉強はPythonの無料講座(講師として約4時間の指導)、NHKラジオの実践ビジネス英語、TopCoder過去問演習など。