TopCoder SRM358 Div2 500Pts

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

あなたはteletextのページ(テレビの情報サービスのこと。番号を入力して情報を参照する。)をみたいと思っている。不幸なことに、リモコンの番号がいくつか壊れてしまっている。そこでいい考えを思いついた。もし、見たいページの番号が入力できなければ別の番号を入力して"+"あるいは"-"を入力してほしい番号へ行けばよいではないか。ここでいう"+"は番号を1増やし、"-"は番号を1減らすという操作である。

あなたは最初に100というページを見ている。別の番号に向かうために、壊れていない番号を用いてページ番号を入力する。そして"+"と"-"で目的の番号へ移動する。pageという目的のページ番号(整数)とbroken[]という壊れた数字の一覧が与えられたとき、目的のページ番号へ向かうのに必要なボタンの押下回数の最小値を求めよ。なお、"+"と"-"のボタンは壊れていないものとする。

例えば、5457に向かいたいときに{6, 7, 8}のボタンが故障している場合、6回ボタンを押すことになる。5455++、5459--という順でボタンを押すことになるからである。

私の解答はこちら。

public class BrokenButtons {

 public int minPresses(int page, int[] broken) {
  if( page == 100 ) return 0; // 初期状態の番号ならボタンを押す必要なし
  if( broken.length == 10 ){ // 全部壊れているなら"+"と"-"を押すしかない
   return page >= 100 ? page - 100 : 100 - page;
  }
  int smallNearest = -1; // broken[]の要素を含まないpage以下でpageに最も近い数
  int bl = broken.length;
  for( int i=0 ; i<=page ; i++ ){
   boolean isUsable = true;
   int num = i;
   while( true ){
    int n = num % 10;
    for( int j=0 ; j<bl ; j++ ){
     if( n == broken[j] ){
      isUsable = false;
      break;
     }
    }
    num /= 10;
    if( num == 0 ) break;
   }
   if( isUsable ) smallNearest = i;
  }

  int largeNearest = 1000000;// broken[]の要素を含まないpage以上ででpageに最も近い数
  for( int i=1000000 ; i>=page ; i-- ){
   boolean isUsable = true;
   int num = i;
   while( true ){
    int n = num % 10;
    for( int j=0 ; j<bl ; j++ ){
     if( n == broken[j] ){
      isUsable = false;
      break;
     }
    }
    num /= 10;
    if( num == 0 ) break;
   }
   if( isUsable ) largeNearest = i;
  }
  // 比較では100からの"+"、"-"による移動も考慮する。
  // 例えば、101は再入力よりも+だけがボタン押下回数が少なくなる
  int ret = page >= 100 ? page-100 : 100-page;
  if( smallNearest >= 0){ // page=0のときの対処が特殊
   int sNType = page - smallNearest + ("" + smallNearest).length();
   ret = Math.min(sNType, ret);
  }
  int lNType = largeNearest - page + ("" + largeNearest).length();
  ret = Math.min(lNType, ret);

  return ret;
 }

}

得点は150/500、3回目のsubmitでようやくシステムテストクリア。大きな方針としては、page以下で入力可能な最大値とpage以上で入力可能な最小値を入れて、そこから+と-の入力回数を加えてどちらが近いか比較するというものである。システムテストには通るが、500msecぐらいかかるのでひどい実装ではある。largeNearestの評価は実は1000000(問題の設定上とりうる最大値)からではなく、page+(page-smallNearest)でよいので、そうすれば多少の計算量削減が期待できる(100万程度なら全部回しても2秒という実行時間の制限はクリアできるとは思っておりましたが)。また、利用可能かどうかを判定するロジック(boolean isUsable～ if(isUsable)の行)は2回コードに現れているので、可読性向上のためにモジュール化した方が良いでしょう。2部の提出者正解率は8%程度でした。場合分けで漏れが生じやすいので、難しいと思います。

TopCoder SRM356 Div2 250Pts

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

SMSメッセージは携帯電話の間でやりとりされる短いメッセージである。最大長で160文字であり、しばしば短縮形が必要となる。textという文字列が与えられたとき、SMS用の言語に変換したものを返せ。変換のルールは次に従う。上にあるものほど優先される。

