TopCoder SRM210 Div2 250Pts

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

よくある文章の処理に、単語の先頭を大文字にするというものがある。titleという文章が与えられたときに、単語の先頭を大文字に変換して返すメソッドtoFirstUpperCaseを作成せよ。単語の区切りは1つ以上のスペースからなるものとする。また、入力の文字は空白の他はa-zという小文字のアルファベットのみかななるものとする。

私の解答は以下の通り。

public class TitleString {
 public String toFirstUpperCase(String title) {
  StringBuffer sb = new StringBuffer();
  boolean isspace = true;
  for( int i=0 ; i<title.length() ; i++ ){
   if( title.charAt(i) == ' ' ){ // i番目の文字は空白
   isspace = true; // 直前の文字が空白であることを示すフラグ
   sb.append(" ");
   }else if( title.charAt(i) != ' ' && isspace == true ){
    // i番目の文字が空白でなく、直前の文字が空白である場合
    isspace = false;
    sb.append(title.substring(i,i+1).toUpperCase());
   }else{
    // 直前は空白ではなく、i番目も空白でない文字の場合は、小文字はそのまま処理する
    sb.append(title.substring(i,i+1));
   }
  }
  return sb.toString();
 }
}

得点は219.34/250。中央値は約211点、正解率約90%。toUpperCaseメソッドの適用方法に手間取って、ややスコアは低めとなった。

TopCoder SRM208 Div2 250Pts

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

ディザリングについて。ディザリングというのは、見かけの色数よりも少ない色数で画像を構成することである。使える色が限られた環境で用いられる技術である。チェスの盤目のように白と黒を配置してグレーに見せるのが代表的な例である(Faxを思い浮かべるとよいかも)。

さて、あなたは、あるディザリングに用いられている色を数えるプログラムを書くことになった。スクリーンの各画素の色情報(文字列型配列で表されている)と、ディザリングに用いられている色の一覧が与えられたとき、スクリーン中に、ディザリングに用いられている色が用いられている画素数を返すメソッドを作成せよ。スクリーンはscreen[](1つの配列がスクリーンの1行を表していると思え)、ディザリングに用いられる色はditheredで与えられている。ditheredの一部に該当する文字がscreen[]中に登場したら、その文字はディザリングされている画素である。

私の解答は以下の通り。原始的ではあるが、1文字ずつ比較していくという方法をとっている。

public class ImageDithering {
 public int count(String dithered, String[] screen) {
  int cnt = 0;
  for( int i=0 ; i<dithered.length() ; i++ ){
   for( int j=0 ; j<screen.length ; j++ ){
    for( int k=0 ; k<screen[j].length() ; k++ ){
     if( screen[j].charAt(k) == dithered.charAt(i) ) cnt++;
    }
   }
  }
  return cnt;
 }
}

得点は246.60/250。中央値は約228点、正解率は97%台であった。この問題はSRM208以前のSRMでも出題されていて、Javaを習い始めた当時は、charAtやlengthメソッドが分からなくて苦労したが、今回はあっさり解くことができた。

NLTK導入メモ

Windows上でPythonを利用してNLTK(Natural Language ToolKitの略)を動作させるために行うべき手順についての覚書。NLTKというのは、自然言語処理のためのライブラリです。

