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