変換前	変換後
"."、","、"?"、"!"	削除("")
A-Z(大文字)	a-z(小文字)
and	&
ate	8
at	@
you	U

以上の変換を文字列textに対して行った結果を返すメソッドを作成せよ。

私の解答はこちら。

public class SMSLanguage {

 public String translate(String text) {
  text = text.toLowerCase();
  text = text.replace(".", "");
  text = text.replace(",", "");
  text = text.replace("?", "");
  text = text.replace("!", "");
  text = text.replace("and", "&");
  text = text.replace("ate", "8");
  text = text.replace("at", "@");
  text = text.replace("you", "U");

  return text;
 }

}

へぇ、replaceメソッドは先頭だけでなく、文字列中の全部の要素を書き換えてくれるんだというのが最初の感想。IDEが便利すぎて驚きます。

TopCoder SRM355 Div2 250Pts

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

ロシアではほとんどの商品にかかる税金は18%であるが、特定の食品の税率は10%である。問題では引数にproductという商品名とpriceというその価格、food[]という税率が10%になる食品名の一覧が与えられる。productが課税されたあとの価格を計算して返すメソッドを作成せよ。

私の解答はこちら。

public class ValueAddedTax {

 public double calculateFinalPrice(String product, int price, String[] food) {
  for( int i=0 ; i<food.length ; i++ ){
   if( product.equals(food[i]) ) return 1.1*price;
  }
  return 1.18*price;
 }

}

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

TopCoder SRM354 Div2 250Pts

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

Thimblesは以下のルールに従ったゲームである。ディーラーは3つの指ぬきをテーブルにおき、1番の指ぬきの下に小さなボールをいれる。つぎに2つの指ぬきの位置を交換することを繰り返す。最後にディーラーはどこにボールがあるかを尋ね、正しい指ぬきを選べば勝ち、そうでなければ負けとなるというものである。これをコンピュータで実装しようとしている。この問題では、あなたは指ぬきの位置交換が終わった時に、ボールがどこにあるかを返すモジュールを作成することになる。swaps[]という交換の順番を示した文字列型配列が与えられる。各要素は"X-Y"という形式で与えられ、XとYの位置にある指ぬきを交換したという意味になる。位置は1、2、3のいずれかである。swaps[]の交換がすべておわったとき、ボールが最後にどの位置にあるかを返すメソッドを作成せよ。

私の解答はこちら。

public class Thimbles {

 public int thimbleWithBall(String[] swaps) {
  int pos = 1;
  for( int i=0 ; i<swaps.length ; i++ ){
   String[] ns = swaps[i].split("-");
   int p1 = Integer.parseInt(ns[0]);
   int p2 = Integer.parseInt(ns[1]);
   if( p1 == pos ){
    pos = p2;
   }else if( p2 == pos ){
    pos = p1;
   }
  }
  return pos;
 }

}

得点は245.83/250、中央値は約223点。1回のsubmitでシステムテストクリア。上の書き方なら1～3に限定されないので、既に簡単な拡張ができてますね。

TopCoder SRM145 Div2 500Pts

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

あなたは運動機器のファームウェアプログラムを書いている。1秒ごとに作業が何パーセント終わったかを表示するか決めるルーチンが呼び出されている。ディスプレイは小数点以下は表示できないので、全体の運動に対してちょうどのパーセンテージになったとき(=整数で表示できるとき)のみ、ルーチンはディスプレイにパーセンテージを表示する。
timeという運動を続ける時間が"hh:mm:dd"の形式で与えられたとき、ルーチンにより何度パーセンテージがディスプレイに表示された回数を返すメソッドを作成せよ。なお、この機械は0%と100%は表示しないものとする。

例えば30分(=1800秒)は99回表示する。18秒ごとに表示すれば1%ずつ進捗状況を表示できるからである。

私の解答はこちら。

public class ExerciseMachine {

