Codeforces 1A Theatre Square

本日解いたCodeforcesの問題の原文はこちらで確認することができる。問題を大まかに説明する。入出力サンプルは原文を参照してほしい。

Berlandの首都の劇場広場はnメートル*mメートルの長方形の形状をしている。街の記念日の機会に、広場に正方形の御影石でできた敷石を詰めるということが決まった。敷石はすべてaメートル*aメートルのサイズである。nメートル*mメートルの領域を埋めるのに必要な敷石は最低でいくつになるか?領域をカバーするに当たり、敷石を壊して埋めることは認められないし、敷石は領域の辺に平行になるように並べなければならないものとする。

私の解答はこちら。

#include <stdio.h>
#include <iostream>
using namespace std;

long long int nFlagstones(long long int s[], long long int a){
 int mMod = s[0] % a == 0 ? 0 : 1;
 int nMod = s[1] % a == 0 ? 0 : 1;
 return (s[0]/a+mMod)*(s[1]/a+nMod);
}

int main(void){
 long long int size[2];
 long long int alpha = 0;

 cin >> size[0] >> size[1] >> alpha;
 cout << nFlagstones(size, alpha);
 return 0;
}

C言語で%lldで入出力しようとしたら、それはダメとシステムに苦情を言われ、やむなくC++でコーディング。TopCoderと違って言語が広く選択できる反面、入出力のコードを書かないといけないので、大変面倒と思いました。問題のポイントはlong long intのサイズまで利用しないとダメになるということでしょうか。入出力の仕様上、最大で必要な枚数は10^18まで大きくなるので、その数字が扱えるよう大きめの型にする必要があります。その他、敷き詰める枚数は切り上げになるということのロジックに気を付けるぐらいでしょう。問題自体は簡単ですが、型に気を使わないといけないというのはTopcoderではあまりなく、斬新に思いました。

TopCoder SRM381 Div2 250Pts

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

あなたたちが知っているように、JOHNという名前ほどよいものはない。名前を比較するルールを定義しよう。アルファベットはAからZの順に1から26までの整数の重みがつけられている。名前の重みは名前全体の重みの総和である。2つの名前を比較するとき、重みが大きい方を良いものとする。もし重みが一致するのであれば、辞書で引いたときに先に来るものがよい。ただし、JOHNという名前はどんな名前よりもよいものとする。names[]という名前が入った文字列型配列が与えられたとき、その名前を良いものから悪いものになるように並べ替えたものを返すメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;
import java.util.HashMap;

public class TheBestName {

 public String[] sort(String[] names) {
  sortByName[] data = new sortByName[names.length];
  for( int i=0 ; i<names.length ; i++ ){
   data[i] = new sortByName(names[i]);
  }
  Arrays.sort(data);
  String[] ret= new String[names.length];
  for( int i=0 ; i<ret.length ; i++ ){
   ret[i] = data[i].name;
   System.out.println(ret[i]);
  }
  return ret;
 }

}

class sortByName implements Comparable<sortByName>{ // ソートのためのオブジェクト
 String name;
 int weight;
 public sortByName(String name) { // 名前と名前の重みで初期化
  int weight = 0;
  for( int j=0 ; j<name.length() ; j++ ){
   weight += name.charAt(j)-'A'+1;
  }
  this.weight = weight;
  if( name.equals("JOHN") ) this.weight = Integer.MAX_VALUE;
  this.name = name;
 }
  public int compareTo(sortByName o) { // 比較のルール
   if( weight - o.weight != 0 ) return o.weight-weight;
   return name.compareTo(o.name);
  }
}

得点は161.76/250、1回のsubmitでシステムテストクリア。SRM当日の正解率は約69%。weightを初期化する際に、+1を省略してはならないことに気付かずタイムロス。Aを0としてしまうと、AよりもAAが先に来る場合に、AAが先に来るようにできないので失敗してしまうというのが原因だった。

TopCoder SRM382 Div2 250Pts

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

整数型の配列が与えられたときに、要素数がK以上かつ、平均が最大になる連続した部分列を見つけ、(0-basedで)その位置を要素2の配列で返すメソッドを作成せよ。もし、そのようなものが複数ある場合は、長さが最大になるもの、それでも複数候補がある場合は、一番最初に登場した部分列の位置を返すようにせよ。

私の解答はこちら。

public class ContiguousSubsequences {

 public int[] findMaxAverage(int[] a, int K) {
  int[] ret = new int[2];
  double maxave = 0.0;
  int maxlen = 0;
  for( int i=0 ; i<a.length ; i++ ){
   for( int j=0 ; j<a.length ; j++ ){
    if( j-i+1 < K ) continue; // 要素数がKに満たない場合は考えない
    double ave = average(a, i, j);
    int len = j-i+1;
    if( ave > maxave ){ // 最大値が更新された場合
     maxave = ave;
     ret[0] = i;
     ret[1] = j;
     maxlen = len;
    }else if( ave == maxave ){ // 最大値に一致した場合
     if( len > maxlen ){ // 長さが以前のものより長い場合
      ret[0] = i;
      ret[1] = j;
      maxlen = len;
     }
    }
   }
  }
  return ret;
 }

 // 添字がfromからtoまでの要素の平均を計算する
 private double average(int[] a, int from, int to){
  double ret = 0.0;
  for( int i=from ; i<=to ; i++ ){
   ret += a[i];
  }
  return ret/(to-from+1);
 }

}

得点は214.46/250、1回のsubmitでシステムテストクリア。PracticeRoomの中央値は約135点、SRM当日の正解率は約65%。平均が同じときに最大長を更新するというロジックを入れずに悩むこと数分。

TopCoder SRM380 Div2 250Pts

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

lucky ticketという数字は桁数が2*n(nは自然数)で、前半のn桁と、後半のn桁の各桁の合計が一致する。sという数字のみからなる文字列が与えられたとき、lucky ticketになる部分文字列で最長になるものを求め、その長さを返すメソッドを作成せよ。

私の解答はこちら。

public class LuckyTicketSubstring {

 public int maxLength(String s) {
  int maxlen = 0;
  for( int from=0 ; from<s.length() ; from++ ){
   for( int to=from+1 ; to<s.length() ; to++ ){
    // 切り出す範囲の文字数が奇数なら考える必要なし
    // 添え字がfromからtoまでを切り出して考えることにする
    if( (to-from)%2 == 0 ) continue;
    int half = (to+from)/2;
    String first = s.substring(from, half+1);
    String second = s.substring(half+1, to+1);
    int sum1 = 0;
    int sum2 = 0;
    for( int i=0 ; i<first.length() ; i++ ){ // 前半と後半の数字の合計を計算
     sum1 += first.charAt(i) - '0';
     sum2 += second.charAt(i) - '0';
    }
    int len = first.length()*2;
    if( len > maxlen && sum1 == sum2 ){ // 合致の条件
     maxlen = to - from + 1;
    }
   }
  }
  return maxlen;
 }

}

