TopCoder SRM179 Div2 250pts

本日の問題はこちら(要TopCoder登録 & 問題文は英語)。

問題のおおまかに説明する。

配列scoresの各要素に対して順位を計算する。順位を決める際には直近のk個のデータと比較する。このとき、全体の順位の合計を計算して返すメソッドcalcRanksを作成せよ。

例えば、scores[]={3,3,2}でk=1としたら、先頭の要素は1位、2番目の要素は先頭と同点なので1位、3番目の要素は2番目と比較して小さいので2位となり、順位を合計すると1+1+2=4になる。

public class OnLineRank {
 public int calcRanks(int k, int[] scores) {
  int sumRank=0;
  int start;
  int tmpRank=1;
  for( int i=0 ; i<scores.length ; i++){
   start = i-k>=0?i-k:0;
   tmpRank = 1;
   for( int j=start ; j<i ; j++){
    if( scores[j]>scores[i] ){
     tmpRank++;
    }
   }
   sumRank += tmpRank;
  }
  return sumRank;
 }
}

得点は209.43/250。解答のポイントは先頭の要素がkに足りないときの例外的な処理の部分である。あとは同点の場合の順位の処理で間違えないことと思われる。特に悩むことはなく素直に実装できた。ただし点数はあまり高くないが(2部リーグの回答者の平均より少し速い程度)。

TopCoder SRM178 Div2 250pts

本日の問題はこちら(要TopCoder登録 & 問題文は英語)。

問題のおおまかな訳は以下の通り。

四則演算ができる計算機クラスSimpleCalculatorを考える。入力の形式は文字列で入力され、<数値> <op> <数値>という形式をしている。<数値>は1以上10000以下の数である。<op>は+、-、*、/のどれかである。このとき、演算結果を返すSimpleCalculatorのメソッドcalculateを作成せよ。結果は0以下になることも当然ありうる。

例えば、"200/4"という文字列が入ってきたら答えは50である。

私が書いたコードはこちら。

public class SimpleCalculator {
 public int calculate(String input) {
  int[] num = new int[2];
  String[] snum = new String[2];
  String sop="";
  String[] ops = new String[]{"+","-","*","/"};
  int op=0;
  for( int i=0 ; i<ops.length ; i++){ // 数値と数値の間にある記号を判定
   if( input.indexOf(ops[i]) >=0 ){
    op = i;
    sop = ops[i];
    break;
   }
  }
  if( sop.equals("*") ){ // 記号がメタ文字であった場合の対処
   sop = "\\*";
  }else if( sop.equals("+") ){
   sop = "\\+";
  }
  snum = input.split(sop);
  for( int i=0 ; i<2 ; i++){
   num[i] = Integer.parseInt(snum[i]);
  }
  switch(op){ // 文字の種類に応じて処理を決める
   case 0:
    return num[0]+num[1];
   case 1:
    return num[0]-num[1];
   case 2:
    return num[0]*num[1];
   case 3:
    return num[0]/num[1];
   default:
    break;
  }
  return 0;
 }
}

得点は158.30/250(System Test Passed)。点数も低いし、汚いコードになってしまった。

最初に躓いたのが正規表現で、+や*がメタ文字ではなく、文字列としての+や*にしてならないといけないということに気付かなかった。+と*だけエスケープシーケンスを付けるという汚い書き方で対処。次に汚いコードと感じられる点は変数opで、これをint型でなく、せめてchar型にしておけば、後半のswitch文に意味のある変数として渡せるということである。0,1,2,3という処理はあまりきれいじゃないな。

新しく学んだこととしては、Integer.parseInt("00001")=1になってくれるということである。自動的に先頭の0は削除してくれるようだ。今回のコードはもう少し学べばもっとうまくかけそうだ。

TopCoder SRM177 Div2 250Pts

本日の問題はこちら(要TopCoder登録 & 問題文は英語)。

問題のおおまかな訳は以下の通り。

階段のデザインの組み合わせについて実装する。階段は一定の(蹴上げの)高さと一定の(踏面の)幅を持つものとする。いま、階段の高さの合計をtotalHeight、幅の合計をtotalWidthとする。高さの上限はmaxHeight、幅の下限はminWidthとする。デザインする階段の高さ、幅は共に正の整数とする。totalHeight、totalWidth、maxHeight、minWidthが与えられたときに、階段を設計するする方法は何通りあるかを返すメソッドdesignsを作成せよ。