 public int getPercentages(String time) {
  String[] t = time.split(":");
  int hours = Integer.parseInt(t[0]);
  int minutes = Integer.parseInt(t[1]);
  int seconds = Integer.parseInt(t[2]);
  seconds += hours * 3600;
  seconds += minutes * 60;
  int nDisp = 0;
  // 何パーセントごとに表示しうるかを求める
  // 100 / 1 = 100, 100 / 2 = 50, ... , 100 / 10 = 10まで求めれば
  // 返り値の候補が以下のようになることがわかる。
  // 33.3%ごとに表示されてしまうため、100 / 3 などはダメ。
  int[] candidates = {1, 2, 4, 5, 10, 20, 25, 50, 100};
  for( int i=0 ; i<candidates.length ; i++ ){
   if( seconds % candidates[i] == 0 ) nDisp = candidates[i]-1;
  }
  return nDisp;
 }

}

得点は418.00/500、1回のsubmitでシステムテストクリア。timeが与えられたときに、きれいに何パーセント終了したという状態が表示できる回数の最大値を求めよということらしい。解候補がcandidatesしかないという決め打ちによる回答はほとんどないようでした。解答よりも問題文の理解に時間がかかりました。

TopCoder SRM146 Div2 500Pts

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

高さheight、幅widthの格子の中に、長方形(正方形は含まない)がいくつあるかを数えて返すメソッドを作成せよというのが問題である。例えば下図のような2*2の格子であれば、1*2の長方形が2つ、2*1の長方形が二つなので、4を返すことになる。1*1や2*2の長方形は数えないことに注意。
__ __
|__|__|
|__|__|

私の解答はこちら。

public class RectangularGrid {

 public long countRectangles(int width, int height) {
  long nRec = 0;
  for( int i=1 ; i<=width ; i++ ){
   for( int j=1 ; j<=height ; j++ ){
    if( i==j ) continue; // 正方形は考慮しない
    nRec += (width+1-i)*(height+1-j); // 幅i、高さjの長方形の数をnRecに加えている
   }
  }
  return nRec;
 }

}

得点は481.20/500、1回のsubmitでシステムテストクリア。方針は2通りで、全部数えて正方形を取り除く方法、正方形以外を逐次カウントする方法があるはず(上の回答は後者)。他のコードを読んでみると、変数名が違う程度で、ほぼ同じ回答もあった。アイディアが問題であるが、500点問題にしては容易であった。

TopCoder SRM353 Div2 250Pts

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

(x1, y1)、(x2, y2)を焦点とする楕円で、2点の距離の和がdで与えられるとき、楕円の中に格子点(x,y座標が共に整数になる点)がいくつあるかを数えて返すメソッドを作成せよという問題である。

私の解答はこちら。

public class EllipseCoverage {

 public int calculateCoverage(int x1, int y1, int x2, int y2, int d) {
  int[] xrange = new int[2];
  int[] yrange = new int[2];
  // とりうる値の範囲を長方形状にしておく(計算量削減のため)
  xrange[0] = Math.min(x1, x2)-d;
  xrange[1] = Math.max(x1, x2)+d;
  yrange[0] = Math.min(y1, y2)-d;
  yrange[1] = Math.max(y1, y2)+d;
  int nInEllipse = 0;
  for( int i=xrange[0] ; i<=xrange[1] ; i++ ){
   for( int j=yrange[0] ; j<=yrange[1] ; j++ ){
    double dx1 = x1-i;
    double dx2 = x2-i;
    double dy1 = y1-j;
    double dy2 = y2-j;
    // 楕円の中というのは2点間の距離の和がd未満ということになる
    if( Math.sqrt(dx1*dx1+dy1*dy1) + Math.sqrt(dx2*dx2+dy2*dy2) < d){
     nInEllipse++;
    }
   }
  }
  return nInEllipse;
 }

}

得点は229.53/250、中央値は約162点。1回のsubmitでシステムテストクリア。実際には焦点の座標は-100～100の整数値しかとらないので、全探索でも解けるのですが、規模が大きくなる場合は探索範囲を絞るのがコツに思います。上のコードでは取り得るx,yの値の範囲を計算して、求める点がすべて含まれる小さな長方形の形状にし、範囲を絞って全探索しました。コーディングでは、<= dとして少し嵌ってましたが、問題文をよく読んで解決しています。

TopCoder SRM352 Div2 250Pts

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

学生がさぼるので、授業に75%以上出席した者のみ、試験を受けることを許したい。names[]という学生の名前とattendance[]という出席記録を基に、出席率が75%未満の学生の一覧を返すようなメソッドを作成せよ。