1. Pythonのインストール
   
   • バージョンは2.xを用いるようにしましょう。NLTKは3.x系に対応しているという情報は公式サイトにはありませんでした。ダウンロード先はこちら(Python Japan User's Group)から2.6.6のインストーラを使うことにしましょう。私は2.6.5を使っていますが(汗
     
   • インストール先はデフォルト(C:/Python26)でよいかと思います。
     
   • 環境変数の登録も忘れずに。環境変数の登録はスタート->マイコンピュータを右クリック->プロパティ->詳細設定タブ->環境変数ボタンと進めれば設定画面に移動できます。
     
   • 環境変数PathにC:/Python26を追加しましょう。システムでもユーザでもどちらでも良いかと思います。Pathが無ければ追加して作成してください。
     
2. NLTKダウンロードページより、NLTKと連動するツールをダウンロードしましょう。以下のツールをダウンロード、インストールします。インストールはすべて、デフォルトの設定で問題ないです。勝手にC:/Python26を見つけてその下にいろいろとインストールしてくれます。少なくともPyYAML、NLTKをインストールする必要があります。他にもグラフを描く関数が呼べないと困りますので、matplotlibとNumPyを入れておくのがよいかと思います。
   
   • PyYAML
     
   • NLTK
     
   • NumPy（Pythonの数学関数ライブラリ）
     
   • matplotlib（グラフ描画のためのライブラリである。NumPyとも連動する箇所があるらしい。）
     
3. NLTKのデータを入れる
   
   • NLTKでいろいろ試したいという場合に、サンプルデータを利用することができます。
     
   • pythonを立ち上げて、次のようにコマンドを打ち込みます。
     

     >>> import nltk
     >>> nltk.download()

     現れた画面で、bookを選択してダウンロードしましょう(画面は既にインストール済みになっていますが...)。私の場合、テキストファイルの保存先はそのままで試しています。
     
     
4. NLTKの簡単な動作確認
   
   • 以上でインストール関連の作業は終了したので、動作確認をしましょう。
     

     >>> from nltk.book import * # サンプルテキストの読み込み
     *** Introductory Examples for the NLTK Book ***
     Loading text1, ..., text9 and sent1, ..., sent9
     Type the name of the text or sentence to view it.
     Type: 'texts()' or 'sents()' to list the materials.
     text1: Moby Dick by Herman Melville 1851
     text2: Sense and Sensibility by Jane Austen 1811
     text3: The Book of Genesis
     text4: Inaugural Address Corpus
     text5: Chat Corpus
     text6: Monty Python and the Holy Grail
     text7: Wall Street Journal
     text8: Personals Corpus
     text9: The Man Who Was Thursday by G . K . Chesterton 1908
     >>> len(text1) # text1の単語数を確認
     260819
     

   ここまでできれば、NLTKを用いた自然言語処理が始められるようです。Hello, NLP world!

TopCoder SRM209 Div2 250Pts

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

問題について説明する。時間のn-移動平均を計算する。n-移動平均とは連続するn個のデータの平均である。連続するデータに対し、1番目からn番目までの平均、2番目から(n+1)番目までの平均、3番目から(n+2)番目までの平均と計算していくことで計算される。今、平均を計算する際に対象とするべきデータ数nと、"hh:mm:ss"(hh時mm分ss秒)というフォーマットからなる文字列型の配列times[]が与えられたときに、時間の秒数のn-移動平均を計算するメソッドを作成せよ。ただしnはtimesの長さ以下である。また、hhは00～23、mmは00～59、ssは00～59であり、timesの要素数は1以上50以下である。また、移動平均の秒数は小数点以下は切り捨てるものとする。

私の解答はこちら。

public class MovingAverages {
 public int[] calculate(String[] times, int n) {
  int[] ret = new int[times.length-n+1];
  int[] seconds = new int[times.length];
  // hh:mm:ssのフォーマットをすべて秒数に変換する
  for( int i=0 ; i<times.length ; i++ ){
   String[] t = times[i].split(":");
   seconds[i] = Integer.parseInt(t[0])*3600+Integer.parseInt(t[1])*60+Integer.parseInt(t[2]);
  }
  // 上で得られた秒数に対して、移動平均の計算
  for( int i=0 ; i<ret.length ; i++ ){
   for( int j=0 ; j<n ; j++ ){
    ret[i] += seconds[i+j];
   }
   ret[i] /= n;
  }
  return ret;
 }

}

得点は228.35/250。中央値は約132点。正解率は約95.8%。秒数の変換で迷うことが無かったので、中央値よりもかなり高速に実装ができた。

TopCoder SRM207 Div2 250Pts

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

あなたは公共交通機関の勉強をしており、ある道を毎分何台のバスが通っているかを知りたい。そこで、車でその道を通り、何台のバスに出会うか、もしくは追い越したかということを数えたい。ここでは、仮定として道は直線で、バスはすべて車と同じ方向に走るものとする。

車の速さをspped(単位はメートル/秒)、車が動き出す瞬間にi番目のがバス何メートル先にいるかを表すpositions[]、i番目のバスの速さvelocities[](単位はメートル/秒)、計測期間timeが与えられたときに、t計測時間中に何台のバスに出会うかを返すメソッドを作成せよ。ただし、最初同じ位置にいるバスは出会ったとするようにせよ。

私の解答はこちら。

public class TransportCounting {
 public int countBuses(int speed, int[] positions, int[] velocities, int time) {
  int met = 0;
  for( int i=0 ; i<positions.length ; i++ ){
   if( positions[i] == 0 ) met++; // 最初の位置が同じ
   else if( speed*time >= positions[i]+velocities[i]*time ) met++; // 途中で追いついた
  }
  return met;
 }

}

得点は242.79/250。中央値は172点程度。最初の位置が同じということを明示的に条件に加えないと間違いになる(最初のif文のこと)。例えば、最初同じ位置で測定を開始し、バスの方が車よりも速い場合、車とバスは以後出会わなくなるので、カウントに失敗するのである。

Javaの私的まとめ3

Javaのお勉強その3

1. データ型
   

   基本データ型と、参照型の2種類がある。
   

   参照型はクラス、インタフェース、配列変数であり、それ以外(int型など)は基本データ型になる。
   

   String型(参照型)は特殊で、いったん生成すると、内部状態を変更することはできない。以下のようにしても、s2の値自体はabcのままである。
   

   String s1 = "abc";
   String s2 = s1;
   s1 = "cba";

2. 配列
   

   C言語とは異なり、定義する際に左辺に要素数を書くことはない。
   

   int[] array = new int[5]; // 0で全部初期化される
   int[] array = {1,2,3}; // 要素数3で、内容を1,2,3で初期化
   int array[] = {1,3,4}; // []は後ろに書いてもよい
   int[][] array2d = new int[3][5]; // 2次元配列の定義
   int[][] array2d = {{1,2,3},{4,5},{6,7,8,9,10}}; // 各配列の中身は要素数は一定でなくても良い

   初期化する際に、整数や実数変数は0、boolean型変数はfalse、参照型変数はnullで初期化される。
   

   整数型配列は参照型であるが、配列の要素自体は基本データ型になる。
   

   参照型の配列は
   

   myClass[] myclass = new myClass[5];

   としただけでは、配列オブジェクトが生成されるだけで、各要素はnullのままである。myclass[0] = new myClass();のようにしてから利用可能になる。上で書いたように、変数宣言と、オブジェクトの生成を同時に行うこともできる。
   

   myClass[] myclass = {new myClass(),new myClass()};

3. 引数
   

   メソッドに渡される引数はコピーされるので、呼んだメソッドで値を変更しても、オリジナルの値は変更されない。参照型、基本データ型のどちらの引数でもこの性質は同じ。
   

   参照型変数は、オブジェクトを指すものであり、コピーされると、同じオブジェクトを指していることになる。したがって、指しているオブジェクトの内容を変更することができる。
   

   引数にfinalを付けると、その引数はメソッド内でfinalになる。引数が参照型変数であった場合、オブジェクトは変更できないが、オブジェクトの値自体は変更可能である。
   

4. ガーベージコレクション
   

   参照されなくなったオブジェクトは自動的に破棄されるが、このことをガーベージコレクションという。
   

   System.gc();、Runtime.getRuntime().gc();とすると、ガーベージコレクションを促すことができる。あくまでも促すだけであることに注意。
   

   Objectクラスにはfinalize()というメソッドが定義されており、このメソッドをオーバーライドすることで、ガーベージコレクションの前に、その内容を実行するようになる。メモリ以外のリソースの回収などに用いられる。
   

Javaの私的まとめ2

Javaのお勉強その2

1. 演算子
   

   &&と&の違いは、&&は左オペランドがfalseなら右オペランドは評価しないのに対し、&は必ず左右のオペランドを評価しているという点である。||と|の違いも同様。
   

   -5%-3は5%3=2(-を取り除いて余りを計算する)としたあとに左オペランドの符号をつける。したがって-5%-3=-2になる。
   

   整数同士の割り算は整数になる。小数点以下は切り捨てられる。例えば、6/4=1になる。
   

   0で割る、または0で剰余を計算するとArithmeticExceptionがスローされる。
   

   instanceof演算子はオブジェクトがあるオブジェクトが特定のクラスを含んでいるか判定するのに用いられる。a instanceof bと書けば、aがbにキャストできるか否か判定すると言ってもよい。
   

2. リテラル
   

   long値には数字の後ろにLまたはlを付ける。
   

   実数をfloatとして扱いたい場合は数字の後ろにFまたはfをつける。
   

   文字リテラルは、''で囲う。'\uに続けて4桁の16進数を書き込む。'\n'(改行の値)という書き方もアリ。
   

   文字列リテラルは、Stringオブジェクトである。同じ文字列のリテラルがあったとすれば、それらは同じStringオブジェクトになる。
   

3. ==とequalsの違い
   

   ==は同じオブジェクトか否かを判定する。equalsはオブジェクトの中身(値)が等しいか否かを判定している。
   

   Objectクラスでは==とequalsメソッドに違いはないが、Stringクラスではequalメソッドがオーバーライドされているため、意味が異なる。Stringクラスのequalメソッドは文字列として単に等しいかを判定している。オブジェクトが等しいかまでは見ていない。
   

TopCoder SRM206 Div2 250Pts

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

「10進数の正の整数nが与えられたとき、2進数表記したときに何ビット必要になるかを返すメソッドを作成せよ。」というのが問題である。

私の解答はこちら。

public class Bits {
 public int minBits(int n) {
  int digits = 0;
  while( n >= 1 ){ // 繰り返し2で割って、桁数を判断
   digits++;
   n /= 2;
  }
  return digits;
 }
}

得点は248.09/250。全体の中央値がおよそ244点という易問。ちなみに、この問題はJavaであれば、ワンライナーで書ける。以下がその解答である。

public class Bits {
 public int minBits(int n) {
    return Integer.toBinaryString(n).length();
 }
}

TopCoder SRM205 Div2 250Pts

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

問題について説明する。ある国の子供が受けた数学と言語の試験結果のリストを受け取った。点数が入った配列math[]とverbal[]が与えられたとき、2科目の平均が、全体の平均点に満たない子供の数を返すメソッドを作成せよ。ただし、配列のi番目は子供iの結果を表す。また、受験した子供の人数は、配列の長さで表される。もちろんmath[]とverbal[]の長さは等しい。

私の解答はこちら。

public class Average {

 public int belowAvg(int[] math, int[] verbal) {
  double ave = 0.0;
  for( int i=0 ; i<math.length ; i++ ){
   ave += (math[i]+verbal[i]);
  }
  ave /= math.length*2;
  int belown = 0;
  for( int i=0 ; i<math.length ; i++ ){
   double tmp = (math[i]+verbal[i])/2.0;
   if( tmp < ave ) belown++;
  }
  return belown;
 }
}

得点は、244.74/250。全体の平均を計算したのちに、一人ずつ下回っているか判定するということを実装しておしまい。

Javaの私的まとめ1

オラクルのJavaプログラマ資格取得のために、勉強を開始した。特にアクセス修飾子が頭に入っていないので、書いて覚える、見て覚えるを実践するために以下にまとめてみた。

1. 宣言
   

   プログラムはパッケージ宣言、インポート宣言、クラス・インタフェースの定義の順で書く。どれかが欠けててもコンパイル自体はできる(クラスがないとコンパイルしてもファイルはできないが)。
   

   パッケージとは、クラス・インタフェースをグループにまとめることである。ファイル中にpackage a;と宣言し、myclassというクラスを用意すると、a.myclassという完全修飾名が得られる。package宣言は1ファイルにつき、1つだけ許されている。
   

2. 識別子
   

   使える識別子は先頭が$、_、英字のみ。キーワード（publicとか）やリテラル（ソース内の値の表現0x10などの数値表現）は識別子として利用できない。
   

3. 基本データ型
   

   Javaの基本データ型は符号付き（C言語でいうとunsignedが"つかない"もの）である。基本データ型はboolean、byte(-128～127)、char、short、int、long、float、doubleがある。charのみ数値と見れば、符号なし整数とみなすことができる。
   

4. 修飾子
   

   修飾子は矛盾しない場合は、いくつつけても良い。何につけるかによって、使えるものや意味が異なる。
   

   クラス修飾子は4種類ある。
   

   クラス修飾子	意味
   public	どこからでもアクセス可能
   abstract	抽象クラス（定義が不完全）
   final	サブクラスを持てないクラス
   strictfp	IEEE754の仕様に沿った浮動小数点の計算を行う

   フィールド（クラスが持つ変数）の修飾子は4種類ある。
   

   フィールド修飾子	意味
   final	値をいったん定義すると変更できない
   static	クラスに付随する変数にする（複数のインスタンスで共有）
   transient	シリアライズのときに保存しない。シリアライズというのは、メモリ上のバイトデータを読み書きできるよう変換するすること。
   volatile	コンパイラの最適化を行わない

   インタフェースは2種類の修飾子が利用できる。
   

   インタフェース修飾子	意味
   public
   abstract

   メソッド（クラス内の関数）の修飾子は5種類ある。
   

   メソッド修飾子	意味
   abstract	抽象メソッド（定義のないメソッド）
   final	サブクラスで変更不可のメソッド
   static	クラスに付随するメソッドにする(インスタンスに付随させない)
   synchronized	実行前にロックを取得する
   native	プラットフォーム依存のコードで定義が書かれる。nativeと書かれたメソッドは、Java以外の言語で実装され、コンパイルされていることを示している。

   コンストラクタの修飾子は3種類(何もつけないデフォルトの状態を含めると4種類)
   

   コンストラクタ修飾子	意味
   public	どこからでもアクセスできる
   protected	同じパッケージ内のすべてからと、他のパッケージでも、そのクラスのサブクラスからのアクセスを許可する
   private	そのクラスの内部からのみアクセスできる
   デフォルト(何もつけない)	同じパッケージ内からのアクセスを許可する

5. 静的インポート宣言
   

   静的インポート宣言は、staticなフィールドの修飾部分を省略するために用いられる。例えば、
   

   import static java.lang.Math.PI;
   import static java.lang.System.out;

   とすれば、プログラム中でPI、outのように省略して書くことができる。

   import static java.lang.Math.*;

   とすれば、Mathクラスのすべてのメソッドを省略して用いることができるが、修飾部分を除いて同じ名前のものがあるとコンパイルエラーになってしまうことには注意。

6. アプレット
   アプレットとは、ブラウザ内で実行されるプログラムである。ブラウザ内のJava仮想マシンがjava.applet.Appletのサブクラスのインスタンスを生成し、実行する。
   

TopCoder SRM204 Div2 250Pts

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

問題について説明する。Mediciというボードゲームがある。このゲームでは各プレーヤーはfame、fortune、secretsという3つのパラメータを稼ぎ、最終的に3つの最小値が最大になったプレーヤーが勝利するということになっている。fame、fortune、secretsの配列を引数に与える。配列のi番目はプレーヤーiを表すものとする。このとき、勝者の添え字を返すメソッドを作成せよ。但し、勝利するプレーヤーが複数存在する場合は、引き分け再試合ということで-1を返すようにせよ。

私の解答はこちら。

public class Medici {
 public int winner(int[] fame, int[] fortune, int[] secrets) {
  int min = -1;
  int idx = 0;
  int mins[] = new int[fame.length];
  for( int i=0 ; i<fame.length ; i++ ){
   int tmp = Math.min(fame[i], fortune[i]);
   tmp = Math.min(tmp,secrets[i]);
   mins[i] = tmp;
   if( min < tmp ){
    min = tmp;
    idx = i;
   }
  }
  int n = 0;
  for( int i=0 ; i<mins.length ; i++ ){
   if( min == mins[i] ) n++; // 既存の物に一致するとn>=1になる
  }
  if( n >= 2 ) return -1; // 2回以上全体の最小値が出現したら-1を返す
  return idx;
 }
}

得点は、241.81/250。正解率は約83.7%。もっと簡単に書いていたコードがあったので以下に紹介する。for文は一つで十分なのであった。

public class Medici {
 public int winner(int[] fame, int[] fortune, int[] secrets) {
  booleans tie = true;
  int max = -1;
  int best = -1;
  for( int i=0 ; i max ){
     max = min;
     best = i;
     tie = false;
    }else if( min == max ){ // 最小値が既存の数値に一致した場合
     tie = true;
    }
  }
  return tie == true ? -1 : best;
 }
}

