TopCoder SRM478 Div2 250Pts

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

タロウはおいしいキウイフルーツのジュースを用意した。彼はそれを0からN-1までの数字がつけられたN個のボトルに注いだ。i番目のボトルの容量はcapacities[i]リットルであり、bottees[i]リットルをそのボトルに注いでいる。そして、彼はボトルのジュースを再分配したいと思っている。このために0からM-1まで番号を付けられた操作を行う。i番目の捜査ではfromId[i]からtoId[i]にジュースを注ぐ。注ぐのをやめるのはfromId[i]の中が空になるか、toId[i]の容量が満杯になるかのどちらか早い方である。すべての操作が終わった時のキウイジュースの量を表したN個の要素からなる整数型の配列を返せ。

public class KiwiJuiceEasy {

 public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId) {
  for( int i=0 ; i<fromId.length ; i++ ){
   int from = bottles[fromId[i]]; // 注げる量
   int to = bottles[toId[i]];
   int toLeft = capacities[toId[i]] - to; // 注げる量
   int pourAmount = Math.min(from, toLeft); // 小さい方を調べて
   bottles[fromId[i]] -= pourAmount; // 移し替える操作
   bottles[toId[i]] += pourAmount;
  }
  return bottles;
 }

}

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

TopCoder SRM477 Div2 250Pts

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

N日(1～Nという日とする)のうちK日(1<=K<=N)連続した休みがとりたいのだが、workingDaysにある日については会議がある（配列の要素は1以上N以下の整数で与えられる）。このとき会議がある日を最小でいくつずらせば、K日の連続した休みを取ることができるか。

import java.util.Arrays;

public class VacationTime {

 public int bestSchedule(int N, int K, int[] workingDays) {
  Arrays.sort(workingDays);
  int mindays = workingDays.length + 1;
  for( int i=1 ; i<=N-K+1 ; i++ ){
   int ndays = 0;
   for( int j=i ; j<i+K ; j++ ){
    for( int k=0 ; k<workingDays.length ; k++ ){
     if( workingDays[k] == j ) ndays++;
    }
   }
   if( ndays < mindays ) mindays = ndays;
  }
  return mindays;
 }

}

得点は190.81/250、1回のsubmitでシステムテストクリア。本文はもうちょっと前フリがあるのですが、面倒なので省略。

TopCoder SRM476 Div2 300Pts

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

N×Mの数字で埋められた行列がある。行列の要素は0～9である。この行列に対し、4つの操作が定義されている。それらは1行上にシフト(1番上の行は1番下に移動)、1行下にシフト(1番下の行は1番上に移動)、1列左にシフト（1番左の行は1番右に移動）、1列右にシフト(1番右の行は1番左に移動)というものである。1行しかなければ、1行上、下にシフトする操作は意味をもたないし、同様に、1列しかなければ1列左、右にシフトする操作は何も効果がないことに注意。matrix[]という、i番目の文字列のj番目の要素が行列の(i, j)要素を表す文字列型配列が与えられたとき、valueという値が一番左上に移動するのに必要な操作の回数の最小値を返せ。なお、valueに該当する値はmatrix中に複数存在することがある。左上に動かすべき要素がないときには-1を返せ。

public class MatrixShiftings {

 public int minimumShifts(String[] matrix, int value) {
  int nRow = matrix.length;
  int nCol = matrix[0].length();
  int minMove = nRow + nCol; // 最小移動回数のカウント
  int[][] array = new int[nRow][nCol]; // とりあえず数値として扱うことにする

  for( int i=0 ; i<nRow ; i++ ){
   char[] line = matrix[i].toCharArray();
   for( int j=0 ; j<nCol ; j++ ){
    array[i][j] = line[j] - '0';
   }
  }

  if( isExist(array, value) == false ) return -1; // 1個も検討すべき値がなければ-1で終了
  for( int i=0 ; i<nRow; i++ ){
   for( int j=0 ; j<nCol ; j++ ){
    if( array[i][j] == value ){
     int moveRow = Math.min(i, nRow-i); // 行方向に動かすべき最小回数
     int moveCol = Math.min(j, nCol-j); // 列方向に動かすべき最小回数
     minMove = Math.min(minMove, moveRow+moveCol); // valueが左上のセルに移動するまでの最小の移動回数を更新
    }
   }
  }

  return minMove;
 }