namesのi番目とattendanceのi番目が対応する。また、attendanceの内容については、AとPとMという文字が含まれている。Aは欠席、Pは出席、Mは欠席だが課題を出したということに対応している。欠席したが課題を出した場合(つまにMの場合)、その授業は出席率にカウントされない。出席率の要件を満たさない学生の一覧を文字列型配列にして返せ。配列の要素はnamesに現れた順序を守るようにせよ。

私の解答はこちら。

import java.util.ArrayList;

public class AttendanceShort {

 public String[] shortList(String[] names, String[] attendance) {
  ArrayList<String> al = new ArrayList<String>();
  for( int i=0 ; i<names.length ; i++ ){
   int nA = 0;
   int nP = 0;
   for( int j=0 ; j<attendance[i].length() ; j++ ){
    if( attendance[i].charAt(j) == 'A' ){
     nA++;
    }else if( attendance[i].charAt(j) == 'P'){
     nP++;
    }
   }
   if( (double)nP/(nA+nP) < 0.75 ){
    al.add( names[i] );
   }
  }
  return (String[])al.toArray(new String[al.size()]);
 }

}

得点は175.14/250、中央値は約160点。3人撃墜して+150点。PMMMMMMMMMAなど、Mが大量にあるケースが考慮されていない解答を撃墜(実際にはattendanceの科教祖はPとAが1回以上必ず登場する)。rng_58さんの回答は30秒ほど意図が分からず驚きましたが、その意図を理解すると、出席率の判定ロジックに小数点以下を利用しない回答として面白かったです。この問題の0.75については2進数で正確に表現可能なので、実数の不等式で判別しても問題ないとは思いますが、精度を気にする場合のアイディアとして役立てられそうでした。

TopCoder SRM350 Div2 250Pts

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

文字列のある1文字に関する距離は(n1-n2)^2で定義される。n1とn2はそれぞれ1番目と2番目の文字列の文字の出現回数(大文字と小文字を区別しない)である。これら2つの文字列に対する距離に関する3番目の文字列とは、3番目の文字列に現れた文字についてのみ2つの文字列の距離の総和をとったものである。問題ではa、b、letterSetという3つの文字列が与えられる。letterSetは各文字が異なっている。このときletterSetに登場する文字について、aとbの文字列の距離を計算してその値を返せ。

私の解答はこちら。

public class DistanceBetweenStrings {

 public int getDistance(String a, String b, String letterSet) {
  int dist = 0;
  a = a.toLowerCase(); // 大文字と小文字の区別をなくす
  b = b.toLowerCase();
  // letterSetの各文字について距離を計算する
  for( int i=0 ; i<letterSet.length() ; i++ ){
   char c = letterSet.charAt(i);
   int na = 0;
   for( int j=0 ; j<a.length() ; j++ ){
    if( a.charAt(j) == c ) na++;
   }
   int nb = 0;
   for( int j=0 ; j<b.length() ; j++ ){
    if( b.charAt(j) == c ) nb++;
   }
   dist += (na-nb)*(na-nb);
  }
  return dist;
 }

}

得点は208.34/250、中央値は約187点。全部小文字として扱えという条件を見落として2回目のsubmitでシステムテストクリア。

TopCoder SRM351 Div2 250Pts

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

あなたは自分の部屋のドアに番号をつけようとしている。家の近くの店からは、プラスチックでできた素敵な数字のセットが提案された。セットはきっちり10個の桁を含んでいる。10個の各桁は0～9の整数である。roomNumberという部屋番号が与えられたとき、必要となる数字のセットの数を返せ。なお、6は9としても使える(その逆も然りである)。

例えば6699であれば2となり、1234567890であれば1、112345は2という結果が返されることになる。

私の解答はこちら。

public class RoomNumber {