TopCoder SRM203 Div2 250Pts

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

問題について説明する。ログイン名の登録について考える。新しくユーザ名を登録しようとしたときに、ユーザ名が既存のものとかぶってしまう可能性がある。そこで、後ろに数字を付けたユーザ名を登録者に提案することにするメソッドを作成する。後ろにつける数字は1から順につける。もし"abc"と登録しようとして、"abc","abc1"が存在していた場合は、"abc2"というユーザ名を返すようにする。

私の解答はこちら。

public class UserName {
 public String newMember(String[] existingNames, String newName) {
  int n = 0;
  boolean loop = false;
  StringBuffer sb = new StringBuffer(newName);
  while( true ){
   loop = false;
   for( int i=0 ; i<existingNames.length ; i++ ){
    if( existingNames[i].equals(sb.toString()) ){
     // 後ろにつける数値をインクリメントした後は、配列の先頭の方を再度見直さないとダメ。
     // フラグ変数(loop)を用意して、先頭からの探索を再実行するようにしている。
     n++;
     sb = new StringBuffer(newName + n);
     loop = true;
    }
   }
   if( loop == false ) break;
  }
  if( n == 0 ) return newName;
  return sb.toString();
 }
}

得点は210.49/250。全体の正解率は87%。後ろにつける数値をインクリメントするたびに、ループを先頭から実行しなおさないといけないことに気付くのに時間がかかった。その他、existingNames[i].equals(sb.toString())はtoString()を付けなかった(sbとしていた)ために、比較がうまくいかなかったというバグを出していた。StringBufferとStringではクラスがクラスが違うから、中身の文字列が同じであっても、オブジェクトとしては異なるものになっているということなのだろう。