私の回答は以下の通り。

public class Stairs {
 public int designs(int maxHeight, int minWidth, int totalHeight, int totalWidth) {
  int raiser, treads;
  int n = 0;
  for( int i=1 ; i<=totalWidth/minWidth ; i++){
   treads = i; # 踏面の数
   raiser = i+1; # 蹴上の数
   if( totalWidth%treads != 0 ) continue; # 踏面の幅は整数でなければならない
   if( totalHeight/raiser <=maxHeight){ # 蹴上の高さは上限以下で、整数でなければならない
    if( totalHeight%raiser == 0  ){
     n++;
    }
   }
  }
  return n;
 }
}

踏面の数は1から最大でtotalWidth/minWidthになる。また、階段の蹴上げの数は踏面の数より1だけ大きいということに気付けば実装ができる。

得点は190.80/250(バグなしにするまで20分弱)。最初、高さと幅が整数でなければならないということに気付かず、回答が遅くなってしまったのが悔やまれる。

TopCoder SRM176 Div2 250Pts

本日の問題はこちら(要TopCoder登録 & 問題文は英語)。

問題のおおまかな訳は以下のようになる。

視覚に訴えかけるメディアでは、特定の部分を引き立たせるため、ある色の補色を考えることがある。補色というのは、画像のRGB値が0-255の範囲で表される場合、RGBのそれぞれの値に対し、255から引き算した値に変換することによって得ることができる。

ただし、RGBの値が128に近いとあまり目立たせることができない。そこで、上記の変換の前後でRGB値の変化がすべて32以下であれば、128足すか引くということを0-255の範囲に収まるように行う。例えば(r,g,b)=(120,130,140)の補色の関係にある色は(r,g,b)=(135,125,115)となるが、いずれの色の変化も32以下なので、(r,g,b)=(120+128,130-128,140-128)=(248,2,12)という変換を行う。130や140に128を足すと255を超えるので、引くことにしなければならないことに注意。

入力rgb[]が与えられたときに、rgb[]の補色を返すようなメソッドgetComplementを作成せよ。クラス名はRGBColorとする。

public class RGBColor {

 public int[] getComplement(int[] rgb) {
  int[] myrgb = new int[rgb.length];
  boolean flg = false;
  for( int i=0 ; i<rgb.length ; i++ ){
   myrgb[i] = 255-rgb[i];
   if( Math.abs(myrgb[i]-rgb[i])>32 ){
    flg = true;
   }
  }
  if( flg == true ){
   return myrgb;
  }else{
   for( int i=0 ; i<rgb.length ;i++){
    if( rgb[i]<=127 ){
     myrgb[i] = rgb[i]+128;
    }else{
     myrgb[i] = rgb[i]-128;
    }
   }
   return myrgb;
  }
 }

}

点数は250点満点の205.14、正解率を考えればまずまずといったところ。最初はflg=trueと書いてバグが出ていたので、それがなければもう少し点数を稼げたかと。

TopCoderの点数と時間の関係をグラフで表す

競技プログラミングTopCoderでは、解いた時間の速さに応じて点数が決まる。こちらで時間から点数を計算する式が示されているので、逆に点数から自分が回答にかかった時間を計算するために、Rで関数を書いてみることにした。

TimeToPoint <- function(x,mP,mT){
 mP*(0.3+(0.7*mT^2)/(10*x^2+mT^2))
}

timeNeeded <- function(p,maxPts=250,maxTime=75){
 res <- uniroot(function(x){TimeToPoint(x,mP=maxPts,mT=maxTime)-p},interval=c(0,maxTime))$root
}
result <- timeNeeded(p=237.93)
result

Rのインタプリタ上で上記コードを実行すると、timeNeeded関数に237.93点を与えた場合、resultには6.455(分)という解くのにかかった時間が代入される。

以下コードの解説。

timeNeeded関数の引数はpが獲得した点数、maxPtsがある問題の点数の最大値、maxTimeが解くのに使える時間の最大値である。デフォルトではmaxPtsに250、maxTimeに75(TopCoderにおけるコーディングの時間)を入れてある。必要に応じて変更する。TimeToPointはその名の通り、時間から点数を計算する関数である。