 public int numberOfSets(int roomNumber) {
  int[] n = new int[10];
  while( roomNumber > 0 ){
   int mod = roomNumber % 10;
   n[mod]++; // 数字の出現回数をカウント
   roomNumber /= 10;
  }
  int n69 = 0; // 6と9が登場した回数
  int max = 0;
  for( int i=0 ; i<n.length ; i++ ){
   if( i!=6 && i!=9 ){ // 6と9以外で必要なセット数の最大値を計算
    max = Math.max(max, n[i]);
   }else{ // 6と9だけは登場回数をカウント
    n69 += n[i];
   }
  }
  n69 = n69%2 == 0 ? n69/2 : n69/2+1; // 6と9で必要になるセット数を計算
  max = Math.max(max, n69);
  return max;
 }

}

得点は219.52/250。1回の提出でシステムテストクリア。6と9の数だけはroomNumberに6と9が出現した回数の合計で考えなければならない。解答の作成よりも、問題文の読解に手間取った感がありました。

TopCoder SRM349 Div2 250Pts

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

あなたは文書をスキャンして、何回特定の単語・フレーズが現れたかをカウントする関数を書く仕事を与えられた。しかし
オーバーラップして出現回数を数えないということが重要である。例えば"abababa"という文字列で"ababa"というキーワードの出現回数を数えるとき、添え字0からと添え字2からの2つがあるが、重なっているので両方を数えることはしてはならない。また、docという文字列型配列を1つの文字列に結合しなければならない。そして、searchという文字列が重ならないという条件で最大でいくつ登場するかを数えて返せ。

私の解答はこちら。

public class DocumentSearch {

 public int nonIntersecting(String[] doc, String search) {
  StringBuilder sb = new StringBuilder();
  for( int i=0 ; i<doc.length ; i++ ){
   sb.append(doc[i]); // 文字列の結合
  }
  String docs = sb.toString();
  int n = 0;
  int len = search.length();
  while( true ){
   int idx = docs.indexOf(search); // 初めてsearchが現れる位置を探索
   if( idx < 0 ) break;
   n++;
   // docsを更新してsearchの最後の文字以前を取り除く
   docs = docs.substring(idx+len);
  }
  return n;
 }

}

得点は240.75/250、中央値は約192点。1回のsubmitでシステムテストクリア。コード中で利用しているStrignクラスのメソッドindexOfにはfromIndexという引数をとる方法がある。これにより、文字列の途中から探索できるので、docsの更新は不要になる。オブジェクトの繰り返し生成を避ける際に有効になるでしょう。

TopCoder SRM348 Div2 250Pts

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

ビリーは祖母の家に行こうとしている。そんな彼を手助けするために、母は従うべき指示をリストにしたものを彼のために書いた。各指示は"N"、"S"、"W"、"E"であり、それぞれ1ブロックだけ北、南、西、東に進めということを意味している。ビリーの住む町は無限に大きなマス目状の通りからなり、どの道も無限に伸びており、同じ方向にむかう隣あう2つの道の間の距離はいつも1ブロックである。ビリーの家と祖母の家はどちらもこの町の角にある。

ビリーは母が必ずしも最短経路を選んで指示を書いてくれないということを知っている。したがって、ビリーは最小の指示で祖母の家に向かえるような新しい指示のリストを作成したいと思っている。instというビリーの母が書いた指示を表した文字列が与えられたとき、ビリーの欲しい新しいリストを作成して返すメソッドを作成せよ。もし複数解があるなら、アルファベット順で最初に来るものを返すようにせよ。

私の解答はこちら。

public class OptimalList {

 public String optimize(String inst) {
  int[] dir = new int[2]; // 上下、左右に動くべき数を入れる
  for( int i=0 ; i<inst.length() ; i++ ){
   if( inst.charAt(i) == 'N'){
    dir[0]++;
   }else if( inst.charAt(i) == 'S'){
    dir[0]--;
   }else if( inst.charAt(i) == 'W'){
    dir[1]++;
   }else if( inst.charAt(i) == 'E'){
    dir[1]--;
   }
  }
  char col = dir[0] >= 0 ? 'N' : 'S'; // 動いた方向を決める
  char row = dir[1] >= 0 ? 'W' : 'E';
  StringBuilder ret = new StringBuilder();
  // アルファベット順にしないといけないのでcol、rowの文字を比較している
  if( col < row ){
   for( int i=0 ; i<Math.abs(dir[0]) ; i++ ) ret.append(col);
   for( int i=0 ; i<Math.abs(dir[1]) ; i++ ) ret.append(row);
  }else{
   for( int i=0 ; i<Math.abs(dir[1]) ; i++ ) ret.append(row);
   for( int i=0 ; i<Math.abs(dir[0]) ; i++ ) ret.append(col);
  }
  System.out.println(ret.toString());
  return ret.toString();
 }

}