TopCoder SRM202 Div2 250Pts

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

問題について説明する。letter-stringというのは、A-Z、a-zの52文字のアルファベットと"-"から成り立っている。letter-stringの長さは"-"を文字列から取り除いたものである。letter-stringである文字列型の配列sが与えられたときに、それらの文字列の長さを返すメソッドを作成せよ。

私の解答は以下の通り。"-"を空文字に置き換えて長さを足すという方針をとった。

public class LetterStrings {
 public int sum(String[] s) {
  int total = 0;
  for(int i=0 ; i<s.length ; i++){
   String ss = s[i].replaceAll("-","");
   total += ss.length();
  }
  return total;
 }
}

得点は247.79/250。正解率は約98%。全体の解答を見ていると、charAtメソッドを用いて、'-'でなければ長さを格納する変数に1ずつ値を加えるという方法をとっている人が多かった。中身を変えるのを嫌うのであれば、charAtを利用する方が賢明だろう。

TopCoder SRM201 Div2 250Pts

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

問題は、min以上max以下の整数で、整数factorで割り切れる数はいくつあるかを返すメソッドを作成せよというもの。もちろんmin<=maxの関係は成り立っている。

for文の例題みたいな問題ですが、解答はこちら。

public class Multiples {
 public int number(int min, int max, int factor) {
  int cnt=0;
  for( int i=min ; i<=max ; i++ ){
   if( i%factor == 0 ) cnt++;
  }
  return cnt;
 }
}