unirootは方程式の根を求める関数である。オプションのintervalで根が存在する範囲を指定する。返り値はリスト形式になっていて、rootが根に相当する。TopCoderの時間と得点の関係は単調減少にあるので、得点を与えれば、一意に点数が定まる。なお、uniroot関数で根を求める方法にはニュートン法が利用されているそうなので、intervalで指定した範囲に複数の解がある場合には利用を避けた方がよいだろう。ニュートン法は区間interval内に複数の根があったとしても、1つの根しか示してくれないからである。

最後に、問題文を開いてから回答までに消費した時間と点数の関係をグラフにする。TimeToPointは既に示した点数と消費時間の関係を表す曲線を描く関数である。

usedTime <- seq(from=0,to=75,by=0.1)
plot(usedTime,TimeToPoint(usedTime,250,75),xlim=c(0,80),ylim=c(75,250),
     xlab="Time",ylab="pts",main="TopCoder",type="l")

TopCoder SRM175 Div2 250Pts

今日も書いたコードのご紹介。本日の問題はこちらから(要TopCoder登録 & 問題文は英語)。

日本語で問題文を要約すると次のようになる。

今あなたは時計の12時の場所にいる。これからコインを投げて、i回目にh(表)が出れば、時計回りにi時間、t(裏)が出れば反時計回りにi時間分時計の周りを動く。hとtが出た順序を示した文字列flipsが与えられたときに、最終的に時計のどの数字の場所にいるか。回答は1-12の整数で回答する(0時はダメ)。ちなみにアメリカで13-24時という時間の表現はミリタリータイムと呼ばれており、軍人さんが使う表現のようである。

例えば、flipsが"hthhhhh"で与えられたとすれば、1-2+3+4+5+6+7=24時間時計回りに回ったので、12(時)と回答すればよいということになる。

実装は以下の通り。得点は237.93(クラス内部の実装で6分台らしい)。toCharArrayというメソッドを最初から知っていればもっと高得点だったに違いない。

public class ClockWalk {
 public int finalPosition(String flips) {
  char[] sp = flips.toCharArray();
  int n=0;
  for( int i=0 ; i<sp.length ;i++){
  if( sp[i] == 'h'){
   n += i+1;
  }else{
   n -= i+1;
  }
 }
 n = n%12;
 if( n<=0 ) n += 12;
 return n;
}

}

TopCoder SRM174 Div2 250Pts

今日の問題はこちら(要TopCoder登録)。

概要は次の通り。クロスワードパズルの行方向を"X...X..X"のように文字列で表す。Xは文字が入らない場所で、.は文字が入る場所を表すとする。クロスワードの各行は配列board[]で与えられている。またsize(>=2)は.が連続して続く数を表すものとする。このとき、パズル全体を見て、行方向で.がちょうどsize個続いている箇所はいくつあるかというのが問題。

上位者の解答を見てなるほどと思ってしまった。こんな時はsplitメソッドでXで区切れば二重ループ一つで解決だ。

public class CrossWord {
 public int countWords(String[] board, int size) {
  int n = 0;
  for( int i=0 ; i<board.length ; i++){
   String[] tmp = board[i].split("X");
   for( int j=0 ; j<tmp.length ; j++){
    if( tmp[j].length() == size){
     n++;
    }
   }
  }
  return n;
 }
}

JavaはCと違って基本的なメソッドをある程度叩き込まないと、ネットとエディタを往復することになり、コーディングに時間がかかりすぎるということを実感。

TopCoder SRM173 Div2 250Pts

問題の詳細はこちらより確認できる(要TopCoder登録)。

問題の大まかな訳は以下の通り。

コンピュータのインストール作業のプログレスバーを実装する。進捗状況に応じて"######.............."のように、#が終了部分、.が終了していない部分として、それらを用いて20文字で表すクラスshowProgressを作成せよ。taskTimes[]が作業一つのタスクにかかる時間、taskCompletedは先頭から順にいくつタスクを終えたかという数を示している。タスクの進捗状況はインストールにかけた時間/インストール終了までにかかる時間である。また、進捗状況の#の数は小数点以下を切り捨てた整数にする。taskCompletedはtaskTimesの要素数を上回らない1以上の数とする。

例えば、taskTimes={20,35,15}、taskCompleted=1とすると、20/(20+35+15)*20=40/7=5.7なので、#は5個、.は15個になる。

Javaで実装すると以下のようになった。