得点は164.82/250、1回のsubmitでシステムテストクリア。当日の正解率は約85%。Stringの生成が多いので、最初にfrom-to+1がmaxlen以下ならcontinueするという条件を付けた方がいいのかなと思いました。

TopCoder SRM379 Div2 250Pts

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

複数のファイルをインターネットからダウンロードしようとしている。各ファイルのダウンロード状況について、"ダウンロード中の速度 ダウンロードにかかる時間"という形式で文字列型配列が与えられる。あるファイルのダウンロードが終わると、利用していた帯域は残りのファイルをダウンロードに割り当てられることができる。そのため、途中でダウンロード中の速度は上がり、ダウンロードにかかる時間は短くなる。さて、ある時点におけるダウンロード状況が与えられたとき、実際にかかる時間を計算して返すメソッドを作成せよ。

私の解答はこちら。

public class DownloadingFiles {

 public double actualTime(String[] tasks) {
  int speed = 0;
  int time = 0;
  int fileSize = 0;
  for( int i=0 ; i<tasks.length ; i++ ){
   String[] tmp = tasks[i].split(" ");
   speed += Integer.parseInt(tmp[0]);
   time += Integer.parseInt(tmp[1]);
   fileSize += Integer.parseInt(tmp[0]) * Integer.parseInt(tmp[1]);
  }
  return (double)fileSize/speed;
 }

}

得点は234.20/250、1回のsubmitでシステムテストクリア。初見で帯域をどうやって割り振っていいか理解できず、ぎょっとしたものの、そのようなことを考える必要はなく、ファイルサイズの合計/バンド幅(というか速度の合計)で求まるというオチ。

TopCoder SRM378 Div2 250Pts

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

小文字と空白のみからなる文字列messageを暗号化する。まずaからzまでの26文字の並びを先頭からfirstSize番目の文字で切って、二つのグループに分ける。次に対応表を作る。先頭のグループはfirstRoteteだけ後ろにずらし(最後方の文字は先頭に移動する)、後半のグループはsecondRoteteだけ後ろにずらす。messageはこのずらしたあとの対応表を基に暗号化する。例えばfirstSize=3、firstRotete=1、secondRotete=0、message="abcde"であれば、abcはbcaとずれることになるので、"abcde"は"bcade"となる(deはsecondRoteteが0なので文字の暗号化は行われない)。暗号化対象のmessage、アルファベット26文字をグループに分ける際に用いられるfirstSize、2つの文字のグループで文字を移動させるfirstRotete、secondRoteteが与えられたとき、messageを暗号化した結果を文字列で返せ。

私の解答はこちら。

public class TwoRotationCypher {

 public String encrypt(int firstSize, int firstRotate, int secondRotate, String message) {
  StringBuilder sb = new StringBuilder();
  for( int i=0 ; i<message.length() ; i++ ){
   char c = message.charAt(i);
   if( c == ' ' ){
    sb.append(' ');
    continue;
   }
   if( c-'a' < firstSize ){ // cがfirst groupに入る場合
    int pos = (c-'a'+firstRotate) % firstSize;
    sb.append((char)('a'+pos));
   }else{
    int pos = (c-'a'-firstSize-1+secondRotate) % (26-firstSize) + firstSize + 1;
    if( pos == 26 ) pos = firstSize;
    sb.append((char)('a'+pos));
   }
  }
  return sb.toString();
 }

}

得点は108.91/250、1回のsubmitでシステムテストクリア。境界値で嵌りました。pos==26という行が後付の箇所です。余りを利用して綺麗に書けないかなとは思うのですが...

TopCoder SRM377 Div2 250Pts

このTopCoderの問題はアーカイブには存在していない。問題文についてざっくりと説明する。

1より大きいNが「ほとんど素数」というのは次の条件を満たすものとする。1)Nは素数ではない。2)1とそれ自身以外で割り切れる数字がある。3)Nを素因数分解するとすべて10より大きいものとなる。さて、引数のmより大きな「ほとんど素数」になる数のうち、最小になるものを返せ。

私の解答はこちら。

public class AlmostPrimeNumbers {

 public int getNext(int m) {
  for( int i=m+1 ; i<Integer.MAX_VALUE ; i++ ){
   int half = i/2 + 1;
   for( int j=2 ; j<half ; j++ ){
    if( j < 10 && i%j==0 ) break; // 2～9で割り切れたら失敗、次へ行く
    if( i%j == 0 ) return i; // 初めて割り切れるのが10より大きな数であればOK
   }
  }
  return 0;
 }

}

得点は105.49/250。1回のsubmitでシステムテストクリア。途中でアリーナが不調に陥り提出に35分ほどロスト...

TopCoder SRM376 Div2 250Pts

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

文字列documentの連続する!を1つにまとめよ。ただし、!に?が1つ以上くっついている場合は!ではなく?1つにまとめよ。documentという入力の文字列をまとめた結果を返せ。例えば!!!は!になるし、!?abc!!!は?abc!となる。空白はそのまま扱う。

私の解答はこちら。

public class PunctuationCleaner {

 public String clearExcess(String document) {
  boolean isPunc = false;
  boolean containQuestion = false;
  StringBuilder sb = new StringBuilder();
  char c;
  for( int i=0 ; i<document.length() ; i++ ){
   c = document.charAt(i);
   if( c == '!' ){
    isPunc = true;
   }else if( c == '?' ){
    containQuestion = true;
   }else{ // !でも?でもない文字が来た場合
    if( containQuestion ){
     sb.append('?');
     containQuestion = false;
     isPunc = false;
    }else if( isPunc ){
     sb.append('!');
     isPunc = false;
    }
    sb.append(c);
   }
  }
  // 最後の文字が!だった場合などの処理
  if( containQuestion ) sb.append('?');
  else if( isPunc ) sb.append('!');
  return sb.toString();
 }

}

得点は146.37/250、2回目のsubmitでシステムテストクリア。正規表現使えるようになりたい...

TopCoder SRM375 Div2 250Pts

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

薬剤師が材料を混ぜ合わせた混合物を作成している。彼女は混合物の最終的な濃度を知る必要がある。濃度は混合物質の重さを体積で割ったものと定義される。文字列型のingredients[]という各要素が"体積 ml of 物質名, weighing 重量 g"という形式のものが与えられる。各要素は1つの物質についての表記である。それぞれ、体積はミリリットル、重量はgを単位にしている。ingredientsの要素に出てくる物質をすべて混ぜた物は1ミリリットルにつき、何グラムになるかを求めて返すメソッドを作成せよ。

私の解答はこちら。

public class MixtureDensity {