得点は187.04/250、中央値は約201点。1回のsubmitでシステムテストクリア。NとS、WとEはペアであることに注目。例えばinst中のNとSの出現回数をカウントし、その回数の差だけ動けば移動距離は最短にできる。WとEの場合も同様である。

TopCoder SRM347 Div2 250Pts

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

あなたは可能な限り安い選択で新しい車を買いたいと思っている。ただ、初期購入費用は車にかける費用の一部であり、税金や燃費も車選びの決定に関係づけたいと思っている。問題ではcars[]という車のモデルの特徴が与えられ、1年に走る距離を表すannualDistanceが与えられる。えらんだ車に対し、購入費用は1度だけ、税金は年に1度、燃料にかかる費用は「fuelPrice*走った距離/燃費」で与えられる。yearsだけ年数が経過したときに、最小のコストになる車を選び、そのときの所有にかかる維持費を実数型で返せ。cars[]は"<購入初期費用> <税金> <燃費>"で与えられる。

私の解答はこちら。

public class CarBuyer {

 public double lowestCost(String[] cars, int fuelPrice, int annualDistance, int years) {
  double ret = Double.MAX_VALUE;
  for( int i=0 ; i<cars.length ; i++ ){
   String[] vals = cars[i].split(" ");
   int purchaseCost = Integer.parseInt(vals[0]); // 初期購入費用
   int tax = Integer.parseInt(vals[1]); // 税金
   int fuelEfficiency = Integer.parseInt(vals[2]); // 燃費
   double totalCost = (double)purchaseCost + (double)tax * years + 
    (double)fuelPrice * annualDistance * years / fuelEfficiency;
   ret = Math.min(ret, totalCost);
  }
  return ret;
 }

}

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

TopCoder SRM346 Div2 250Pts

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

あなたは奇妙な鉱物の中にあるダイヤモンドを探すダイヤモンドハンターである。鉱物は"<"と">"という文字からなる文字列で、ダイヤモンドは"<>"という部分列である。ダイヤモンドを見つける度に、それを除いたものが残りの鉱物として扱われる。"><<><>>><"という文字列が与えられると、"><<>>><"となり、"><>><"になる。さらにもう一度取り除いて">><"となると、鉱物にダイヤモンドは無くなり、"<>"を取り除く操作は終了する。mineという"<"、">"からなる文字列が与えられたとき、その中に含まれるダイヤモンドの数を返せ。なお、どの順でダイヤモンドを取り除いたとしても、同じ結果になることに注意せよ。

私の解答はこちら。

public class DiamondHunt {

 public int countDiamonds(String mine) {
  StringBuffer sb = new StringBuffer();
  int nDiamonds = 0;
  while( true ){
   boolean diaRemain = false;
   int pos = -1;
   // ダイヤモンドの存在判定
   for( int i=0 ; i<mine.length()-1 ; i++ ){
    if( mine.charAt(i) == '<' && mine.charAt(i+1) == '>' ){
     nDiamonds++;
     pos = i;
     diaRemain = true;
     break;
    }
   }
   if( diaRemain == false ){
    break; // ダイヤモンドが存在しないならカウント終了
   }else{
    // 上で見つけた文字(pos、pos+1の位置にある"<>")を除く
    for( int i=0 ; i<mine.length() ; i++ ){
     if( i == pos || i == pos+1 ) continue;
     sb.append(mine.charAt(i));
    }
    mine = sb.toString();
    sb.delete(0, sb.length());
   }
  }
  return nDiamonds;
 }

}

得点は204.24/250、中央値は約214点。1回の提出でシステムテストクリア。ちょっと長めのコードですが、やろうとしていることは単純。

TopCoder SRM345 Div2 250Pts

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

