TopCoder SRM413 Div2 250Pts

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

地下鉄の電車は人々をある駅から隣の駅へ高速に動かすことができる。二つの隣り合う駅について、lengthメートルであることが知られている。安全のため、電車はmaxVelocityメートル/秒よりも速く移動することは許されない。また、快適さのため、加速度の絶対値はmaxAccelerationメートル/秒^2を超えてはならないものとする。電車は0メートル/秒から動きだし、隣の駅で停車する(つまり駅に到着したときに0メートル/秒の速度になる)。隣の駅へ到着するのに必要な時間の最小値を返すようなメソッドを作成せよ。

私の解答はこちら。

public class Subway2 {

 public double minTime(int length, int maxAcceleration, int maxVelocity) {
  double toMax = maxVelocity * 1.0 / maxAcceleration;
  double s = maxVelocity * toMax;
  if( length < s ){
   double half = length / 2.0;
   return Math.sqrt(half * 2 / maxAcceleration)*2;
  }else{
   return toMax * 2 + (length - s) / maxVelocity;
  }
 }

}

209.07/250、1回のsubmitでシステムテストクリア。高校の物理学に出てくる運動の問題ですね。最高速に達する(コード中の分岐では後半)か、達しない(コード中の分岐では前半)かで場合分けすると簡単です。

2012年7月の学習記録

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

入門・演習 数理統計(pp.68～97、65問)

積率母関数や条件付き期待値の問題などを解く。

マスタリングTCP/IP(pp.231～338読了)

この本の範囲はエンジニアなら知っておいて損はないように思いました。とりあえず自分の周囲半径3メートル程度で発生したネットワークトラブルは自分の力で原因究明できるようになりたいものです。

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

テキストをうまく指標に落として検定等に持ち込む方法について学習中。個人的にはRでネットワークを作るパッケージの紹介が参考になりました。

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

信頼区間は区間が最小になるように選んでいると知ってナルホドと思いました。

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

もう少し深く読みたいです。個人的には演習問題の解答を一通り作ってしまいたい。

初めてのPython(第13～16、22～23章)

どちらかというとリファレンス的な本なので、実践的なテキストを読んだ方が楽しそう。

その他、実践ビジネス英語、入門ソーシャルデータなどを少々掻い摘む。

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でシステムテストクリア。