 public double getDensity(String[] ingredients) {
  int volume = 0;
  int mass = 0;
  for( int i=0 ; ilt;ingredients.length ; i++ ){
   String[] tmp = ingredients[i].split(" ");
   volume += Integer.parseInt(tmp[0]);
   mass += Integer.parseInt(tmp[tmp.length-2]);
  }
  return (double)mass/volume;
 }

}

得点は242.18/250、1回のsubmitでシステムテストクリア。当日の提出者の正解率は約88%。最初はtmp.length-2を5(スペース気切りで6番目に重量があると思っていた)としていたが、物質が2語以上のときに、文字列を整数にparseしようとするため、例外が発生するので修正した。

英単語学習記録20120416

英単語	意味
stunning	すばらしい
complimentary	無料の
venue	会場
transaction	事務処理
balance	残額
facility	設備
incur	～を負う
appliance	電化製品
due	支払うべき
shipping	送料
handling charge	手数料
dine	食事をする
with ease	容易に
adjacant to	～に隣接する
brochure	パンフレット

TopCoder SRM148 Div2 600Pts

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

キーボードのキー配列が入れ替えられ、ユーザは何をタイプしたか覚えようとしている。typedというスクリーン上に表示された文字列と、switches[]というキー配列の交換の様子が与えられたdecipherというメソッドを作成せよ。このメソッドは本来意図していたメッセージを返すものである。また、キー配列の交換は1度以上起きるものとする。例えば、もし誰かがAとSを交換し、SとDを交換したとすれば、Aがもともとあった場所にはDが、Dがもともとあった場所にはSが、Sがもともとあった場所にはAがあることになる。交換を表すswithches[]の各要素は"*:*という形式で表される。例えば先述の交換は{"A:S","S:D","D:A"}ということになる。なお、各要素の文字は順番が逆でも同じ結果になることに注意。

私の解答はこちら。

public class CeyKaps {

 public String decipher(String typed, String[] switches) {
  char[] keys = new char[26]; // 26文字のキーボードを表す配列と思っておく
  for( int i=0 ; i<keys.length ; i++ ){ // 値の初期設定
   keys[i] = (char)('A' + i);
  }
  // キーボードのボタンを交換していく
  for( int i=0 ; i<switches.length ; i++ ){
   char c1 = switches[i].charAt(0);
   char c2 = switches[i].charAt(2);
   int pos1 = searchFromKeys(keys, c1);
   int pos2 = searchFromKeys(keys, c2);
   swap(keys, pos1, pos2);
  }
  // typedの内容が実際に何になるかはkeysでわかる
  StringBuilder sb = new StringBuilder();
  for( int i=0 ; i<typed.length() ; i++ ){
   int pos = typed.charAt(i) - 'A';
   sb.append(keys[pos]);
  }
  return sb.toString();
 }
 // targetという文字のある位置を見つける。存在しないなら-1。
 private int searchFromKeys(char[] keys, char target){
  for( int i=0 ; i<keys.length ; i++ ){
   if( target == keys[i] ) return i;
  }
  return -1;
 }
 // keysのp1とp2の要素を入れ替える
 private void swap(char[] keys, int p1, int p2){
  char tmp = keys[p1];
  keys[p1] = keys[p2];
  keys[p2] = tmp;
 }
}

得点は449.94/600、1回のsubmitでシステムテストクリア。提出者の正解率は約89%。テストのコードの良さで正解率が決まってしまっているような気がします。

英単語学習記録20120413

TOEIC対策ということで、後で復習できるよう英単語を記録していく。TOEICの点数は約700点強なので、同じぐらいのスコアの人には参考になるかもしれない。

英単語	意味
supervise	監督する(教師あり学習はsupervised learning)
fabric	布地
appreciate	感謝する
attire	衣装
demanding	きつい
seal the deal	契約を結ぶ
branch	支店、枝
controversial	問題のある
concur	同時に起きる、一致する
procrastinate	先延ばしにする
reach a verdict	判決を出す
receipt	領収書
crave for ～	～を渇望する
handyman	便利屋
just about anything	ほとんど何でも
entrepreneur	起業家、アントレプレナー
diverse	多様性がある
resign	退職する
enact	制定する
icon	偶像
headquaters	本社
legislation	法律、立法
proliferate	急増する
vacantly	ぼんやり
hand in ～	～を提出する

TopCoder SRM439 Div2 250Pts

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

dataという長方形グリッドの各セルに1桁の数字が入った文字列型配列が与えられる。4つの角にあるセルが同じ数字になる最大の正方形の中に含まれるセルの数を返すメソッドを作成せよ。なお、正方形の辺は常にグリッドに平行である(要は回転して正方形になるというケースは考慮しなくてもよい)。なお、1セルも正方形とみなすので、解答は常に存在する。

私の解答はこちら。

public class SquareOfDigits {

 public int getMax(String[] data) {
  int nRow = data.length;
  int nCol = data[0].length();
  int maxS = -1;
  int maxSide = Math.min(nRow, nCol);
  for( int n=0 ; n<maxSide ; n++ ){ // 探索する正方形の辺のサイズをnとしている
   for( int i=0 ; i<nRow-n ; i++ ){
    for( int j=0 ; j<nCol-n ; j++ ){
     // 正方形の存在条件
     if( data[i].charAt(j) == data[i].charAt(j+n) &&
      data[i+n].charAt(j) == data[i+n].charAt(j+n) &&
      data[i].charAt(j) == data[i+n].charAt(j) ){
      maxS = Math.max(maxS, (n+1)*(n+1));
     }
    }
   }
  }
  return maxS;
 }

}

得点は214.96/250、1回のsubmitでシステムテストクリア。SRM当日の正解率約66%。答えは常にn*nの形で与えられる。そのサイズにマッチするものを探索すればよいということに気付いてからは解答が速かったです。この問題はSRM前に開ける問題ということでウォーミングアップを兼ねて解きました。

TopCoder SRM374 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。画像があるので、問題の原文も確認していただきたい。それでは、問題文について説明する。

先週、国際アイスホッケー連盟からあるチームのプレーヤーがリンクに入りすぎた場合に警告を出すシステムを要望する至急の電話が入った。システムは次の3つの部分からなる。

• デジタルカメラが毎秒リンクを撮影する。
  
• カメラで撮影された各プレーヤの位置を抽出する
  
• ホッケーリンク内にいる同一チームに属する人数を数える。
  

リンクは真上から見ると、長方形の両端に半円をつけた形状をしている。長方形は幅width、高さheightであり、半円の半径はheight/2で与えられる。また、長方形の左下の座標が(x,y)である。そして、プレーヤの位置がpx[]、py[]という配列で与えられ、プレーヤiの位置は(px[i],py[i])である。