得点は249.37/250と過去最高。正解者の平均点も240点以上で簡単なはずなのに、正解率自体は約85%という不思議な問題。

TopCoder SRM200 Div2 250Pts

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

問題について説明する。

左から順に演算を行うという、通常の四則演算とは異なる演算を行う。つまり、3+5*7といえば、普通は5*7を優先し3+35=28とするが、今回は左にある3+5を優先し、8*7=56とする。さて、0-9の一桁の数字と+、-、*の演算子が交互に現れる文字列exprが与えられたときに、左から順に演算を行った結果を返すメソッドevaluateを作成せよ。

私の解答は以下の通り。

public class NoOrderOfOperations {

 public int evaluate(String expr) {
  int num = 0;
  int oldnum = Integer.parseInt(expr.substring(0,1)); // 先頭の数値
  char op = 'a'; // 初期化のためだけ...不格好だ
  boolean flg =true;
  for( int i=1 ; i<expr.length() ; i++){
   if( Character.isDigit(expr.charAt(i) ) ){
    num = Integer.parseInt(expr.substring(i,i+1));
    if( flg == false ){
     if( op == '+' ){
      oldnum += num;
     }else if( op == '-'){
      oldnum -= num;
     }else if( op == '*'){
      oldnum *= num;
     }
    }
    flg = true;
   }else if( expr.charAt(i) == '+' ){
    op = '+';
    flg = false;
   }else if( expr.charAt(i) == '-' ){
    op = '-';
    flg = false;
   }else if( expr.charAt(i) == '*' ){
    op = '*';
    flg = false;
   }
  }
  return oldnum;
 }

}