山の一部を小旅行することを計画している。旅行では歩くのに何日か費やし、夜はテントで過ごすことになる。山はあまり友好的ではない（山は急であり、岩はごつごつしている箇所がある）ため、キャンプをするのに適さない場所が多く存在する。問題ではtrailという歩く場所を順に表した文字列が与えられる。trail[i]が"."であればi番目は泊まるのに適切な場所であるし、"^"であれば適切でないということになる。また、plansという文字列型配列も与えられる。plans[i][j]は"w"であればi番目の計画の位置jでは歩くということを意味し、"C"であればその場所jでキャンプを行うということになる。計画が不適切というのは、キャンプを行うのに不適切な場所でキャンプをするということである。trailとplansに対し、山で過ごすのが最初の日数となる妥当な計画のうち、計画の番号が最小となるものを返せ。すべての計画が不適切であれば、-1を返すようにせよ。

私の解答はこちら。

public class Trekking {

 public int findCamps(String trail, String[] plans) {
  int minNights = trail.length()+1; // 最小値の初期値は取りえない大きめの値に設定
  for( int i=0 ; i<plans.length ; i++ ){
   boolean isValidPlan = true;
   int nNights = 0;
   for( int j=0 ; j<plans[i].length() ; j++ ){
    if( trail.charAt(j) == '^' && plans[i].charAt(j) == 'C' ){
     isValidPlan = false; // 不適切な計画と判明、breakを入れた方が処理が速い
    }
    if( plans[i].charAt(j) == 'C' ){
     nNights++; // 日数をカウント
    }
   }
   if( isValidPlan ){
    minNights = Math.min(minNights, nNights);
   }
  }
  return minNights == trail.length()+1 ? -1 : minNights;
 }

}

得点は231.71/250、中央値は約196点。1回でシステムテストクリア。不適切な計画が明示的にどういう条件か理解すればすぐに解ける。

TopCoder SRM343 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。画像が問題に含まれるので、問題文を直接見ることを推奨する。では、問題についておおまかに説明する。

8*8のチェスボードは列方向にa～h（左がa、右がh）、行方向に1～8(最下段が1、最上段が8)が割り当てられている。マスは"e4"のように、その行と列の文字から表される。さて、チェスのプログラムに取り組んでいるときに、先述の表記とマスを表す数字とを変換する必要が生じた。数値表現する場合、内部的にはマスを1から64で表している。つまり、a1は1、b1は2、...、h8は64ということになっている。cellというセルを表す文字あるいは数値の文字列が与えられたとき、その表記を変換せよ（文字<->数値の変換を行えということである）。

私の解答はこちら。

public class Chessboard {

 public String changeNotation(String cell) {
  // cellの1文字目が数字か文字列かで変換方法が異なる
  if( Character.isLowerCase(cell.charAt(0)) ){
   return aton(cell);
  }else{
   return ntoa(cell);
  }

 }
 // ascii to number(文字表現を数値に変換)
 private String aton(String c){
  int n = (c.charAt(0)- 'a' + 1) + (c.charAt(1) - '0' - 1) * 8;
  return "" + n;
 }
 // number to ascii(数値表現を文字に変換)
 private String ntoa(String c){
  int n = Integer.parseInt(c);
  char f = (char)((n-1) % 8 + 'a');
  int s = (n-1) / 8 + 1;
  return "" + f + s;
 }
}

得点は204.32/250、中央値は約110点。提出者の正解率約46%。場合分けの方法が1つ目の難関、あとは変換ロジックをそれぞれで書けばよい。思ったより中央値の点数が低い印象です。

TopCoder SRM342 Div2 250Pts

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

xという数字が与えられたとき、p(x)はxの各桁の積と定義する。すると、x、p(x)、p(p(x))のように数列を作成できる。xのpersistence(持続性などと訳されるか)とは、数列中の値がはじめて1桁の数字になったときの数列の添え字である(先頭は0とする)。例えば99は9*9=81、8*1=8なので2となる(数列としては99、81、8である)。さて、nという数値が与えられたとき、その数字のpersistenceを求めて返せ。

私の解答はこちら。

public class PersistentNumber {

 public int getPersistence(int n) {
  int nPersist = 0;
  while( true ){
   if( n<10 ) break; // 終了条件
   int tmp = n % 10;
   n = n / 10;
   while( n > 0 ){ // 数列の次の値を計算
    tmp *= n % 10;
    n = n / 10;
    System.out.println(tmp);
   }
   nPersist++; // 添え字を1つ進める
   n = tmp;
  }
  return nPersist;
 }

}

