TopCoder SRM338 Div2 250Pts

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

賭けの戦略として以下のことを考えている。最初の勝負では1ドル賭ける。もし賭けにかてば、1ドルを得て、次の勝負では1ドルかける。負けた場合は、1ドルを失って次の勝負で2ドルを書ける(少なくとも手元に2ドル持っているものとする)。もし勝てば2ドルを得て、3回目の勝負では1ドルを賭ける。これでも負ければ2ドルを失い、3回目の勝負では4ドルを賭ける(少なくとも手元に4ドル持っているものとする)。つまり、負けたときは、いつでも次の勝負では掛け金を倍にするということである。勝ったときは1ドルを次の勝負で賭けることになる。

問題ではinitSumという最初の所持金が与えられる。またoutcomeという文字列が与えられる。outcomeのi番目の文字はW(勝利)またはL(敗北)で与えられる。文字はi番目の勝負の結果を表している。すべての勝負を終えた後の残っている金額を返せ。もし、次に賭けようとした額が賭けられない場合は、そこでやめ、そのときに持っているお金の額を返せ。

例えば10ドル手元にあって、勝ち、負け、負け、勝ちの場合は10+1-1-2+4=12ドルとなる。

私の解答はこちら。

public class BettingStrategy {

 public int finalSum(int initSum, String outcome) {
  int nBet = 1;
  int nMoney = initSum;
  for( int i=0 ; i<outcome.length() ; i++ ){
   if( nMoney < nBet ){
    break; // これ以上賭けられない
   }
   if( outcome.charAt(i) == 'W' ){
    nMoney += nBet;
    nBet = 1;
   }else{
    nMoney -= nBet;
    nBet *= 2;
   }
  }
  return nMoney;
 }

}

得点は240.50。

TopCoder SRM337 Div2 250Pts

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

回文というのは、文字を右から読んでも左から読んでも同じになる文字列を指す。sという文字列が与えられたとき、sを最小限変えることで回文を作成せよ。文字を変えるというのは、ある場所の文字を置き換えるということである。文字を削ることや付け加えることは認められていない。もし回答が複数あるなら、アルファベット順で最も早く来る物を返せ。

私の解答はこちら。

public class Palindromize2 {

 public String minChanges(String s) {
  StringBuffer sb = new StringBuffer();
  for( int i=0 ; i<s.length(); i++ ){
   // headとtailから順にi番目を比較して、先に来る方をcとする
   char h = s.charAt(i);
   char t = s.charAt(s.length()-i-1);
   char c = h > t ? t : h;
   sb.append(c);
  }
  return sb.toString();
 }

}

得点は236.12/250、中央値は約228点。実は文字の交換回数が最小とかは関係ないというオチ。

バームクーヘン型積分

よくある1変数積分の問題に、ある関数で囲まれる面をy軸の周りに1回転させてできる体積を求めよというものがあります。そのような問題を解く際に用いられる手法としてバームクーヘン型積分というものが知られています。バームクーヘン(ドイツ語で木のケーキという意味です)の形状は軸の周りに線が入っているのが特徴です。バームクーヘン型積分というのは、その線を一つ一つかき集めて体積とみなす計算方法です。

具体的にy=f(x) (0<=x<=a)という形が与えられていると、この曲線とx軸で囲まれた面をy軸回りで1回転させたときの体積は次式のようになります。

2*PI*x*yというのは、底面の半径がx、高さがf(x)の円柱の側面積に相当します。側面積をxが0からaまでの範囲で集まると先述のように体積となるわけです。

余談ですが、この問題は東大が大学受験の問題として出したのがきっかけで広まったそうです。

TopCoder SRM336 Div2 250Pts

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