あなたはプロジェクトリーダーから、"リンクの形状とプレーヤーの位置が与えられたときに、リンクの境界とその内部にいるプレーヤーの数を返せ"という、3番目の昨日の実装を割り当てられた。そのようなメソッドを作成せよ。

私の解答はこちら。

public class HockeyFault {

 public int numPlayers(int width, int height, int x, int y, int[] px, int[] py) {
  int nPlayers = 0;
  for( int i=0 ; i<px.length ; i++ ){
   if( px[i] >= x && px[i]<=x+width &&
       py[i]>=y && py[i]<=y+height){
    nPlayers++; // 長方形内部
   }else if( Math.pow(px[i]-x, 2)+Math.pow(py[i]-(y+height/2.0), 2)
             <= Math.pow(height/2.0,2) ){
    nPlayers++; // 長方形の左側の半円内部
   }else if( Math.pow(px[i]-(x+width), 2)+Math.pow(py[i]-(y+height/2.0), 2)
             <= Math.pow(height/2.0,2) ){
    nPlayers++; // 長方形右側の半円内部
   }
  }
  return nPlayers;
 }

}

得点は233.28/250。1回のsubmitでシステムテストクリア。当日の正解率は約87%。素直なので、特にコメントは無い。

TopCoder SRM373 Div2 250Pts

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

X、Y、Pという3つの正の整数が与えられる。a、bを正の整数としてa*X+b*YがPで割り切れるとき、a+bを最小にするaとbの組合せを求め、その値を求めよ。

私の解答はこちら。

public class TheEquation {

 public int leastSum(int X, int Y, int P) {
  int min = Integer.MAX_VALUE;
  for( int i=1 ; i<=2*P ; i++ ){
   for( int j=1 ; j<=2*P ; j++ ){
    if( (i*X+j*Y) % P == 0 ){
     min = Math.min(min, i+j);
    }
   }
  }
  return min;
 }

}

得点は243.63/250、1回のsubmitでシステムテストクリア。当日の正解率は約82%。ヒントにより探索範囲が分かるので、簡単でした。解答が2*P以下になるということ(P*X+P*YがPで割り切れるから)なので、全探索でゴリ押し。

TopCoder SRM147 Div2 600Pts

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

numMales人の男性と、numFemales人の女性が輪をなしている。ある地点から時計回りにカウントし、K番目の人を輪から取り除く（最初の人は1番目、時計回りに次の人を2人目と数える）。取り除いたのちに、次の人を1番目の人として輪から取り除く人を決める。これをnumFemales回繰り返すと、輪から女性がいなくなる。そのようなときに、女性を取り除く前はどのような状態であったかを表す文字列を返すメソッドを作成せよ。先頭は1番最初にカウントされた人の性別に対応し、文字列の並びはそこから時計回りに並んだ人の性別の順になる。例えば、5人の男性と3人の女性がいて、2人ごとに取り除くとした場合、返される文字列は"MFMFMFMM"となる。

私の解答はこちら。

public class PeopleCircle {

 public String order(int numMales, int numFemales, int K) {
  int numPeople = numMales+numFemales;
  char[] gender = new char[numPeople]; // 並びを表す配列
  int pos = 0; // 配列の中で注目している位置
  // 抜けた位置(つまり女性の位置)にtrueが入る配列
  boolean[] isRemoved = new boolean[numPeople];
  for( int i=0 ; i<numFemales ; i++ ){ // 女性の位置を探索
   int n = 0; // 途中の抜けを考慮してカウントした人数
   while( true ){
    if( isRemoved[pos] == false ){ // 抜けていなければカウント
     n++;
    }
    if( n >= K ){ // K人カウントしたところでFの位置が決まる
     break;
    }
    pos = pos >= numPeople-1 ? 0 : pos+1; // 配列の終端に来たら先頭へ
   }
   gender[pos] = 'F';
   isRemoved[pos] = true;
  }
  for( int i=0 ; i<numPeople ; i++ ){ // 上のループでFと確定できない要素はMになる
   gender[i] = gender[i] == 'F' ? 'F' : 'M';
  }
  return String.valueOf(gender);
 }

}

数か月放置したのち、約25分で回答。得点は180.00/600。当時の提出者正解率は50%。案外考えれば解けますね。

TopCoder SRM372 Div2 250Pts

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

医者があなたに、食べるべきものを文字列(1つの食べ物が1文字になっている)で表した食事療法を与えた。あなたは自分が朝食と昼食で食べたものを知っており、それらも文字列(やはりこれも1つの食べ物が1文字)で表されている。夕食はたべてよい残りの物をすべて食べることを決めたので、それを文字列として返すようなメソッドを作成してほしい(文字はアルファベット順にソートせよ)。もし、食事計画にないものや、あるものを指定された量以上食べた場合は"CHEATER"という文字列を返すようにせよ。

例えばdiet="ABCD"でbreakfast="A"、lunch="BC"であれば、夕食には"D"が食べられるので"D"を返すことになる。

私の解答はこちら。

import java.util.Arrays;

public class DietPlan {

 public String chooseDinner(String diet, String breakfast, String lunch) {
  String eat = breakfast + lunch;
  StringBuilder sb = new StringBuilder(diet); // 文字列の除去のためStringBuilderを利用
  for( int i=0 ; i<eat.length() ; i++ ){
   int idx = sb.toString().indexOf(eat.charAt(i)); // たべたものを探す
   if( idx < 0 ) return "CHEATER"; // たべたものがdiet中になかったら...
   sb = sb.delete(idx, idx+1); // たべてよいものがあったので、食べたということで取り除く
  }
  char[] tmp = sb.toString().toCharArray(); // ソートのために1文字ごとに分解
  Arrays.sort(tmp);
  return String.valueOf(tmp);
 }

}

得点は210.37/250、中央値は約214点。1回のsubmitでシステムテストクリア。文字列を順に取り除くということを実装しようとしたばかりに操作が増えてしまってますね。

TopCoder SRM371 Div2 250Pts

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

選挙における試みの1つに、候補者を順位づけするということがある。候補者Aが候補者Bより「好ましい候補者」であるというのは、AがBより高い順位をつけた人が、その逆より多いということを指す。コンドルセ勝者というのは、他のすべての候補者よりも「好ましい候補者」である候補者のことを言う。コンドルセ勝者は選挙においては最大で一人いるが、0人になることもある。

問題ではvotes[]というi番目の要素のj番目の文字がiさんが候補者jに対して評価した結果が小文字のアルファベットで格納されている。"a"に近いほど好評価で、"z"に近いほど低評価になる。コンドルセ勝者を表す数字を、先頭を0とするインデックスで返せ。もし、コンドルセ勝者が存在しない倍は-1を返すようにせよ。

私の解答はこちら。

public class CondorcetVoting {