得点は226.31/250、中央値は約228点。各桁の積をどのように定義するかというのが考えどころ。

TopCoder SRM341 Div2 250Pts

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

地理学では、緯度・経度など地理的な計測に用いられるもののように、角度は60を基数として計測されることがある。基本単位は度である。1度が60分、1分が60秒として扱われる。度、分、秒が整数値で測定されたものが引数として与えられたとき、それを弧度法(=ラジアン)の値にして返せ。なお、n度というのはn*PI(円周率)/180ラジアンに一致する。

私の解答はこちら。

public class DegreesToRadians {

 public double convertToRadians(int degrees, int minutes, int seconds) {
  double n = degrees + minutes/60.0 + seconds/3600.0;
  return n*Math.PI/180;
 }

}

得点は246.99/250、中央値は約237点。与えられた引数から度を実数で計算して、式に当てはめるだけなので、特に悩む箇所はなし。

2012年2月の学習記録

2012年2月に学習した主な本一覧。忙しさが増してほとんど何もできず。

大学生の微積分(pp.103～167)

チェインルールは超重要公式。調和関数は特別扱いするのはなぜだろう...?物理で使うのかな。

高専の数学3問題集(2章)

ひき続き演習。

TopCoder SRM340 Div2 250Pts

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

アルファベットの小文字のみからなる同じ長さの文字列AとBが与えられる。二つの文字の距離というのを、差の絶対値で定義される。文字列AとBの距離はAとBの同じ位置にある文字の距離の和として定義する。例えば"abcd"と"bcda"の距離は6となる(aとbの距離は1、dとaの距離は3などとして求められる)。Aの文字のうち、K文字を変えなければならない。このとき、AとBの文字の距離を最小値を返せ。

私の解答はこちら。

import java.util.Arrays;

public class ChangingString {

 public int distance(String A, String B, int K) {
  int[] diff = new int[A.length()];
  int dist = 0;
  // ひとまず1文字ごとに距離計算
  for( int i=0 ; i<A.length() ; i++ ){
   diff[i] = Math.abs(A.charAt(i)-B.charAt(i));
  }
  Arrays.sort(diff);
  // 距離の大きい方からK個の値を変更
  for( int i=0 ; i<K ; i++ ){ 
   int idx = diff.length-i-1;
   if( diff[idx] > 0 ){
    diff[idx] = 0;
   }else{
    diff[idx] = 1;
   }
  }
  // 距離の合計を計算
  for( int i=0 ; i<diff.length ; i++ ){
   dist += diff[i];
  }
  return dist;
 }

}

得点は241.67/250、中央値は約196点。距離の大きさで順に並び替えて、大きい方からK個の距離を0にすればよい。もし、距離の大きいK個の値に0が含まれていたら、それは1とすればよい。Aの文字をK個強制的に変えなければならないので、0のままではダメということである。

TopCoder SRM339 Div2 250Pts

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

CSSのプロパティ名はすべて小文字で単語の区切りが"-"となっているのが典型的である。しかしながら、JavaScriptを用いてCSSプロパティを設定しようとするなら、キャメルノーテーションを使う必要がある。キャメルノーテーションでは、最初の単語を除いて単語の先頭は大文字となり、隣の単語との区切り文字はない。cssPropertyNameという"-"で単語が区切られた表記が与えられたとき、それをキャメルノーテーションに書き換えたものを返せ。

私の解答はこちら。

public class CssPropertyConverter {

 public String getCamelized(String cssPropertyName) {
  String[] sp = cssPropertyName.split("-");
  StringBuffer ret = new StringBuffer();
  for( int i=0 ; i<sp.length ; i++ ){
   char[] tmp = sp[i].toCharArray();
   if( i > 0 ){ // 先頭の文字を差替
    tmp[0] = Character.toUpperCase(tmp[0]);
   }
   ret.append(tmp);
  }
  return ret.toString();
 }

}

得点は244.96/250、中央値は約222点。charの配列に変換して先頭だけ差し替えるという手法で解けたので、コーディングが簡単にできました。