Pig Latinというのは、文字を暗号化する簡単な手法である。我々は"Vowel Latin"という手法を開発した。これは単語から母音を除去し、その除去した順を維持したまま後ろに除去した文字をつけるという手法である。母音というのは"a"、"i"、"u"、"e"、"o"とその大文字である。並べ替えたことによって、大文字・小文字が変わるということはない。VowelLatinという文字列wordを与えたときに、その単語をVowel Latinという手法で暗号化したときの単語を返すメソッドを作成せよ。

私の解答はこちら。

public class VowelLatin {

 public String translate(String word) {
  char[] vowels = {'a', 'i', 'u', 'e', 'o', 'A', 'I', 'U', 'E', 'O'};
  StringBuffer sb = new StringBuffer();
  StringBuffer ret = new StringBuffer();
  for( int i=0; i<word.length() ; i++ ){
   char c = word.charAt(i);
   boolean isVowel = false;
   for( int j=0 ; j<vowels.length ; j++ ){
    if( c == vowels[j] ){
     isVowel = true;
     sb.append(c);
     break;
    }
   }
   if( isVowel == false ){
    ret.append(c);
   }
  }
  return ret.toString() + sb.toString();
 }
 /*
 // cが母音か否かの判定は、これで綺麗に書ける
 boolean isVowel(char c){
  return "aiueoAIUEO".indexOf(c) >= 0;
 }
 */
}

得点は245.64/250、中央値は約232点。最後に書いたコメントの方が母音かそうでないかの判定ロジックがすっきりしますね。上のコードはC言語の癖がついて取れていないだけです ^^;

TopCoder SRM335 Div2 250Pts

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

回文というのは、右から読んでも左から読んでも同じになるものである。sという文字列が与えられたとき、sの右に0文字以上の文字を最小限足すことで得られる、もっとも短い回文を返せ。これは唯一に定められる。

私の解答はこちら。

public class Palindromize {

 public String minAdds(String s) {
  StringBuffer sb = new StringBuffer(s); // 文字列の反転にStringBuffer
  String rev = sb.reverse().toString();
  int idx = 0;
  int len = s.length();
  for( int i=0 ; i<len ; i++ ){
   String s1 = s.substring(i);
   String s2 = rev.substring(0, len-i);
   System.out.println("---");
   System.out.println(s1);
   System.out.println(s2);
   if( s1.equals(s2) ){
    return s + rev.substring(len-i);
   }
  }
  return null;
 }

}

得点は177.51/250、中央値は約164点。元の文字列の後ろn文字ととひっくり返した文字列の先頭n文字をnが小さくなる方向に探索していけばよいというだけなのだが、それに気付くのに思いのほか手間取った。

TopCoder SRM334 Div2 250Pts

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

3人の女の子がスーパーで買い物をしている。スーパーは1回のお買いもので$50以上の買い物をすると$10引くというセールを行っている。女の子たちは買うものをまとめれば、個別に買うよりも安く買えるということに気付いた。例えば、$46、$62、$9の品物を買うとすれば、$62、$46と$9の組合せによって、$20値引くことができる。goods[]という女の子たちがそれぞれ買った品物の合計額が入った整数型の配列が与えられる(3人なので要素数は3)。このとき、すべての品物を買うのに必要な最低費用を返せ。女の子たちは喜んで先述のように買い物をまとめようとするし、またどの子も買うものを分割するようなことはしないものとする。

私の解答はこちら。

import java.util.Arrays;

public class SupermarketDiscount {

 public int minAmount(int[] goods) {
  int nCosts = 0;
  int idx;
  Arrays.sort(goods);
  // $50以上のものはそれ単体で値引く
  for( idx=goods.length-1 ; idx>=0 ; idx-- ){
   if( goods[idx] >= 50 ){
    nCosts += goods[idx]-10;
   }else{
    break;
   }
  }
  int nTotal = 0;
  // 合わせて50を超えるようなことがあれば値引く
  for( int i=idx ; i>=0 ; i-- ){
   nTotal += goods[i];
   if( nTotal >= 50 ){
    nCosts += nTotal - 10;
    nTotal = 0;
   }
  }
  nCosts += nTotal;
  return nCosts;
 }

}