 private boolean isExist(int[][] a, int value){
  for( int i=0; i<a.length; i++ ){
   for( int j=0; j<a[0].length; j++ ){
    if( a[i][j] == value ) return true;
   }
  }
  return false;
 }
}

得点は254.13/300、1回のsubmitでシステムテストクリア。位置だけで左上のセルへの最小移動回数は決まるので、valueに合致するすべてのセルについてその回数を計算するだけ。コードは長いが、250点でも良さげ。

TopCoder SRM475 Div2 250Pts

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

ウサギたちはしばしばさびしさを感じるので、あるグループがまとまり、どれが一番美しい耳かを競うビューティーコンテストを開催した。1匹が1票を持つ。もし自身に投票した場合は無効となる。もっとも票数が多かったのが勝者となる。namesがウサギの名前、votesが投票先、それぞれのi番目の要素について取り出すと、ウサギnames[i]がvotes[i]に投票したということを意味する。勝者を文字列で返せ。もし複数の勝者がいるのであれば、空文字を返せ。

私の解答はこちら。

import java.util.HashMap;

public class RabbitVoting {

 public String getWinner(String[] names, String[] votes) {
  HashMap<String, Integer> hm = new HashMap<String, Integer>();
  for( int i=0 ; i<names.length ; i++ ){
   if( names[i].equals(votes[i]) ) continue; // 自分に投票したら票として扱わない
   if( hm.containsKey(votes[i]) ){ // 票としてカウント
    hm.put(votes[i], hm.get(votes[i])+1 );
   }else{
    hm.put(votes[i], 1);
   }
  }
  int maxvotes = -1;
  String winner = "";
  for( String key: hm.keySet() ){ // こういうループもある
   if( maxvotes < hm.get(key) ){ // 最多得票数を更新した場合
    winner = key;
    maxvotes = hm.get(key);
   }else if( maxvotes == hm.get(key) ){ // 最多得票数が複数でた場合
    winner = "";
   }
  }
  return winner;
 }

}

得点は189.29/250、2回目のsubmitでシステムテストクリア。最初にputするときに0で初期化して間違えるというオチ(1で初期化する必要がある)。

TopCoder SRM474 Div2 250Pts

今回解いた問題は、文字列Aの途中(Aの先頭と最後尾も含む)のすべての位置に文字列Bを挟んだとき、できた文字列が回文になっている数を返すメソッドを作成せよという問題。

私の解答はこちら。

public class PalindromesCount {

 public int count(String A, String B) {
  int n = 0;
  for( int i=0 ; i<=A.length() ; i++ ){ // 最後尾に付け足すので、A.lengthまで調べる必要がある
   String cur = A.substring(0, i) + B + A.substring(i); // Aの途中にBを挟んだ文字列を生成
   if( isPalindrome(cur) ) n++;
  }
  return n;
 }

 private boolean isPalindrome(String s){ // 文字列をひっくり返して一致しているか調べる
  StringBuffer sb = new StringBuffer(s);
  String rev = sb.reverse().toString();
  return s.equals(rev);
 }
}

得点は240.30/250、1回のsubmitでシステムテストクリア。割ときれいにかけました。

2013年9月の学習記録

とある弁当屋の統計技師(pp.1～読了)

初心者向けには良いと思う。高校1年生向けかと言われると後半はちょっと怪しい気がしないでもない。

サンプルサイズの決め方(pp.61～70)

t検定で一定の検定力を持つために必要なサンプル数について学ぶ。うーん、ちょっと理論が飛躍している箇所があるぞ...

その他、データサイエンティスト完全ガイドを半分ほど読むなど。