 public int winner(String[] votes) {
  int nCandidates = votes[0].length();
  // iがjに勝ち越せば正、負け越せば負の値がi行j列に入る。j行i列はその-1倍の値になる。
  int[][] win = new int[nCandidates][nCandidates];
  for( int i=0 ; i<votes.length ; i++ ){
   for( int j=0 ; j<nCandidates ; j++ ){
    for( int k=j+1 ; k<nCandidates ; k++ ){
     if( votes[i].charAt(j) < votes[i].charAt(k) ){
      win[j][k]++;
      win[k][j]--;
     }else if( votes[i].charAt(j) > votes[i].charAt(k) ){
      win[j][k]--;
      win[k][j]++;
     }
    }
   }
  }

  // コンドルセ勝者の探索
  for( int i=0 ; i<nCandidates ; i++ ){
   boolean isCondorcetWinnerExist = true;
   for( int j=0 ; j<nCandidates ; j++ ){
    if( i==j ) continue; // 対角成分はiさんがiさんに勝ったか?を評価するので無視
    if( win[i][j] <= 0){ // コンドルセ勝者は対角成分以外が全部正の値である
     isCondorcetWinnerExist = false; // ここに入ったら失敗
     break;
    }
   }
   if( isCondorcetWinnerExist ) return i;
  }
  return -1;
 }

}

得点は132.43/250、1回のsubmitでシステムテストクリア。2次元配列で勝ち負けを格納するという方法を思いつくのに時間がかかりました。また、最初に人を固定して候補者を比較するという順序が大事なようです。

TopCoder SRM370 Div2 250Pts

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

いくつかのコンテナが1列に並んでおり、パッケージをそれらに入れたいと思っている。最初のコンテナに最初のパッケージを入れることから始める。すべてのパッケージがコンテナに入るまで、以下のことを行う。

1. もしパッケージがコンテナに収まらないなら、ステップ3へ行く、そうでなければ次のステップへ行く。
   
2. パッケージをコンテナにつめる。次のパッケージを手に取り、ステップ1へいく。
   
3. コンテナにこれ以上パッケージを詰められなければ現在のコンテナを追いやる。ラインから次のコンテナを取り、ステップ1へ戻る。
   

containers[]というi番目の要素がi番目のコンテナの容量を示した整数型の配列と、packages[]というi番目の要素がi番目のパッケージの大きさを意味する整数型の配列が与えられる。制約により、すべてのパッケージは上の手続きにより、コンテナに入れることが可能である。全コンテナの無駄な領域の合計を返せ。コンテナ中の無駄な領域とは、総容量から内容量の合計を引いたものになる。

私の解答はこちら。

public class Containers {

 public int wastedSpace(int[] containers, int[] packages) {
  int cPos = 0; // 注目するcontainer
  int pPos = 0; // 注目するpackage
  while( true ){
   int capacity = containers[cPos];
   int total = 0;
   boolean isFinish = false; // packageの終わりに辿りついたらtrueになる
   while( true ){
    if( pPos == packages.length ){
     isFinish = true;
     break;
    }
    if( total + packages[pPos] > capacity ){
     break;
    }else{
     total += packages[pPos++];
    }
   }
   if( isFinish ) break;
   cPos++;
  }
  int sumContainer = 0;
  for( int i=0 ; i<containers.length ; i++ ) sumContainer += containers[i];
  int sumPackage = 0;
  for( int i=0 ; i<packages.length ; i++ ) sumPackage += packages[i];
  return sumContainer - sumPackage;
 }

}

得点は187.11/250、中央値は約216点。1回のsubmitでシステムテストクリア。実はうすうす気づいていたが、単純にコンテナの合計-パッケージの合計でよいのである。制約には「必ず収まる」という条件がついているので、何番目に入れるとか考えなくてもよい。まさかと思いつつも、面倒な実装に走ってしまったのでした。

TopCoder SRM369 Div2 250Pts

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

長方形の集まりが描かれる面は最初は完全に真白である。各長方形は厳密に直前に描いた長方形の内部に収まる。長方形は赤、青、緑の3色のどれかで描かれる。色は混じることがないので、長方形を別の長方形の内部に描いたとき、新しい色がその位置にあった既存の色を置き換えることになる。長方形の集まりはwidth[]とheight[]という整数型の配列とcolorという文字列で表される。i番目に描かれる長方形のサイズはwidth[i]とheight[i]である。そしてその色はcolorのi番目の文字である。文字は"R"、"G"、"B"の3つであり、それぞれ赤、緑、青を表している。すべての長方形が描かれたとき、赤、緑、青が占める面積を計算し、3つの面積の中から最大になるものの値を返せ。

私の解答はこちら。

public class ChainOfRectangles {

 public int getMaximalArea(int[] width, int[] height, String color) {
  int r = 0; // 各色ごとに見えている面積を表す変数
  int g = 0;
  int b = 0;
  char prev = ' '; // 注目している長方形の直前の長方形の色を記録
  for( int i=0 ; i<color.length() ; i++ ){
   int iArea = width[i]*height[i]; // 注目する色の面積を増やす
   char col = color.charAt(i);
   if( col == 'R' ){
    r += iArea;
   }else if( col == 'G' ){
    g += iArea;
   }else{
    b += iArea;
   }
   switch(prev){ // 直前の色の面積を減らす
   case 'R':
    r -= iArea;
    break;
   case 'G':
    g -= iArea;
    break;
   case 'B':
    b -= iArea;
    break;
   default:
    break;
   }
   prev = col;
  }
  return Math.max(r, Math.max(g, b));
 }

}

得点は228.08/250、中央値は約197点。1回のsubmitでシステムテストクリア。実装要求の割にちょっと行数がおおいかな?

TopCoder SRM148 Div2 300Pts

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

numberという整数型の数字が与えられたとき、その数字の1桁の値で割り切れるものはいくつあるかを返すメソッドを作成せよ。なお0では割り切れない。例えばnumberが12345であれば、numberは1と3と5割り切れるので3を返すことになる。

私の解答はこちら。

public class DivisorDigits {

 public int howMany(int number) {
  int n = number;
  int ret = 0;
  while( n > 0 ){
   int mod = n % 10;
   n /= 10;
   if( mod == 0 ) continue;
   if( number % mod == 0 ) ret++;
  }
  return ret;
 }

}

得点は75.00。Javaを始めた頃に解いていた問題だったのだが、システムテストで確認していなかったので、バグを取り除いた上で再提出。

TopCoder SRM368 Div2 300Pts

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