得点は136.96/250。正解率は約93%。最初は二桁の数値が入ったらなどと思い、面倒な実装をしていたが、問題文をよく読むと非常に単純だった。こうして勘違いのなごりがあるプログラムができた。

良い解答を見つけたので、写経しておく。上のようなフラグも不要であり、非常に見通しがよい。

public class NoOrderOfOperations {
 public int evaluate(String expr) {
  int val = expr.charAt(0)-'0';
  for( int i=0 ; i<expr.length() ; i++ ){
   if( expr.charAt(i)=='+' ){
    val += expr.charAt(i+1)-'0'; // 先の1文字をとってきて計算
   }else if( expr.charAt(i)=='-' ){
    val -= expr.charAt(i+1)-'0';
   }else if( expr.charAt(i)=='*' ){
    val *= expr.charAt(i+1)-'0';
   }
   // i番目の文字が数値である場合はif文の中に入らず、何もしない
  }
  return val;
 }
}

TopCoder SRM199 Div2 250Pts

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

問題について説明する。

文字列の掛け算というものを次のように定義する。

• 空の文字列("")にどんな整数を掛けても空の文字列になる
• 整数0を掛けると、どんな文字列も空の文字列になる
• 空でない文字列に正の整数を掛けると、文字列をその値の数だけ繰り返す
• 空でない文字列に負の整数を掛けると、文字列を反転させたものを、その数だけ繰り返す