得点は228.21/250、中央値は約203点。結局面倒な実装はしなくても、先頭から順番に数えて$50を超えた時点で値引くということにすればOKということのようだった。気付けばなんてことのない実装になる。

TopCoder SRM333 Div2 250Pts

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

チェスの盤面の模様は以下の条件を満たす。

• 模様は長方形である。
• 模様は"."と"X"のみからなる。
• どの二つの隣り合う模様も、水平方向、垂直方向に同じではない
• 模様の左下は"."である。

作成するメソッドの引数には、rowsとcolumnsという二つの整数が与えられる。rowsとcolumnsという次元を持つ盤面を計算し、それを文字列型配列として返せ。返り値の要素は模様の行方向に対応する。特に、最後の要素の先頭は盤面の左下を指すものとする。

私の解答はこちら。

public class ChessboardPattern {

 public String[] makeChessboard(int rows, int columns) {
  String[] ret = new String[rows];
  String[] pat = {"", ""}; // Arrays.fill(pat,"")と書いてもいいですね
  for( int i=0 ; i<columns ; i++ ){ // 行方向の2パターンを生成
   if( i % 2 == 0 ){
    pat[0] += ".";
    pat[1] += "X";
   }else{
    pat[0] += "X";
    pat[1] += ".";
   }
  }
  for( int i=0 ; i<rows ; i++ ){ // 行番号に応じてパターンをセット
   if( i % 2 == 0 ){
    ret[rows-i-1] = pat[0];
   }else{
    ret[rows-i-1] = pat[1];
   }
  }
  return ret;
 }

}

得点は235.38/250、中央値は約222点。最後の要素が左下になるということをどう表現するかという点が一番難しいが、比較的簡単な部類の問題。

TopCoder SRM332 Div2 250Pts

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

単語は連続するアルファベットの最大長である。単語は空白、数字、句読点によって分けられる。単語の平均長とは、全単語の長さの合計を単語数で割ったものである。textという文字列が与えられたとき、単語の平均長を返せ。もし、単語が無いようであれば、0.0を返すようにせよ。

私の解答はこちら。

public class TextStatistics {

 public double averageLength(String text) {
  String[] words = text.split("[ 0-9.,?!-]");
  int nWords = words.length;
  int nAlpha = 0; // アルファベットの数をカウント
  int nBlank = 0; // words中の""をカウント
  for( int i=0 ; i<words.length ; i++ ){
   if( words[i].equals("") ){
    nBlank++;
    continue;
   }
   for( int j=0 ; j<words[i].length() ; j++ ){
    char c = words[i].charAt(j); // cは2回評価するので変数にしておく
    if(  Character.isLowerCase(c) || Character.isUpperCase(c) ){
     nAlpha++;
    }else{
     break;
    }
   }
  }
  if( nWords == nBlank ) return 0.0; // wordsが全部空白だった場合は0.0
  return (double)nAlpha/(nWords-nBlank);
 }

}

得点は112/250。当初、区切り文字(words)の設定が空白だけでよいと思っていたので、そこで複数回提出になってしまった。

TopCoder SRM331 Div2 250Pts

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

サンタクロースが、今年もプレゼントを袋一杯にしてやってきた。N人の子供たちは一列に並び、プレゼントがもらえることを待ち遠しくおもっている。サンタクロースは袋からプレゼントを取り出して、列の先頭にいる子供にそれを渡す。プレゼントをもらった子供はもらったプレゼントが4つにならないうちは列の最後尾に行く。4つの場合は家に帰る。これを列の子供とプレゼントが残っている間繰り返す。

gifts[]というサンタの袋に入っているプレゼントの文字列があり、その配列の順序でサンタはプレゼントを渡す。k番目の要素がk番目に並んだ子供の受け取ったプレゼントを表すN個の文字列型配列を返せ。プレゼント名はもらった順にならべ、それらの文字は半角スペース1つで区切られる。なお、0番目の子供は初期状態で、列の先頭に並んでいた子供、1番目はその次に並んでいた子供を表す。