偉大な海賊シルバは熱帯の島に宝を埋めた。あなたは島のある点にXがつけられた地図と指令を手に入れた。指令は"Bの方向にAだけ進め"と書かれている。もしX地点からその移動の指示に従ったなら、宝が埋められた場所に到着するであろう。ずるがしこい双子の兄弟が地図のコピーを持っており、既に指示に従って動き出している。兄弟に勝つために、宝の位置を見つけ、そこへまっすぐ向かわなければならない。問題ではsteps[]という整数型配列と、directions[]という文字列型配列が与えられる。各配列のi番目の要素が対応している。これによりdirections[i]の方向にstep[i]だけ進むということを表す。宝の位置を見つけ、最初の位置から宝の埋められた場所までの直線距離を実数型で返すメソッドを作成せよ。directions[]の中身は8つのコンパスに書かれた方向である。実際の問題文を参照して確認してほしい。

私の解答はこちら。

public class PirateTreasure {

 public double getDistance(int[] steps, String[] directions) {
  double vert = 0; // 南北方向の移動量、北へ進めば正、南へ進めば負の値になる
  double hori = 0; // 東西方向の移動量、東へ進めば正、西へ進めば負の値になる
  for( int i=0 ; i>directions.length ; i++ ){
   if( directions[i].equals("NORTH") ){
    vert += steps[i];
   }else if( directions[i].equals("NORTHEAST") ){
    vert += steps[i]/Math.sqrt(2);
    hori += steps[i]/Math.sqrt(2);
   }else if( directions[i].equals("EAST") ){
    hori += steps[i];
   }else if( directions[i].equals("SOUTHEAST") ){
    vert -= steps[i]/Math.sqrt(2);
    hori += steps[i]/Math.sqrt(2);
   }else if( directions[i].equals("SOUTH") ){
    vert -= steps[i];
   }else if( directions[i].equals("SOUTHWEST") ){
    vert -= steps[i]/Math.sqrt(2);
    hori -= steps[i]/Math.sqrt(2);
   }else if( directions[i].equals("WEST") ){
    hori -= steps[i];
   }else if( directions[i].equals("NORTHWEST") ){
    vert += steps[i]/Math.sqrt(2);
    hori -= steps[i]/Math.sqrt(2);
   }
  }
  return Math.sqrt(vert*vert + hori*hori);
 }

}

得点は278.03/300、1回のsubmitでシステムテストクリア。言われた通りにやってみただけですね。コード量を減らす工夫も難しいように思います。

TopCoder SRM367 Div2 250Pts

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

チェスの盤面は8*8のマスからなる。各行、列は黒と白が交互に並んでいる。左上の(0,0)の位置は白である。さて、問題ではboard[]という文字列型配列が与えられる。boardのi番目の要素のj番目の文字は"F"であれば占領されている(訳注：チェスの駒がマスの上にあるというイメージでしょうか)。"."であればマスの上になにもないということになる。白いマスで占領されているものの数を返せ。

私の解答はこちら。

public class WhiteCells {

 public int countOccupied(String[] board) {
  int nOccupied = 0;
  for( int i=0 ; i<board.length; i++ ){
   String row = retRow(i);
   for( int j=0 ; j<board[0].length() ; j++ ){
    // 白いマスの上が占領されている条件
    if( row.charAt(j) == 'W' && board[i].charAt(j) == 'F') nOccupied++;
   }
  }
  return nOccupied;
 }

 private String retRow(int r){ // 行によって要素の並びが違うWが白、Bが黒を表す
  return  r % 2 == 0 ? "WBWBWBWB" : "BWBWBWBW";
 }

}

得点は227.93/250、1回のsubmitでシステムテストクリア。実装よりも英語の問題文の理解に時間がかかっています。

TopCoder SRM366 Div2 250Pts

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

あなたはギターを大量に所持しており、ギターはそれぞれ異なったシリアルナンバーを持っている。シリアルナンバーを高速に検索できるようにしたいので、ソートすることにした。各シリアルナンバーはA-Z、0-9の文字のみからなる。シリアルナンバーAがシリアルナンバーBより前にくるか確認するのは次のステップを踏む。

• AとBが違う長さであれば、短い方が先に来る。
  
• AとBの文字列の長さが同じになる場合、AとBに現れる数字の各桁の総和が小さい方が先に来る。A-Zの数字は0扱い。
  
• それでもAとBに違いがでない場合はアルファベット順になるようにする。
  

serialNumbers[]という文字列型配列が与えられたとき、上のルールに従い文字列型配列を昇順に並び替えたものを返せ。

私の解答はこちら。

import java.util.Arrays;

public class SerialNumbers {

 public String[] sortSerials(String[] serialNumbers) {
  String[] ret = new String[serialNumbers.length];
  sortBySerial[] obj = new sortBySerial[serialNumbers.length];
  for( int i=0 ; ilt;obj.length ; i++ ){
   obj[i] = new sortBySerial(serialNumbers[i]); // ソートのためのオブジェクトに値をセット
  }
  Arrays.sort(obj); // これでオブジェクトがソートされたので、
  for( int i=0 ; ilt;ret.length ; i++ ){
   ret[i] = obj[i].str; // sortBySerialオブジェクトからStringのみを取得して、
  }
  return ret; // ソートした結果を返却する
 }

}

class sortBySerial implements Comparablelt;sortBySerialgt;{
 String str; // 文字そのもの
 int nStr; // 文字に現れる数字の合計
 public sortBySerial(String s){ // ソートのためのオブジェクトのコンストラクタ
  this.str = s;
  int n = 0;
  for( int i=0 ; ilt;s.length() ; i++ ){
   if( s.charAt(i) gt;= '0' && s.charAt(i) lt;= '9') n += s.charAt(i)-'0';
  }
  this.nStr = n;
 }
 public int compareTo(sortBySerial obj){ // ソートのルールを実装
  if( str.length() != obj.str.length() ){
   return str.length() - obj.str.length();
  }else if( nStr != obj.nStr ){
   return nStr - obj.nStr;
  }else{
   return str.compareTo(obj.str);
  }
 }
}

得点は204.29/250、1回のsubmitでシステムテストクリア。中央値は約97点と低め。ソートのルールが複雑なので、2重ループを1つのメソッドに書くより簡単だろうということで、Comparableを利用。過去に書いたComparableのコードを流用したので高速に解答できたはず。

TopCoder SRM365 Div2 250Pts

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

チェスの大会で、全員が一度ずつペアになって対戦する。試合の結果は3つの中のどれかになる。プレーヤ1の勝利、プレーヤ2の勝利、引き分けである。トーナメントのあいまいさを表す数字は3すくみの関係が成立する3人のペアの数になる。つまり、aはbに勝利し、bはcに勝利し、cはaに勝利するということである。table[]という試合結果が入った文字列型配列が渡される。table[i]のj番目の要素について、iがjに勝てば"1"、負ければ"0"、引き分けなら"-"が含まれることになる。与えられたトーナメントのあいまいさを表す数字を返せ。

私の解答はこちら。

public class TournamentsAmbiguityNumber {