文字列sFactor、整数iFactorを与えたときに、以上のルールに従って得られる文字列を返すメソッドを作成せよ。

私の解答は以下の通り。

public class StringMult {

 public String times(String sFactor, int iFactor) {
  if( sFactor.equals("") || iFactor ==0 ){
   return "";
  }
  if( iFactor < 0 ){
   StringBuffer sb = new StringBuffer(sFactor);
   sFactor = sb.reverse().toString();
   iFactor = Math.abs(iFactor);
  }
  String result = "";
  for( int i=0 ; i<iFactor; i++ ){
   result += sFactor;
  }
  return result;
 }

}

得点は239.13/250、全体の正解率は約94.4%。

文字列の反転はStringBufferクラスにメソッドが用意されているので、それを用いる。また、文字列の結合はStringよりもStringBufferを用い、appendメソッドで結合していくのが高速化できるポイントになるようだ。

Rのmissing関数に関する調査

あるパッケージの関数を眺めていたらmissingという関数が出てきて、気になったので調べてみた。missing関数の呼び方は極めて単純である。

missing(x)

missingは関数の引数として欠けているか否かを評価する。missing関数は関数の中で評価される前に利用しないと意味がない。つまり、missing(x)とする前に、引数xに一切手を加えてはならないのである。また、ネストするとmissing関数は使えなくなる。同じ階層のみで利用可能である(将来的には変更されるらしいが)。

