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

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

2013年8月の学習記録

外出が多すぎて大したことができておりませぬ...

サンプルサイズの決め方(pp.16～60)

相変わらずのマニアック感。

オープンソース・ソフトウェアルータVyatta入門(pp.1～74)

ルータ、NAT変換、ファイアウォール、DNSやNTPのサーバを指定する設定など。機能を分割して複数のマシンでメールサーバを構築してました。

その他、TopCoderの易問をいくつか解くなど。

TopCoder SRM473 Div2 250Pts

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

頭の数をhead、脚の数をlegsとするとき、鶴亀算を行い、鶴の数と亀の数を表す要素2の整数型の配列を返せ。もし適切な解がない場合は要素数0の整数型の配列を返せ。

私の解答はこちら。

public class OnTheFarmDivTwo {

 public int[] animals(int heads, int legs) {
  if( 4*heads - legs < 0 || legs - 2*heads < 0 ){
   int[] x= new int[0];
   return x;
  }
  if( (4*heads - legs) % 2 != 0 || (legs - 2*heads) % 2 != 0 ){
   int[] x= new int[0];
   return x;
  }
  int[] x = {(4*heads - legs)/2, (legs - 2*heads)/2};
  return x;
 }

}

得点は233.91/250、1回のsubmitでシステムテストクリア。連立方程式を立てて解が非負の整数になるような条件を求める方針で解きました。日本語訳なので鶴亀算と紹介しましたが、英文では鶴を鶏と亀を牛で表現していました。そこは興味深いところかもしれません。

TopCoder SRM472 Div2 250Pts

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

タロウはカラフルなもの、特にカラフルなタイルが好きである。タロウの部屋は連続したL個のタイルで区切られている。各タイルは以下の4つの色の1つである：赤、緑、青、黄。roomという文字列が与えられ、各部屋のi番目の文字はR、G、BまたはYで現され、それぞれ赤、緑、青、黄を表している。タロウは隣り合う部屋の色が同じにならないように部屋の色を変えることにした。変えなければならないタイルの数の最小値を返せ。

私の解答はこちら。

public class ColorfulTilesEasy {

 public int theMin(String room) {
  int nChange = 0;
  char[] roomchars = room.toCharArray();
  char prevColor = 'X';
  for( int i=0 ; i<room.length() ; i++ ){
   char curColor = room.charAt(i);
   if( curColor == prevColor ){
    nChange++;
    roomchars[i] = 'X';
   }
   prevColor = roomchars[i];
  }
  return nChange;
 }

}

得点は243.22/250、1回のsubmitでシステムテストクリア。1文字ごとに分解してしまえばしめたものです。