私の解答はこちら。

public class SantaGifts {

 public String[] distribute(String[] gifts, int N) {
  String[] ret = new String[N];
  // Arrays.fill(ret,"");としても良い
  for( int i=0 ; i<ret.length ; i++ ){
   ret[i] = "";
  }
  int nGift = Math.min(N*4, gifts.length);
  for( int i=0 ; i<nGift ; i++ ){
   if( i >= N ) ret[i%N] += " ";
   ret[i%N] += gifts[i];
  }
  return ret;
 }

}

得点は238.51。文字型配列の初期化方法はArras.fillが私の解答よりエレガントですね。

TopCoder SRM330 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

異なった数値からなる数列のsortnessというのは、各要素のsortnessの平均である。各要素のsortnessというのは、ある要素の前にそれより前に現れた大きな数と、それよりあとに現れた小さな数の出現回数である。sortnessが小さくなるにつれ、ソート済みの数列に近くなる。ソートされた数列ではsortnessは0になる。例えば{3,2,1,4}では、sortnessは(2+1+2+0)/4=1.25となる。各要素が異なる数からなる整数型の数列a[]が与えられたとき、aのsortnessを計算して返せ。

私の解答はこちら。

public class Sortness {

 public double getSortness(int[] a) {
  int nSortness = 0;
  for( int i=0 ; i<a.length ; i++ ){
   for( int j=0 ; j<a.length ; j++ ){
    if( i == j ){
     continue;
    }else if( i < j ){
     if( a[j] < a[i] ) nSortness++;
    }else{
     if( a[j] > a[i] ) nSortness++;
    }
   }
  }
  return (double)nSortness/a.length;
 }

}

得点は242.19/250、中央値は約234点。

TopCoder SRM329 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

text[]という各要素が1単語からなる文字列型の配列が与えられる。母音(a,i,u,e,o)をすべてtextから取り除き少なくとも一つは母音でない文字が残るように暗号化する。もし、単語が母音のみからなる場合は、そのままにしておく。i番目の要素がtext[i]を暗号化した結果になる文字列型の配列を返すようなメソッドを作成せよ。

なおtext[]を構成する文字は小文字のアルファベットのみからなるものとする。

私の解答はこちら。

public class VowelEncryptor {

 public String[] encrypt(String[] text) {
  for( int i=0 ; i<text.length ; i++ ){
   StringBuffer sb = new StringBuffer();
   boolean isAllVowels = true;
   for( int j=0 ; j<text[i].length() ; j++ ){
    char c = text[i].charAt(j);
    if( c != 'a' && c != 'i' && c != 'u' && c != 'e' && c != 'o' ){
     isAllVowels = false; // text[i]はすべて母音ではなかった
     sb.append(c);
    }
   }
   // すべて母音でなければ、得られた子音のみの文字列をtext[i]に代入
   // 逆にすべて母音なら処理はしない
   if( isAllVowels == false ){
    text[i] = sb.toString();
   }
  }
  return text;
 }

}

得点は239.98/250、中央値は約215点。

2012年1月の学習記録

2012年1月に学習した主な本一覧。

高専の数学3(pp.71～109)

重積分まで読了。残りは微分方程式。

UNIX/Solarisアソシエイツ(pp.146～読了)

エンドユーザなら価値があるかも。Solarisのシェアは今後上がるのかな...?

大学生の微積分(pp.55～102)

意外と忘れていることが多いことに気付く。極座標系における面積計算(要は積分)とか。

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

ひたすら演習。

TopCoder SRM328 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