plot関数はx,y座標のyを省くと、勝手にxがyになり1,2,3,...をx座標に設定するが(plot(c(1,3,5))を試してみよ)、それはmissing関数を用いて実装することができる。Exampleの関数myplotがその例である。

myplot <- function(x,y) {
 if(missing(y)) { # yがなかったら
  y <- x # xをyに置き換えて
  x <- 1:length(y) # xを再設定 
 }
 plot(x,y)
}

TopCoder SRM197 Div2 250Pts

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

問題について説明する。

ガーデニングにおける水やりを考える。縦にn、横にn箇所植物を格子状に配置する。植物の間隔はrowDist、colDistで定義されている。また、泥で汚れるのが嫌なので、水やりは離れたところから行う。hoseDist離れた場所まで水をやることができるものとする。このとき、何ヶ所の植物に水をやることができないかを返すメソッドを作成せよ。なお、植物周りにも泥があるため、踏みこめない領域は、植物の周囲にもrowDist、colDistの分だけ存在する。

例えば、n=3、rowDist=2、colDist=1、hostDist=1とすると、2行目の3つの植物には水をやれないので、3が返される(1、3行目は上下から水をやればcolDist=1、hoseDist=1なので水が届く)。

私の解答は以下の通り。

public class GardenHose {
 public int countDead(int n, int rowDist, int colDist, int hoseDist) {
  boolean watered[][] = new boolean[n][n];
  for( int i=0 ; i<n ; i++ ){
   for( int j=0 ; j<n ; j++){
    watered[i][j] = false;
   }
  }
  for( int i=0 ; i<n ; i++ ){
   for( int j=0 ; j<n ; j++ ){
    if( hoseDist >= colDist*(i+1) ){
     watered[i][j] = true; // 列方向から水が届く
     watered[n-1-i][j] = true; // 反対側も同じく届く
    }
    if( hoseDist >= rowDist*(j+1) ){
     watered[i][j] = true; // 行方向から水が届く
     watered[i][n-1-j] = true;
    }
   }
  }
  int dry = 0;
  for( int i=0 ; i<n ; i++ ){
   for( int j=0 ; j<n ; j++ ){
    if( watered[i][j] == false ){
     dry++; // 水をやれなかった場所をカウント
    }
   }
  }
  return dry;
 }
}

得点は192.34/250。正解率は約72%。対称性を利用すると、問題が簡単になる。楽に実装するために、プログラマは怠惰であるべきですな。後から調べて分かったことだが、boolean変数はfalseで初期化されているので、実はwatered[i][j]にfalseを代入する作業は不要であった。

6月の学習記録

2011年6月に学習した本一覧

言語処理のための機械学習入門(pp.1～80)

言語処理のための数学、文書のベクトル表現、k-Means法などを学習

ソフトウェアテスト HAYST法入門(pp.1～139)

HAYST法というのは、効率の良いテストのために直交表を応用したものらしい。詳細は後日記事にしたい。

はじめての実験計画法(pp.1～20)

一元配置分散分析、実験計画法は直交表を利用する手法らしいので、学習することに。