 public int scrutinizeTable(String[] table) {
  int nAmbiguity = 0;
  int nMember = table[0].length();
  for( int i=0 ; i<nMember ; i++ ){
   for( int j=0 ; j<nMember ; j++ ){
    for( int k=0 ; k<nMember ; k++ ){
     if( i==j || j==k || k==i ) continue; // 3人の関係を見ていない場合
     char a = table[i].charAt(j);
     char b = table[j].charAt(k);
     char c = table[k].charAt(i);
     // よくよく考えてみると a == '1' && b == '1' && c == '1'
     // とすればよいだけだった。そうすればreturn文で2で割ることも不要になる。
     if( a == '-' || b == '-' || c == '-' ) continue;
     if( a == b && b == c ){
      nAmbiguity++;
     }
    }
   }
  }
  return nAmbiguity/2; // 全部0,0,0と1,1,1の場合がカウントされているので2で割る
 }

}

得点は227.60/250、1回のsumbitでシステムテストクリア。無駄にコードが増えてますな。

TopCoder SRM364 Div2 250Pts

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

マージは息子が時間をすごしている不良たちについてかなり心配している。アーケードですべての時間を過ごしていることは別として、彼らは暗号化されたメッセージで互いにコミュニケーションをとっている。心配している親として、マージは彼らが何について話しているのかということを知りたいと思っている。マージは彼らの暗号ライブラリをしっており、文字列型配列library[]にそれが与えられる。library[]の各要素は"アルファベットの大文字1文字 暗号化前の文字列"という形式をとっている(半角1文字で区切られている)。マージはmessageという暗号化されたメッセージからlibrary[]を用いて元の文章に戻そうとしている。ただし、マージはすべての単語に対応するライブラリを持っていないため、対応しない単語がmessageに現れてしまうことがある。その場合は"?"で単語を埋めることになる(マージは賢い母親なので、断片的な情報から単語が何か理解できるのである)。messageを復号化した結果を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.HashMap;
import java.util.Iterator;

public class MorselikeCode {

 public String decrypt(String[] library, String message) {
  String[] msgArray = message.split(" ");
  // 大文字と単語はハッシュで対応づけておく
  HashMap<String, String> hm = new HashMap<String, String>();
  for( int i=0 ; i<library.length ; i++ ){
   String[] tmp = library[i].split(" ");
   hm.put(tmp[1], tmp[0]); // 順番注意!
  }
  StringBuilder sb = new StringBuilder();
  for( int i=0 ; i<msgArray.length ; i++ ){
   Iterator<String> it = hm.keySet().iterator();
   boolean isExist = false; // library[]に対応する単語はあるか?
   while( it.hasNext() ){
    String tmp = it.next();
    if( tmp.equals(msgArray[i]) ){
     sb.append(hm.get(tmp));
     isExist = true;
     break;
    }
   }
   if( !isExist ) sb.append("?");
  }
  return sb.toString();
 }

}

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

TopCoder SRM363 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題についてごく簡単に説明する。テストケースには画像があるので、本文も参照されたい。

問題は自分の背中にあるアナログ時計(短針・長針のみからなる)を目の前にある鏡を通してみた時刻は実際には何時何分かを求めるメソッドをかけというもの。時計に数字は振られておらず、5分刻みの位置に点が打ってあるだけのものとなっている。例えば鏡を通して10時であれば、実際には2時である。

私の解答はこちら。

public class MirroredClock {

 public String whatTimeIsIt(String time) {
  String[] hhmm = time.split(":");
  int h = Integer.parseInt(hhmm[0]);
  int m = Integer.parseInt(hhmm[1]); // timeの形式から時間・分を計算
  if( m == 0 ){ // 分の値によって場合分けが発生する
   int trueHour = 12 - h ;
   return String.format("%02d:%02d", trueHour%12 , m);
  }else{
   int trueMinute = 60 - m;
   int trueHour = 11 - h;
   return String.format("%02d:%02d", trueHour%12 , trueMinute);
  }
 }

}

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

TopCoder SRM362 Div2 250Pts

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

1からNまで番号を時計回りにつけられたN人の友人が円状に座っている。ゲームははじめ、プレーヤ1がボールを受け取る。プレーヤーはボールを互いに渡しあう。渡し合う際には次の行動が行われる。もし、プレーヤーがM回ボールを受け取ったならゲームは終了である。そうでない場合、もしプレーヤーがp回受け取っていたなら、pが奇数であれば右、偶数であれば左へL人先の人にボールを渡す。N、M、Lが与えられたとき、ボールが受け渡された回数を返すメソッドを作成せよ。

私の解答はこちら。

public class ThrowTheBall {

 public int timesThrown(int N, int M, int L) {
  int[] nReceive = new int[N]; // 個人が受け取った回数を記録
  int nThrow = 0; // 全体でボールが投げられた回数を記録
  int pos = 0; // ボールの位置
  nReceive[0] = 1;
  while( true ){
   if( maxRecieve(nReceive) == M ) break; // 誰かがM回受け取ったら終了
   nThrow++;
   // 受け取った回数に応じて自分の左右のどちらに渡すか決める
   if( nReceive[pos] % 2 == 0 ){
    pos = ( pos + N - L ) % N;
   }else{
    pos = ( pos + L ) % N;
   }
   nReceive[pos]++;
  }
  return nThrow;
 }
 int maxRecieve(int[] array){ // 受け取った回数の最大値を求める
  int max = -1;
  for( int i=0 ; i<array.length ; i++ ){
   max = Math.max(max, array[i]);
  }
  return max;
 }

}

得点は190.25/250、中央値は約192点。1回のsubmitでシステムテストクリア。ちょっとした処理でも意味を持たせてみると見通しが良くなりますね。

TopCoder SRM361 Div2 250Pts

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

テキストエディタのテキスト検索を実装する必要がある。引数のtextは検索対象である。searchは検索したい単語である。wholeWordというのはオプションで"Y"であれば、単語全体がsearchに完全一致(前後は空白あるいは終端で区切られている)、"N"であれば単語の一部は一致でもOKということになる。startというのは、検索の開始位置(0から単語長-1)である。検索が一致した位置を返すメソッドを作成せよ。検索では大文字・小文字は違うものとして扱うことに注意せよ。位置はtextの先頭を0文字目として、初めて一致した箇所の先頭文字の位置を返すことになる。もし一致する位置がない場合は-1を返すようにせよ。

私の解答はこちら。

public class SearchBox {