public class ProgressBar {

 public String showProgress(int[] taskTimes, int tasksCompleted) {
  int taskSum=0;
  int taskCompSum=0;
  for( int i=0 ; i<taskTimes.length ; i++){
   taskSum += taskTimes[i];
  }
  for( int i=0 ; i<tasksCompleted ; i++){
   taskCompSum += taskTimes[i];
  }
  int igetaNum = 20*taskCompSum/taskSum;
  int dotNum = 20-igetaNum;
  String result = "";
  for( int i=0 ; i<igetaNum ; i++){
   result = result + "#";
  }
  for( int i=0 ; i<dotNum ; i++){
   result = result + ".";
  }
  return result;
 }

}

得点は235.80/250。素直な算数の実装なので、まずまずの速さ。上位者のコードでためになるものがあったので、メソッドだけ紹介。前回のArrays.sortに続いて、配列操作のメソッドを集めたクラスArraysが再度登場。

import java.util.*;

public String showProgress(){
 int done = 0, total = 0;
 for( int i=0; i<taskTimes.length ; i++ ){
  total += taskTimes[i];
  if( i<tasksCompleted ) done += taskTimes[i];
 }
 char[] r = new char[20];
 Arrays.fill(r, '.');
 Arrays.fill(r, 0, done * 20 / total , '#');
 return new String(r);
}

メモリの節約方法で参考になったものがあったのでこちらも紹介。Stringクラスは値が変更されると、別のメモリ領域に変更された値を割り当てるので、提出したコードのように、Stringクラスの変数に1文字ずつ追加するコードだとメモリを無駄に利用してしまうのである。以下のコードはそれに対策を施したものである。

StringBuffer buf = new StringBuffer("");
  for( int i=0 ; i<20 ; i++ ){
  if( i<igetaNum ){
   buf.append("#");
  }else{
   buf.append(".");
  }
 }
 return buf.toString();

上位の人の書き方にはArrays.fillを使っているものが多かった。行数も少ないし、可読性が高く参考になる。

TopCoder SRM172 Div2 250Pts

昨日のJavaと英語の練習。問題の詳細はこちらより確認できる(要TopCoder登録)。

問題を大雑把に和訳すると以下のようになる。

縄跳びを二人でする。このときできるだけ身長heightの人と同じ身長の人をパートナーにしたい。candidates[]からheightに近い身長順に、候補者二人の身長を取り出し、二人の身長は昇順にして返せ。ただし、heightとの身長差(絶対値だよ!)が同じになった候補者が複数現れた場合は、背の高い方の優先順位を上にせよ。また、candidates[]は同じ身長の値が何度も現れる可能性がある。

例えばcandidates[] = {169,170,166,172},height=168とした場合は{169,170}が回答になる。169は文句なしに選ばれる。166と170は両方ともheight=168との身長の差は2であるが、身長の高い方を優先するためである。

Javaで実装したサンプルはこちら。点数は112.55と大苦戦。

public class SkipRope {
 public int[] partners(int[] candidates, int height) {
  Arrays.sort(candidates);
  int first=-1; // 1番heightに近い人の身長
  int second=-1;
  int firstDiff=100000; // heightとの差の絶対値
  int secondDiff=100000;
  int diff;
  for( int i=0 ; i<candidates.length ; i++){
   diff = Math.abs(candidates[i]-height);
   if( Math.abs(diff) <= firstDiff ){ // 1番height近い人が現れた場合
    secondDiff = firstDiff; // 1番近いのは2番目に移り、
    second = first;
    firstDiff = diff; // 1番目に新たにデータを入れる
    first = candidates[i];
   }else if( Math.abs(diff) <= secondDiff ){
    secondDiff = diff; // 1番heightに近くないが、2番目にheightに近い人が現れた場合
    second = candidates[i];
   }
  }
  int[] result = new int[]{first,second};
  Arrays.sort(result);
  return result;
 }
}

ポイントになるのは初めて知ったArrays.sort()。このメソッドによってcandidatesが昇順にソートされるので、candidatesを先頭から順番に見ていき、heightとの身長差が同じになった場合はあとの方に現れた方を優先度の高い候補者にすれば、身長の高い方が自動的に選ばれるということである。