さまざまな色からなる数珠状のネックレスについて考える。色はアルファベットの大文字1字で表される。すると、ネックレスは以下のような文字列で記述することができる。つまり、ある珠から始め、時計回り、あるいは反時計回りで辿った順序を用いて、現れた色の順序によって文字列が作成されるということである。明らかに同じネックレスは複数の表現方法がある。例えば"CDAB"は"DABC"などと同じになる。さて、necklaceというネックレスを表す1つの文字列が与えられたときに、辞書式順序でもっとも最初に来るneckleceと同じネックレスの表現を返すメソッドを作成せよ。例えば、"CDAB"であれば"ABCD"がもっとも最初に来ることになる。

私の解答はこちら。

import java.util.ArrayList;
import java.util.Collections;

public class MarbleNecklace {

 public String normalize(String necklace) {
  String rep = necklace + necklace;
  ArrayList<String> aList = new ArrayList<String>();
  for( int i=0 ; i<necklace.length() ; i++ ){
   String s = rep.substring(i, i+necklace.length());
   aList.add(s);
   s = rep.substring(rep.length()-i-necklace.length(), rep.length()-i);
   StringBuffer sb = new StringBuffer(s);
   aList.add(sb.reverse().toString());
  }
  Collections.sort(aList);
  return aList.get(0);
 }

}

得点は202.50/250、中央値は約193点。いったん2倍の文字列にし、時計回りと反時計周りを同時にリストに入れ、最後にリストをソートして先頭の要素を取り出せばよい。Collections.sortは、コレクションを自然な順序で並べ替えてくれるので、文字列型のデータが入ったArrayListのソートであれば、辞書式順序で並べ替えてくれることになる。この性質より、先頭のものを取り出せば、答えになる。

TopCoder SRM327 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

文字列がfenceと呼ばれるのは"|"と"-"が交互に来るときである。sという"|"と"-"からなる文字列が与えられたとき、s中の部分文字列でfenceの最大長さになるものを見つけ、その長さを求めよ。

私の解答はこちら。

public class FunnyFence {

 public int getLength(String s) {
  int maxlen = 0;
  int len = 0;
  char prev = 'a'; // ダミーの文字
  for( int i=0 ; i<s.length() ; i++ ){
   char cur = s.charAt(i);
   if( prev != cur ){ // 直前の文字と違えばfenceの長さに1加える
    len++;
   }else{ // 直前の文字と同じならfence=1として再探索
    len = 1;
   }
   prev = cur;
   maxlen = Math.max(maxlen, len);
  }
  return maxlen;
 }

}

得点は243.76/250、中央値は約222点。

TopCoder SRM326 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

00から99までの2桁の数ではじめる。二つの桁の数字を足す。次に、元の数字の右側の桁と二つの数字を足した結果の右側の桁をくっつける。この操作を繰り返すと、やがて元の数字に戻る。nという00以上99以下の数字が与えられたとき、元の数字に戻るまでに先述の操作を何回繰り返したかを返すメソッドを作成せよ。

私の解答はこちら。

public class AdditionCycles {

 public int cycleLength(int n) {
  int nStep = 0;
  int tmp = n;
  while( true ){
   int d1 = tmp / 10;
   int d2 = tmp % 10;
   tmp = d2 * 10 + (d1 + d2) % 10;
   nStep++;
   if( n == tmp ){
    break;
   }
  }
  return nStep;
 }

}

得点は245.10/250、中央値は約226点。

TopCoder SRM325 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

ある会社では、労働者は毎月、最初の200時間の労働では1時間当たりP1ドル受け取る。200時間を超えた残りの労働時間では1時間あたりP2ドルを受け取る。この労働者がsalaryという給料を受け取るために、最小限働かなければならない時間は何時間かを実数型で計算して返せ。

私の解答はこちら。

public class SalaryCalculator {

 public double calcHours(int P1, int P2, int salary) {
  if( P1 * 200 >= salary ){
   return (double)salary/P1;
  }
  salary -= P1*200;
  return (double)salary/P2+200;
 }

}

得点は241.88/250、中央値は約217点。