 public int find(String text, String search, String wholeWord, int start) {
  if( wholeWord.equals("N") ){ // 単語の完全一致でない場合
   return text.indexOf(search, start);
  }

  int from = start;
  while( true ){
   int pos = text.indexOf(search, from); // 第2引数に探索開始位置
   if( pos == -1 ) return -1; // 見つからない場合
   // 見つかった場合
   // 直前の文字の位置
   int prev = pos == 0 ? -1 : pos-1;
   // 直後の文字の位置
   int next = pos+search.length() == text.length() ? -1 : pos+search.length();
   // 直前と直後の文字の内容が空白あるいは前後の端かを考慮して
   // 完全一致を判定
   if( ((prev >= 0 && text.charAt(prev) == ' ') || prev==-1 )
    && ((next >= 0 && text.charAt(next) == ' ') || next==-1 )) return pos;
   from = pos+1; // 単語が完全一致しなかったので、検索の位置を先に進める
  }
 }

}

得点は104.85/250、中央値は約102点。3回目のsubmitでシステムテストクリア。2回失敗して中央値より上なので難しめだったのでしょう。当日の正解率は約25%でした。

TopCoder SRM360 Div2 250Pts

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

ロボットが以下の命令に従って平面上を動いている。

命令	意味
LEFT	左に90度回転
RIGHT	右に90度回転
TURN AROUND	反対に向く(180度の回転と同じ)
LEFT X	左にX度回転(X>0である)
RIGHT X	右にX度回転(X>0である)
HALT	停止、以後の操作は受け付けない

instructions[]という上の命令が要素となった文字列が与えられる。最初にロボットは北を向いている。ロボットの最終的な方位角を返せ。方位角とは北とロボットが向いている方向のなす角度である。方位角は時計回りに計測し、その値は0から359で与えられる。例えば、西の方向の方位角は270である。

私の解答はこちら。

public class AzimuthMonitoring {

 public int getAzimuth(String[] instructions) {
  int angle = 0;
  for( int i=0 ; i<instructions.length ; i++ ){
   if( instructions[i].startsWith("LEFT ") ){
    int a = Integer.parseInt(instructions[i].substring(5));
    angle += (-a+360);
   }else if( instructions[i].startsWith("RIGHT ") ){
    int a = Integer.parseInt(instructions[i].substring(6));
    angle += a;
   }else if( instructions[i].startsWith("LEFT") ){
    angle += 270;
   }else if( instructions[i].startsWith("RIGHT") ){
    angle += 90;
   }else if( instructions[i].startsWith("TURN AROUND") ){
    angle += 180;
   }else if( instructions[i].startsWith("HALT") ){
    break;
   }
  }
  return angle%360;
 }

}

得点は230.88/250、中央値は約184点。1回のsubmitでシステムテストクリア。0から359までの値に収めるためにどのように処理を記述するかという点のみ考えさせられた。startWithメソッドを利用して命令を判別しているが、先に"LEFT X"でなく、"LEFT"を判別しようとすると失敗することには注意。

TopCoder SRM358 Div2 250Pts

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

循環する単語は円に書くことができる。循環する単語を表すため、任意の開始地点を選び、文字を時計回りに順に読む。つまり、"picture"と"turepic"は同じ循環する単語である。words[]という文字列配列が与えられたとき、その中に何種類の循環する単語が存在するかを返すメソッドを作成せよ。

私の解答はこちら。

import java.util.ArrayList;

public class CyclicWords {

 public int differentCW(String[] words) {
  ArrayList<String> al = new ArrayList<String>();
  for( int i=0 ; i<words.length ; i++ ){
   al.add(words[i]+words[i]);
  }
  boolean[] isUnique = new boolean[al.size()];
  for( int i=0 ; i<isUnique.length ; i++ ){
   isUnique[i] = true;
  }
  for( int i=1 ; i<al.size() ; i++ ){
   for( int j=0 ; j<i ; j++ ){
    String tar = al.get(j);
    int n = tar.indexOf(words[i]);
    // 単語が循環しているかを判定する方法
    // 後半の条件は例えば"aaa"と"aa"の区別のために必要になる
    if( n >= 0 && tar.length() == words[i].length()*2 ){
     isUnique[i] = false;
     break;
    }
   }
  }
  int nUnique = 0;
  for( int i=0 ; i<isUnique.length ; i++ ){
   if( isUnique[i] == true ) nUnique++;
  }
  return nUnique;
 }

}

得点は168.08/250、中央値は約187点。1回のsubmitでシステムテストクリア。2回繰り返した単語を考えることで循環するということを簡単にしている。これにより、ある単語について途中にindexOfで0以上の値があれば、繰り返しとみなすことができる。

2012年3月の学習記録

2012年3月に学習した主な本一覧。来月は思いっきり勉強しよう。

大学生の微積分(pp.168～197)

重積分に登場するヤコビアンの意味は調べなおしの必要がありそう。

TopCoder SRM357 Div2 250Pts

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

数学のテストにおいて、上手いニーモニックフレーズを持つことはしばしば役に立つ。例えば25735という数字は"is there anybody out there"と記憶することができる。もし、すべての単語の文字数を数えることができれば、25735という元の数字を得ることができる。不幸なことに、教授は学生にでたらめな数字を記憶させ、テストをするのを好んでいる。そのシステムを負かすため、あなたは覚えなければならない数字を表すニーモニックフレーズを見つける計画をしている。numberという数字を文字列とdictionary[]という文字列型の配列が与えられたとき、単語をスペース1文字で区切ったリストを返せ。ここで、各単語はdictionaryの要素であり、どの単語も1度しか利用しない。フレーズはnumberの桁数と同じである。i番目の単語の長さはi番目の数字に一致する。もし複数のフレーズが回答の候補にある場合(訳注：例えば同じ223のように同じ数字が複数回登場した場合を考えよ)は、アルファベット順で最初に来るものを返すようにせよ。

例えばnumber="1234"、dictionary[]={"This","is","a","pen"}であれば、"a is pen this"になる。

私の解答はこちら。

import java.util.Arrays;

public class MnemonicMemory {

 public String getPhrase(String number, String[] dictionary) {
  Arrays.sort(dictionary); // 単語の長さごとにアルファベット順でソート
  StringBuilder sb = new StringBuilder();
  boolean[] isUsed = new boolean[dictionary.length]; // 使用済みの単語の位置にtrueを入れる
  for( int i=0 ; i<number.length() ; i++ ){
   int n = number.charAt(i) - '0'; // 文字数を解釈
   for( int j=0 ; j<dictionary.length ; j++ ){
    // 未使用の単語が登場して、文字数が条件に合う
    if( dictionary[j].length() == n && isUsed[j] == false ){
     isUsed[j] = true;
     sb.append(dictionary[j]);
     sb.append(" ");
     break;
    }
   }
  }
  return sb.toString().trim(); // 最後の空白を削るためtrim()する
 }

}

得点は218.56/250、中央値は約187点。最初にソートしておくことで、文字数が一致した物のうち、先頭に出てきた未使用の単語を利用すればよいということにできるのがポイント。