最初はソートのメソッドを知らず、見せられないよ～というコードを書いていたので、思いの他時間がかかってしまった。2部リーグの正解率も41%台とかなり難問の部類になるようだ。調べてみると、この問題よりも正答率が低かった2部リーグの第1問は、過去出題された約350題のうちわずか9題だった。

上記の内容を補足すると、TopCoderは2部リーグ制をとっている。75分で3問解くルールで、1問目から3問目まで順に難しくなるようにできているのである。

TopCoder SRM165 Div2 250Pts

Eclipse Coderを導入して2日目、以前より速い作業ができるようになったかも。

本日解いた問題を日本語にするとこんな感じ。

1971年までのイギリスの通貨は1シリング=12ペニー、1ポンド=20シリングであった。ペニーの数が与えられたときに、それは何シリング、何ポンド、何ペニーに変換されるか計算し、この順で返せ。ただし、できるだけペニーを多くし、次にポンドをできるだけ多くするものとする。

例えば533ペニーであれば、2ポンド4シリング5ペニーとなる。また入力となるペニーの値は0から10000とする。

public class BritishCoins {
 public int[] coins(int pence) {
  int[] ret = new int[3];
  ret[0] = pence/240;
  pence -= ret[0]*240;
  ret[1] = pence/12;
  pence -= ret[1]*12;
  ret[2] = pence;
  return ret;
 }

}

得点は244.16/250。上から30%ぐらいの位置であった。かなり速いかなとおもっていたけど、簡単な問題だったせいか、皆コーディングが速かった。この問題はOne-linerに書けるようだ。上のretのように無駄に変数を使っていないから、コードが分かりやすい。

public int[] coins(int pence){
 return new int[]{pence/240,pence%240/12,pence%240%12};
}

TopCoder SRM169 Div2 250Pts

昨日に引き続いてJavaと英語の練習。今日の問題設定はこんな感じ。

ある人iがspeed[i]の速さで泳ぐ。distances[i]は泳ぐ距離を表し、currentは川の流れの速さを表す。このとき、泳ぐ人はdistances[i]の距離だけ川を上下する。このとき、ある人iは泳ぎきるのにどれほど時間がかかるか整数値(切り捨て)で求めよ。ただし、川の流れの方がある人iの泳ぐ速さ以上に速い場合は川を上れないので、かかる時間は-1とする。また、泳ぐ距離が0の場合は泳ぐのにかかる時間は0になる。上下の折り返しに時間はかからないものとする。

私が作成した回答は以下の通り。

public class Swimmers{
 public static int[] getSwimTimes(int[] distances,int[] speeds, int current){
  int i;
  int[] result = new int[distances.length];
  for( i=0 ; i<distances.length ; i++ ){
   if( distances[i] == 0 ){
    result[i] = 0;
   }else if( speeds[i]<=current ){
    result[i] = -1;
   }else{
    result[i] = (int)((double)distances[i]/(current+speeds[i]) + (double)distances[i]/(speeds[i]-current));
   }
  }
  return result;
 }
}

結果は226.14/250。キャストと、ifとif elseの内容を逆に書いていたことでコンパイルエラーが発生したが、そのほか特に問題なく実装を行うことができた。Eclipseのプラグイン入れて練習した方がスピードが上がるのかちょっと検討中。デフォルトの環境ではちょっと厳しいかもしれない。

TopCoder SRM171 Div2 250Pts

Javaの練習も兼ねてTopCoderでプログラミング。以下に書いたコードを紹介するがLevelUpという整数型を返すクラスを実装する。問題を日本語に訳すと以下のような問題である。

よくあるRPGではモンスターを倒して経験値を稼ぐことでレベルが上がるが，これについての実装を行う。expNeededが次のレベルに必要な経験値、receivedが現在の経験値を表している。このとき、次のレベルになるのに必要な経験値を返せ。

例えばexpNeededに[100,300,600](単調増加と仮定してよい)という配列の値が入っていて、receivedに320と入っていたら、600-320=280を返せということになる。receivedが300なら600-300=300になる。

実装したコードは以下の通り。

public class LevelUp{
 public static int toNextLevel(int[] expNeeded, int received){
  int i;
  int idx=0;
  for( i=0 ; i< expNeeded.length ; i++ ){
   if(received < expNeeded[i] ){
    return expNeeded[i]-received;
   }
  }
  return 0;
 }
}

点数は184.09/250といまいち。簡潔な解法を思いつくのに時間がかかってしまった。