Javaの私的まとめ13

Javaのお勉強その13

1. クラス2
   

   メソッド内でクラスとオブジェクトの生成を同時に行う。以下の例ではインタフェースをmain内で実装し、オブジェクトを作成している。引数にnewを渡して関数を呼ぶことも無名クラスを利用したことになる。
   

   interface IF{
    void method();
   }
   
   class mumei{
    public static void main(String[] args){
     IF ifobj = new IF(){
      public void method(){
       System.out.println("Hello,java");
      }
     };
     ifobj.method();
    }
   }

   結果は次の通り。
   

   Hello,java

2. Scanner
   

   java.util.Scannerは入力の読み込みに使われる。
   

   Scanner sc = new Scanner(入力ファイルパスor入力ストリームor文字列オブジェクト)

   標準入力からの読み込みを行う場合はScannerの引数にSystem.inを与える。
   

   Scannerには区切りを表す文字(","などのStringまたはPattern)を引数に取り、その結果をScannerに戻すメソッドuseDelimiterというメソッドがある。
   

   Scannerの検索メソッド

   String findInLine(Pattern p)	pで指定されるパターンを検索し、見つけたものを戻す。なければnullを戻す
   String findInLine(Pattern p)	pで指定される文字列を検索し、見つけたものを戻す。なければnullを戻す
   boolean hasNext(Pattern p)	次に読み込むべきものがpで指定されるパターンであればtrueを戻す。
   String next(Pattern p)	pで指定されるパターンに一致するものを読み込んで戻す。

3. 正規表現
   

   正規表現を使うときにはjava.util.regex.*(PatternとMatcher)をimportする必要がある。
   

   パターンは文字列検索に用いることができる。Patternオブジェクトの作成は次の形式で作成される。Matcherオブジェクトはpで指定した正規表現を検索するためのオブジェクトである。
   

   Pattern p = Pattern.complile("ABA");
   Matcher m = p.matcher("abcABABAdABA")

   Matcherクラスのメソッドの代表例

   boolean find()	正規表現に一致したものがあればtrueを返す。
   int start()	見つかったパターンの先頭インデックスを返す。
   String group()	見つかったパターンに該当した文字列を返す。

   正規表現の例

   .	任意の文字
   \d	数字
   \s	空白文字
   c?	cが1or0回
   \w	アルファベット、数字、アンダーバーのいずれか
   c*	cが0回以上
   c+	cが1回以上

   ScannerクラスのfindInLineによりパターンの検索ができる。
   

   StringにはString[] split(String s)というメソッドがある。sには正規表現を指定することもできる。
   

TopCoder SRM222 Div2 250Pts

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

入力の文字列inputが与えられたときに、2回以上同じ文字列が現れる文字列の中で、最長になる文字列を返せ。なお、文字列inputの長さの上限は50であり、文字列に利用可能な文字は小文字、大文字のアルファベットのみとする。

私の解答はこちら。

public class TextCompressor {
 public String longestRepeat(String sourceText) {
  for( int i=sourceText.length()/2 ; i>0 ; i-- ){
   for( int j=0 ; j<sourceText.length()-i ; j++ ){
    String tar = sourceText.substring(j, j+i);
    if( sourceText.substring(j+i).contains(tar) ) return tar;
   }
  }
  return "";
 }
}

実はSRM198の問題とコードはほとんど同じ。返す値が最長の文字列そのものか、その長さなのかという違いぐらいしかないというオチ。

TopCoder SRM198 Div2 250Pts

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

入力の文字列inputが与えられたときに、2回以上同じ文字列が現れる文字列の中で、最長になる文字列の長さを返せ。なお、文字列inputの長さの上限は50であり、文字列に利用可能な文字は小文字、大文字のアルファベットのみとする。

サンプルとなる解答はこちら。

public class Reppity {
 public int longestRep(String input) {
  for( int i=input.length()/2 ; i>0 ; i-- ){
   for( int j=0 ; j<input.length()-i ; j++ ){
    String tar = input.substring(j, j+i);
    if( input.substring(j+i).contains(tar) ) return i;
   }
  }
 return 0;
 }
}

長い方の文字列から探索していくのがキモ。気持ちのよい解き方が思い浮かばず解くのを断念してしまいました。解答を見れば納得できるのですがね...

TopCoder SRM238 Div2 250Pts

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

文字列配列が入力されたときにそのハッシュ値を計算する。今回ハッシュ値は配列の一つの要素に対して次のように定義する。

ハッシュ値=アルファベットの位置+その文字列が配列の何番目か+文字が文字列の何番目の位置にあるか

配列の各要素で上の値を計算し、その合計を配列のハッシュ値として返すメソッドを作成せよ。ただし、アルファベットの位置というのは、'A'を基準とした位置である。'A'を0とし、'B'を1、'C'を2というようにする。なお、入力input[]中のアルファベットは大文字のA-Zに限られる。配列や文字が何番目かというのも同様に先頭を0として扱うこと。

例えば、input[]={"ABC","DEF"}という入力であったとすれば、先頭の要素"ABC"のハッシュ値は(0+0+0)+(1+0+1)+(2+0+2)=6、"DEF"のハッシュ値は(3+1+0)+(4+1+1)+(5+1+2)=18なので、6+18=24が返す値となる。

私の解答はこちら。

public class ArrayHash {
 public int getHash(String[] input) {
  int total = 0;
  for( int i=0 ; i<input.length ; i++ ){
   for( int j=0 ; j<input[i].length() ; j++ ){
    total += i+j+(input[i].charAt(j)-'A');
   }
  }
  return total;
 }
}

得点は248.36/251、中央値は約240点弱。二重ループの例題になってしまいました。

TopCoder SRM237 Div2 250Pts

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

0-9と書かれたカードからなるデッキからプレーヤーにカードを配る。カードの順を上から表した文字列をdeckとし、それをnumPlayersに順番に配る。このとき各プレーヤーに対し、配られたカードを順に表す文字列配列を返せ。ただし、カードの枚数は常にプレーヤー数の倍数ちょうどで用意されているとは限らない。倍数にならない時は、最大限配りつつ枚数は全員同じになるようにせよ。

例えばnumPlayers=3、deck="03579"とすると、返す配列は{"0","3","5"}になる。7、9と書かれたカードは配らないことに注意。

私の解答はこちら。

import java.util.Arrays;
public class Cards {
 public String[] deal(int numPlayers, String deck) {
  int nDeal = deck.length()/numPlayers;
  String[] ret = new String[numPlayers];
  Arrays.fill(ret,"");
  for( int i=0 ; i<nDeal ; i++ ){
   for( int j=0 ; j<numPlayers ; j++ ){
    ret[j] += deck.charAt(i*numPlayers+j);
   }
  }
 return ret;
 }
}

得点は205.07/250、参照型のStringを初期化すると""でなく、nullが入るということを忘れていて、いつまでたってもnull pointer exceptionが出ていましたとさ。

TopCoder SRM236 Div2 250Pts

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

大きな数というのは指数表記される。"基数部^指数部"という形式で与えられた二つの数値を表す文字列が与えられたときに、大きい方の値を示す文字列を返せ。数値の比較には実際の値を比較するのではなく、数学的トリック、つまり対数を取るということを用いるとよい。なお、二つの値が等しいということは無いものとする。

私の解答はこちら。

public class MassiveNumbers {
 public String getLargest(String numberA, String numberB) {
  int[] A = new int[2];
  int[] B = new int[2];
  String[] sA = numberA.split("\\^"); // \\^としないと^という文字を指さないことに注意
  String[] sB = numberB.split("\\^");
  for( int i=0 ; i<2 ; i++ ){
   A[i] = Integer.parseInt(sA[i]);
   B[i] = Integer.parseInt(sB[i]);
  }
  return A[1]*Math.log(A[0]) > B[1]*Math.log(B[0]) ? numberA : numberB;
 }
}

得点は241.06/250、中央値は約211点。StringTokenizerというクラスが目に留まったので、近いうちに調べてみることにしよう。

Javaの私的まとめ12

Javaのお勉強その12

1. 基本パッケージその1
   

   java.lang.*はJavaの基本的なパッケージであり、このパッケージのクラスを用いるときには、java.langを付ける必要はない。
   

   すべてのクラスのスーパークラスがObjectになる。
   

   Objectのequalsは==と同じだが、サブクラスでは異なることがある。例えばStringのequalsはオブジェクトの内容を比較するようになっている。
   

2. String
   

   Stringは変更不可な文字列を表すクラスである。
   

   同じ文字列のリテラルは、同じオブジェクトが割り当てられる。以下のs1、s2は同じオブジェクトが割り当てられ、s1==s2であり、s1.equals(s2)==trueでもある。
   

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

   StringBuffer、StringBuilderはStringとは違い、変更可能な文字列を扱うクラスである。
   

   StringBufferとStringBuilderはスレッドセーフか否かという違いのみである。単一スレッドのプログラムであれば、StringBuilderが推奨されている。
   

   StringBuilderのコンストラクタは次の3種類がある(StringBufferでも同様)。
   

   StringBuilder(); // 空のオブジェクト生成
   StringBuilder(int num); // バッファサイズがnumの空のオブジェクトを生成
   StringBuilder(String str); // sという文字列を持つオブジェクトを生成

   StringBuilderの役に立つメソッド
   

   insert(int pos,X s); // posにsを入れる。Xは基本データ型やString、Objectが入れられる。
   delete(int start,int end); // インデックスがstartからend-1までの箇所を削除
   setCharAt(int pos,char c); // posの場所の内容をcで置き換える
   // 文字列の長さをlenにする。lenが現在の文字列長よりも小さいと切り捨て、
   // 長い場合は'\u0000'を後ろに埋める。
   setLength(int len);

   StringBuilder、StringBufferは==とequalsは同じ働きをする。
   

3. ラッパークラス
   

   基本データ型にはラッパークラスが定義されており、値は変更できない。boolean以外のラッパークラスは、Numberという抽象クラスのサブクラスになる。
   

   ラッパークラスのオブジェクトは、対応する値、変数から生成される。
   

   Character以外のラッパークラスのオブジェクトは文字列からも生成できる。
   

   Boolean bl = new Boolean("True"); // 大文字が混じってもOK

   valueOfは値からオブジェクトを生成するのに用いられる。
   

   Integer i = new Integer.valueOf(1);

   ラッパークラスのtoStringメソッドは保持する値を文字列に変換する。
   

   ラッパークラスから基本データの値を取り出すのは*Value()というメソッドを用いる。
   

   char pc = wc.charValue();

   文字列から基本データの値を取り出すにはparse*()というメソッドを用いる。
   

   double d = Double.parseDouble("1.234");

   Integer、Longクラスにはto{Binary,Octal,Hex}Stringというメソッドがあり、10進数の数値を2進数、8進数、16進数に変換した文字列を得ることができる。
   

   ラッパークラスの比較はequalsメソッドを用いる。ラッパークラスと基本クラスは比較できる。比較する際に、ボクシング・アンボクシング変換が発生し、比較できるようになる。
   

   Booleanはif文の条件判定に用いることができる。
   

   Boolean以外のラッパークラスにはMAX_VALUE、MIN_VALUEというpublic static finalなフィールドがある。基本データの最大、最小の値を示している。
   

4. ロケール
   

   ロケールは言語などで特徴づけられる地域を表す。例えば数値を表すフォーマットは地域によって違うため、ロケールによって処理を変えるといったことをする。java.util.Localeというクラスが用意されている。
   

   Local ljp = new Locale("ja","JP");

   数値を扱うためにjava.text.NumberFormatというクラスが用意されている。通貨を表すために、Currencyというクラスがある。
   

   import java.util.*;
   import java.text.*;
   
   class localeTest{
       public static void main(String[] args){
   	Locale lus = new Locale("en","US");
   	NumberFormat nf = NumberFormat.getInstance(lus);
   	System.out.println(nf.format(1000));
   	NumberFormat nfc = NumberFormat.getCurrencyInstance(new Locale("ja","JP"));
   	System.out.println(nfc.getCurrency().toString());
       }
   }

   上のプログラムの出力結果は次のようになる。
   

   1,000
   JPY

Javaの私的まとめ11

Javaのお勉強その11

1. スレッドその2
   

   waitメソッドはスレッドのロックを解放し、通知を受けるまでスレッドを待機状態にする。
   

   notifyメソッドはロックの解放を通知し、待機状態のスレッドのどれかをロック探索状態(ロック取得を求める状態)にする。
   

   notifyAllメソッドはすべての待機中のスレッドに通知し、それらをロック探索状態にする。スレッドが多くなるとメソッドの実行時間は大きくなる。
   

   wait、notify、notifyAllはObjectクラスに属するメソッドである。
   

   interruptはThreadのメソッドである。そのスレッドがwaitで待機している場合は、それを再開してwaitにInterruptedExceptionをスローさせる。
   

   holdsLockはObjectを引数に取るThreadのstaticメソッドである。Thread.holdsLock(obj)として、objはロックを取得されていればTrue、そうでなければFalseを返す。
   

   2スレッドが互いに必要としているオブジェクトをロックするとプログラムが停止する。このことをデッドロックという。
   

   staticなsynchronizedメソッドはクラスのロックを取得する。
   

   synchronizedはメソッド全体でも、一部だけにつけることもできる。
   

2. クラス1
   

   クラスの中で定義されるクラスをネストクラスとよび、staticでないネストクラスをインナークラスという。staticでないネストクラスはstaticなメンバや静的初期化子を持つことができない。
   

   staticでないネストクラスはその側のクラスのオブジェクトを生成してからでないと使えない。
   

   class Outer{
    class Inner1{ ... }
    static class Inner2{ ... }
   }

   上のようなコードがあったときに、Outerの非staticなメソッドの内部では次のようにする。
   

   Inner1 inner1 = new Inner1();

   staticなメソッド内では次のようになる。
   

   Outer outer = new Outer();
   Inner1 inner1 = outer.new Inner1();

   staticなネストクラスの場合はOuterのメソッド内では、
   

   Inner2 inner2 = new Inner2();

   になる。Outerの外部では次のように呼べる。
   

   Outer.Inner1 inner1 = new Outer.new Inner1();
   Outer.Inner2 inner2 = new Outer.Inner2();

   メソッドの中でクラスを定義することもできる。ローカルインナークラスと呼ばれ、メソッド内でのみ有効になる。アクセス修飾子は付けられない。
   

   インナークラスが定義されているメソッド内の変数や引数で、final指定されているものにはローカルインナークラスからアクセスできる。
   

TopCoder SRM235 Div2 250Pts

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

物理実験で温度が整数値で得られるセンサーを利用している。ただ、このセンサーは精度が悪く、ノイズが乗るのでメジアンフィルタを利用してノイズを減らそうと考えた。ここでいうメジアンフィルタというのは、ある注目しているi番目の測定値とその前後の測定値の中央値を返すというものである。また、最初と最後の要素は、前後のどちらかの要素がかけているので、その場合は、注目している値をそのまま返せばよいとする。data[]という配列が与えられたときに、メジアンフィルタを適用した結果得られる配列を返せ。

私の解答はこちら。

import java.util.*;
public class NoisySensor {
 public int[] medianFilter(int[] data) {
  ArrayList result = new ArrayList();
  ArrayList list = new ArrayList();
  if( data.length < 3) return data;
  result.add(data[0]);
  list.add(data[0]);
  list.add(data[1]);
  for( int i=2 ; i<data.length ; i++ ){
   list.add(data[i]);
   Collections.sort(list);
   result.add(list.get(1));
   int idx = list.indexOf(data[i-2]);
   list.remove(idx);
  }
  result.add(data[data.length-1]);
  Integer[] Warray = (Integer[])result.toArray(new Integer[0]);
  int[] array = new int[data.length];
  for( int i=0 ; i<array.length ; i++ ){
   array[i] = Warray[i].intValue();
  }
  return array;
 }
}

得点は158点、中央値はもっと上の値である。はじめてコレクションを利用したので、本を見ながら試行錯誤して解いていた。

TopCoder SRM234 Div2 250Pts

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

プレーヤーを表すAとBという文字がある。A、Bが実行したことをA、Bという文字列で表したmovesという文字列が与えられたときに、AかBの最大コンボ数を返すメソッドを作成せよ。コンボというのは相手に邪魔されていない一連の実行を指す。

例えばAABAAABBBBAとあれば、Bの4連続が最大で続いた回数になるので4が回答になる。

私の解答はこちら。

public class ComboLength {
 public int howLong(String moves) {
  String[] sp = moves.split("");
  String start = sp[0];
  int max = 1;
  int combo = 1;
  for( int i=1 ; i<sp.length ; i++ ){
   if( start.equals(sp[i]) ){
    combo++;
    max = Math.max(max, combo);
   }else{
    combo = 1;
    start = sp[i];
   }
  }
  return max;
 }
}

得点は244.71/250。上位者の回答でお気に入りはこれ。分岐もStringオブジェクトの大量生成もなく、スマートに感じました。

public class ComboLength {
 public int howLong(String moves) {
  char prev = -1;
  int result = 0;
  int count = 1;
  for( final char c : moves.toCharArray() ){
   count = (c == prev) ? count+1 : 1;
   result = Math.max(result, count);
   prev = c;
  }
  return result;
 }
}

TopCoder SRM233 Div2 250Pts

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

textという文字列配列が与えられたときに、それらをすべて右揃えにしたものを返せ。文字列配列の順序はそのままでよい。したがって、文字列の長さはすべて、text中の文字列の中で最長のものになる。また、左に埋められる文字はすべて空白(" ")になる。

私の解答はこちら。

public class JustifyText {
 public String[] format(String[] text) {
  int maxlen = -1;
  // 全体で最大になる文字列の長さを求める
  for( int i=0 ; i<text.length ; i++ ){
   maxlen = Math.max(maxlen,text[i].length());
  }
  String[] ret = new String[text.length];
  for( int i=0 ; i<text.length ; i++ ){
   StringBuffer tmp = new StringBuffer();
   // Rのrepみたいな関数はないのかな?ここで空白を生成
   for( int j=0 ; j<maxlen-text[i].length() ; j++ ){
    tmp.append(" ");
   }
   ret[i] = tmp.toString() + text[i];
  }
  return ret;
 }
}

得点は242.12/250、中央値は約215点。素直な実装になっていると思います。

TopCoder SRM229 Div2 250Pts

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

ゲームではハイスコアを記録していることがよくある。ハイスコアは降順にスコアをならべたものである。例えば100,90,90,30など。これを順位に直すと、1,2,2,4のようになる。同点はとりうる順位候補の中で一番小さい順位にする。ハイスコアを記録する数placesと既存のハイスコアscores[](ソート済)と新しい記録newscoreが入力されたときに、newscoreが何位になるかを返すメソッドを作成せよ。ただし、placesに入れない場合は-1を返すようにせよ。また、同点の場合は、後ろに並べられると考える。このことについては次の例を見て欲しい。

scores[]={5,4,3,2,1}、newscore=1、places=5とすると、1は5位タイになるが、その値はplaces=5になっているため、scoresの中に追加できないので-1を返すことになる。またscores[]={}、newscore=4、places=2とするとscoresは空なので1位となり1が返される。

私の解答は以下の通り。

public class Highscore {
 public int getRank(int[] scores, int newscore, int places) {
  int rank = 0;
  boolean isIn = false;
  if( scores.length == 0 ) return 1;
  for( int i=0 ; i<scores.length ; i++ ){
   if( newscore > scores[i] && isIn == false ){
     return i+1; // いきなり上回った
   }else if( newscore == scores[i] && isIn == false ){
    rank = i+1;
    // 同点が出てきた && まだランキングに入れられる
    if( scores.length < places) return rank; 
    isIn = true;
   }else if( newscore > scores[i] && isIn == true ){
    return rank; // 同点が出てきたのち、途中で上回った(scores.length == placesだよ!)
   }
  }
  // 同点も、いきなり上回ることもなかったら、最後に入れられるかチェック
  if( scores.length < places ) return scores.length+1;
  return -1;
 }
}

得点は75.00/250、再提出5回でようやくシステムテストを通過。中央値は約120点という難しめの問題。

TopCoder SRM225 Div2 250Pts

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

ネットやメールにおいて、署名をカスタムして面白いものにしようとすることがある。あなたは掲示板の管理者で、特定のルールに従ったときに名前に飾りをつけるようにしようとしている。nameは名前、commands[]はnameの前後のどちらを飾るかを指定するもので、decorations[]は飾る文字列である。commandは3種類ある。commnads[i]がprependなら前にdecorations[i]をつけ、appendなら後ろにdecorations[i]をつけ、surroundならdecorations[i]を前につけ、後ろにはdecoratios[i]を反転させたものを付けることになる。nameに対し、command[]、decorations[]を順番に施した結果得られる文字列を返すメソッドを作成せよ。

私の解答は以下の通り。

public class SignatureDecorator {
 public String applyDecoration(String name, String[] commands, String[] decorations) {
  String str = new String(name);
  for( int i=0 ; i<commands.length ; i++ ){
   if( commands[i].equals("prepend") ){
    str = decorations[i] + str;
   }else if( commands[i].equals("append") ){
    str = str + decorations[i];
   }else if( commands[i].equals("surround") ){
    String rev = new StringBuffer(decorations[i]).reverse().toString();
    str = decorations[i] + str + rev;
   }
  }
  return str;
 }
}

得点は216.56/250、中央値は約192点。

TopCoder SRM232 Div2 250Pts

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

1971年以前は、イギリスの通貨システムはシャルルマーニュの時代からのものが利用されていた。通貨の種類はペニー、シリング、ポンドであった。12ペニーが1シリング、20シリングが1ポンドということになっていた。penceというペニーの数が与えられたときに、ポンドをできるだけ多く、次にシリングをできるだけ多くし、それぞれが何枚ずつに変換されるかをint型の配列にして返すメソッドを作成せよ。配列の中身は、penceを変換した結果得られる順にポンド、シリング、ペニーの数である。

例えば500ペンスは2ポンド、1シリング、8ペニーになる。2*12*20+1*12+8=500という関係になっている。

私の解答は以下の通り。

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

得点は248.45/250、中央値は約236点。初めてのワンライナーです。240で割って240を掛けるというコードは気味が悪いです。

TopCoder SRM226 Div2 250Pts

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

acronymというのは、長い名前を表す文字列である。各単語の先頭を取り出し、大文字にすることによってacronymは作られる。ただし、例外があって、and、the、ofについてはacronymを作るときには無視をすることになっている。この問題では単語とは空白を含まない連続した文字と定義する。longNameという文字列(文章)が与えられたときに、acronymを生成してその文字列を返すメソッドを作成せよ。

私の解答は以下の通り。

public class VLNString {
 public String makeAcronym(String longName) {
  String[] sp = longName.trim().split(" ");
  StringBuffer sb = new StringBuffer();
  for( int i=0 ; i<sp.length ; i++ ){
   // 単語と単語の間の空白は常に1字とは限らないのがミソ
   if( sp[i].equals("and") || sp[i].equals("the") || 
       sp[i].equals("of") || sp[i].equals("") ){
    continue;
   }else{
     sb.append(sp[i].substring(0,1).toUpperCase());
   }
  }
  return sb.toString();
 }
}

得点は223.77/250、中央値は約220点。スペースで切った後にできることがある""の処理は処理しないということに気付くのに時間がかかった。

TopCoder SRM227 Div2 250Pts

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

綴りチェックのシステムを作成しており、2つの単語の近さを決めるコードを書くことになった。単語の近さというのは、(あまりよくないが)同じ文字になった位置の数で決めるものとする。二つの文字列a、bが与えられたときに、単語の近さを表す数を返すメソッドを作成せよ。

私の解答は以下の通り。

public class StringCompare {
 public int simpleDifference(String a, String b) {
  int nmatch = 0;
  for( int i=0 ; i<Math.min(a.length(), b.length()) ; i++ ){
   if( a.charAt(i) == b.charAt(i) ) nmatch++;
  }
  return nmatch;
 }
}

得点は249.25/250、中央値は約244.6点。簡単なので、特にコメントはなし。

TopCoder SRM230 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。それでは、問題について説明する。なおSRM 231のDiv2 250PtsはSRM 186と同じ問題なので、省略する。

数学的帰納法により、次の式を示すことができる。
s = 1³ + 2³ + ... + (n-1)³ < n⁴ < 1³ + 2³ + ... + n³ = S

上の式にnが与えられたとして、(S+s)/2 - n⁴/4を表す分数を返せ。ただし、分数は2要素の整数型配列からなり、一つ目の要素が分子、二つ目の要素が分母を表すものとする。また、約分も行うこと。

私の解答は以下の通り。

public class InequalityChecker {
 public int[] getDifferences(int n) {
  int s = ((n-1)*n/2)*((n-1)*n/2);
  int S = (n*(n+1)/2)*(n*(n+1)/2);
  int num = 2*(S+s)-n*n*n*n;
  int den = 4;
  if( num % 4 == 0){
   num /= 4;
   den /= 4;
  }else if( num % 2 == 0 ){
   num /= 2;
   den /= 2;
  }
  return new int[]{num,den};
 }
}

得点は235.09/250、中央値は約160点。開催時の提出者の正解率は約90%。最大公約数の計算が不要なので、約分も難しくないと思います。分母の候補は(2(s+S)-n⁴)/4を返すということから1,2,4しかありえないので、2、4で割り切れるか検討すればOKということになります。また、sやSの計算には高校数学で習うシグマの公式を利用しているので、ちょっとわかりにくいかもしれません。ただ、O(1)で計算できるので速い計算になると思います。

TopCoder SRM228 Div2 250Pts

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

商品のコストと売値が与えられたときのマージンについて考える。例えば、$100で$80のコストの商品を売れば、マージンは20%である。今、items[]という売値とコストが文字列になった文字列配列が与えられたときに、全体のマージンはいくつになるかを計算して返すメソッドを作成せよ。ただし、マージンは小数点以下は切り捨てる。また、items[]の一つの文字列は長さが13で、"222.22 111.11"のように、小数点以下は2桁、百の位まである数字が並べられている。左側の数字が売値で、右側の数字がコストを表している。

私の解答は以下の通り。

public class ProfitCalculator {
 public int percent(String[] items) {
  double sold = 0.0;
  double cost = 0.0;
  for( int i=0 ; i<items.length ; i++ ){
   String[] sPrice = items[i].split(" ");
   sold += Double.parseDouble(sPrice[0]);
   cost += Double.parseDouble(sPrice[1]);
  }
  return  (int)((sold-cost)/sold*100);
 }
}

得点は244.21/250、解答者の中央値は218.5点。言われた通りの実装なので、単純かと思います。Javaであれば、一つの文字列は13文字という条件はあっても関係なかったですね。

TopCoder SRM223 Div2 500Pts

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

半分赤、半分黒のデッキ（カードの集まり）のカードゲームをしている。友人はカードをシャッフルして、あなたはデッキをどこかで切る(デッキを切るというのは途中で分けて、上にあるカードをそのまま下に置くということである)。友人は切られたところから順番にカードを表にし、もし途中で赤が出た回数が黒が出た回数を上回ったらあなたは負けとなる。一度もそのようなことが起こらなければあなたの勝ちになる。何度か連続して負けたあなたはずるがしたくなった。そこでルールを破ってカードをこっそり見て、どこで切れば勝てるか見た。さて、deckというR(赤)、B(黒)という文字からなる文字列型変数が与えられる。文字列の先頭がデッキの一番上を示している。デッキを切った後にある一番上のカードを示すインデックスを返すメソッドを作成せよ。もし、複数勝てる方法があるのであれば、インデックスが最小になるものを返せ。

例えばdeck="BRBRBR"であれば0(つまりカードの順序は不変)、2(2枚最後尾に動かす)、4が条件を満たすが、最小の値として0を返すことになる。

私の解答は以下の通り。

public class BlackAndRed {
 public int cut(String deck) {
  int[] rNum = new int[deck.length()];
  int[] bNum = new int[deck.length()];

  for( int i=0 ; i<deck.length() ; i++ ){
   if( deck.charAt(i) == 'R' ){ // R,Bの累積枚数をカウント
    rNum[i]++;
   }else{
    bNum[i]++;
   }
  }
  int idx = 0;
  for( int i=0 ; i<deck.length() ; i++ ){
   boolean isOK = true;
   int[] rr = new int[deck.length()-i];
   int[] bb = new int[deck.length()-i];
   rr[0] = rNum[i];
   bb[0] = bNum[i];
   // i番目以降の部分配列で、R、Bの累積枚数を配列で表現
   for( int j=1 ; j<rr.length ; j++ ){
    rr[j] = rNum[j+i]+rr[j-1];
    bb[j] = bNum[j+i]+bb[j-1];
   }
   for( int j=0 ; j<rr.length ; j++){
    if( bb[j] - rr[j] < 0){ // Rの枚数がBの枚数より多くなった
     isOK = false;
     break;
    }
   }
   if( isOK ){
    idx = i;
    break;
   }
  }
  return idx;
 }
}

得点は180.37/500。部分配列の累積和をとる関数でバグを出していて、printデバッグを行う羽目に。問題はブルートフォース的に解いている。i番目で切ると仮定して、その後のRとBの累積枚数を数え、途中でRの枚数が上回ればダメ、そうでなければOKという方針で回答している。

Javaの私的まとめ10

Javaのお勉強その10

1. スレッドその1
   

   1つのプログラム中に複数の処理を同時に走らせることをスレッドという。
   

   スレッドの作り方は2種類ある。一つはThreadクラスを拡張してrunメソッドを実装する方法
   

   class myThread extends Thread{ public void run(){ ... }}

   myThread mt = new myThread();mt.start();

   もう一つはRunnableインタフェースを実装するし、runメソッドを実装する方法である。
   

   class myRunnable implements Runnable{ public void run(){ ... }}

   myRunnable mr = new myRunnable();Thread t = new Thread(mr);t.start();

   runメソッドを実装して、startメソッドでスレッド(中身はrunメソッド)を開始する。
   

   スレッドには実行中、実行可能、実行不可能、死んでいる(終了状態)の4つの状態がある。
   

   yieldはThreadのstaticメソッドである。これを実行すると、実行中のメソッドは実行権利を放棄する。実行可能状態のスレッドがほかにあれば、スケジューラにより、それを実行することがある。
   

   sleepはThreadの実行を一定時間止める役割を持つ。これもThreadのstaticメソッドである(呼ぶときはThread.sleep(1000)などと記述する)。
   

   joinはThreadの非staticなメソッドで、他のスレッドと同期をとるために、スレッドの終了を待つメソッドである。
   

   JavaのI/Oメソッドは、時間がかかるとスレッドを実行不可能なブロック状態にし、他のスレッドに実行権利を譲る。状況が変化すると、実行可能状態に遷移する。
   

   複数のスレッドを制御する共有オブジェクトをモニターという。スレッドの実行順序は不定なので、あるスレッドがもにーたにアクセスしている間に別のスレッドがそれを書き換えて矛盾が起きる可能性がある。
   

   synchronizedメソッドを利用すると、あるスレッドがメソッドを呼び出している間、他のスレッドはそのメソッドを利用できなくなる。
   

Javaの私的まとめ9

Javaのお勉強その9

1. アサーション
   

   プログラマーがプログラム実行時に常に真にならないとassertする条件式を書き、実行時に条件が満たされているかチェックする仕組みのこと
   

   アサート文は次の形式になっている。
   

   assert 式1;
   assert 式1:式2;

   式1はチェックする条件式、1行目ではfalseだとAssetionErrorがスローされる。2行目では式2がAssertionErrorがスローされるだけでなく、式2のメッセージが表示される。式2は値を持たせる必要がある。
   

   assertを使うと、評価を行う分だけ、実行速度は下がる。
   

   -source 1.3をつけてコンパイルすると、assert文がコンパイルエラーになる。識別子として使用できるが、警告が表示される。1.4以降の数値をつけてコンパイルするとassertという識別子は利用不可になる。
   

   assertを利用する場合は、実行時に-eaオプションをつける。次の指定方法がある。
   

   java -ea Test
   -ea
   -ea:クラス名
   -ea:... (作業ディレクトリの名前のないパッケージ内のassertを有効にする)
   -ea:パッケージ名

   アサーションを無効化する実行オプションは-daである。
   

   複数の矛盾するオプションを指定した場合は、詳細な設定をした方が優先される。
   

   assertはエラー処理ではないことに注意。
   

TopCoder SRM224 Div2 250Pts

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

プリンタがウィルスに感染して、訳のわからないことになってしまった。あなたは、しばらく印刷しているうちにあることに気が付いた。ひっくり返っているのである。ページの各行の左半分は真ん中から左の余白へ、右半分は右の余白から真ん中に文章が続いているのである。例えば、"abcd"という印刷は本来は"badc"になっているということである。あなたへの問題は1行のlineが与えられたときに、これを解読して本来の順序に戻すということである。なお、文字の数は常に偶数であると仮定してよいものとする。

私の解答は以下の通り。

public class InsideOut {
 public String unscramble(String line) {
  StringBuffer s1 = new StringBuffer(line.substring(0, line.length()/2));
  StringBuffer s2 = new StringBuffer(line.substring(line.length()/2));
  return s1.reverse().toString() + s2.reverse().toString();
 }
}

得点は244.95。StringBuilderというクラスを利用している回答があったので、調べてみようかと思う。

TopCoder SRM223 Div2 250Pts

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

1つの商品を売るのにかかるコストcosts[]、売値のprices[]、売れた個数sales[]、商品名items[]が与えられたときに、もっとも利益を生み出した(利益率ではないよ)商品名を返すメソッドを作成する。どの配列も一つの添え字で一つの商品を表している。利益を生みだす製品がなければ空文字を返すようにせよ。もっとも利益を出した商品が複数ある場合は添え字の小さい方を返すようにすること。

私の解答は以下の通り。

public class MostProfitable {
 public String bestItem(int[] costs, int[] prices, int[] sales, String[] items) {
  int idx = -1;
  int maxProfit = -1;
  for( int i=0 ; i<costs.length ; i++ ){
   int profit = (prices[i]-costs[i])*sales[i];
   // profit > maxProfitの不等号に注意、=は不要
   // 利益を出す商品に絞るためprofit>0が必要
   if( profit > maxProfit && profit>0 ){ 
    idx = i;
    maxProfit = profit;
   }
  }
  if( idx < 0) return "";
  return items[idx];
 }
}

得点は244.86、中央値は約225点。

Javaの私的まとめ8

Javaのお勉強その8

1. 例外
   

   配列の添え字が配列の範囲を超えるなどすると、例外が発生する。例外はその場所から「投げられる」という。
   

   例外を捕捉するにはtry～catch節を用いる。例外が発生する箇所でtry{ }、例外を受け取る場所でcatch(指定した例外){ }と書く。finallyを付けると、例外の発生の有無に関わらず実行される。例えばファイルを閉じるなどの作業をここで行われることがある。
   

   class exceptionTest{
       static int method(){
   	int[] array = new int[3];
   	try{
   	    array[10] = 5;
   	}catch(ArrayIndexOutOfBoundsException e){
   	    System.out.println(e);
   	    return -1;
   	}finally{
   	    System.out.println("Called finally");
   	}
   	return 0;
       }
       public static void main(String[] args){
   	int x = method();
   	System.out.println(x);
       }
   }

   結果は次のようになる。
   

   java exceptionTest
   java.lang.ArrayIndexOutOfBoundsException: 10
   Called finally
   -1 // 例外が発生しても、プログラムは最後まで実行される。
   

2. 例外の種類
   

   Throwableはスローされるクラスを表す。ThrowableのサブクラスであるErrorは回復不可能なエラーでありキャッチすべきでない状態にある。一方、Throwableのもう一つのサブクラスであるExceptionはさらにRuntimeExceptionと検査例外のサブクラスに分かれる。RuntimeExceptionはコンパイル時にチェックされない。その他の例外はコンパイル時にチェックされる。
   

   Errorとそのサブクラスもコンパイル時にチェックされない。
   

   検査例外が発生する場合は、以下のどちらかの方法で処理しなければならない。
   

   // 1つめの処理方法
   int test(){
    try{
     // 処理1
    }catch(例外){
     // 処理2
    }
   }
   // 2つめの処理方法
   int test() throws 例外{
    // 処理1
   }
   

   2つめの処理方法の場合は、メソッドを呼ぶときに再び、上のどちらかの処理を噛ませる必要がある。
   

   複数の例外がある場合はtry～catch～catch～finallyのように書く。
   

   複数の例外が投げられうる候補にある場合、次のように書くことができる。
   

   int test() throws 例外1, 例外2{
    // 処理
   }

   例外はJVMとプログラムが投げるものの2種類に分けられる。
   

   オーバーライドされたメソッドのスローする検査例外は、もとのメソッドのスローする例外かそのサブクラスでなければならない。
   

   RuntimeExceptionとそのサブクラスは検査例外なので自由にスローできる(スーパークラスで何をスローしようともサブクラスでは何をスローしても良い)。また、オーバーライドされたメソッドで例外をスローしなくて良い。
   

   インタフェースのメソッドもオーバーライドと同様のルールが適用される。
   

   Exceptionを派生(extends)させることで、独自の例外を定義できる。
   

TopCoder SRM221 Div2 250Pts

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

小文字のみからなるstrが与えられる。このとき二つの文字列x、yを返すようにせよ。ただし、x、yは次の条件を満たす。

• xとyをくっつけるとstrになる
  
• x中の"a"の数と、y中の"b"の数は等しい
  
• 複数のx、yの候補がある場合は、xの長さが最長になるものを返す
  

私の解答は以下の通り。

public class EqualSubstrings {
 public String[] getSubstrings(String str) {
  String[] ret = {"",""};
  for( int i=0 ; i<=str.length() ; i++ ){ // i=str.lengthまで検討が必要
   String first = str.substring(0,i);
   String second = str.substring(i); // 2つの文字列候補を生成
   int na = 0;
   int nb = 0;
   for( int j=0 ; j<first.length() ; j++ ){
    if( first.charAt(j) == 'a' ) na++;
   }
   for( int j=0 ; j<second.length() ; j++){
    if( second.charAt(j) == 'b' ) nb++;
   }
   if( na == nb ){
    ret[0] = first;
    ret[1] = second;
   }
  }
  return ret;
 }
}

得点は127.55/250、中央値は約188点、提出者の正解率は約54%と低めの結果に。文字列は先頭から見ていくのではなく、後ろからみた方が高速化できますね。解の候補が複数あるときに、xをできるだけ長くというのですから、後ろから見れば、最初にna==nbとなった時点で、そのほかの解を検討する必要がなくなりますので。

Javaの私的まとめ7

Javaのお勉強その7

1. 型変換
   

   大きな型へは自動的に変換される。型の大小関係はdouble>float>long>int>short,char>byteになる。
   

   型が小さくなる方向への型変換は自動的に行われない。ただし、byte、char、shortの変数にint型のリテラルや定数を代入する場合、値が型の扱える値の範囲内であれば、縮小変換が行われる。
   

   足し算や掛け算を行うと、拡大変換が適用される。例えば、double型+int型の結果はdouble型に変換される。byte、char、shortの演算は計算結果がintになる。
   

   暗黙的に型変換ができなくても、キャストにより型変換ができることがある。
   

   参照型の暗黙的な型変換はサブクラスからスーパークラスへの場合、自動的に行われる。
   

   参照型から基本データ型へのキャストは不可能。
   

   int i=40000;
   short s = (short)i;

   はコンパイルできるが、shortが扱える範囲を超えた値なので、情報が失われる。iを2進数表示したうち、下位16ビットがsに入り、その結果が表示されることになる。
   

   参照型データではスーパークラスからサブクラスにキャストすることが可能である。また、サブクラスからスーパークラスへは代入時、暗黙的に変換が行われる。
   

   スーパークラスからサブクラスへのキャストが許されるのは、スーパークラスの変数がサブクラスのオブジェクトを指しているかもしれないからである。ただし、スーパークラス変数の指すものが実際にスーパークラスのオブジェクトであった場合、サブクラスのオブジェクトとして利用できないので、ClassCastExceptionが投げられる。
   

TopCoder SRM220 Div2 250Pts

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

うまれた年(born)から現在の年(year)まで、何回のうるう年を迎えたかを求めるメソッドを作成せよ。ただし、bornがうるう年の場合はそれをカウントせず、yearがうるう年の場合はそれをカウントするようにせよ。

私の解答は以下の通り。

public class LeapAge {
 public int getAge(int year, int born) {
  int nLeap = 0;
  for( int i=born+1 ; i<=year ; i++ ){
   if( i % 100 == 0 && i % 400 == 0 ){
    nLeap++;
   }else if( i % 100 == 0 ){
    continue;
   }else if( i % 4 == 0 ){
    nLeap++;
   }
  }
  return nLeap;
 }
}

得点は237.55/250、中央値は約225点。うるう年の問題はFizzBuzzにならぶベタな問題ですよね。

TopCoder SRM219 Div2 250Pts

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

あなたは美味しい中華料理を食べ終え、ウェイターが請求書を持ってきた。課税される前の額はtotalであった。消費税はこの地域ではtexPercentである。そしてあなたの現在の所持金額はmoneyである。サービスがとてもよかったので、できるだけチップを弾みたいと思った。そこで、次の式を満たすtipの最大値を求めるメソッドを作成せよ。

total + floor(total*taxPercent/100) + floor(total*tip/100) <= money

私の解答は以下の通り。

public class WaiterTipping {
 public int maxPercent(int total, int taxPercent, int money) {
 for( int i=money-total ; i>=0 ; i-- ){ // tipの取りうる上限値から考える
   int tmp = (int) Math.floor(total*taxPercent/100) + (int)Math.floor(total*i/100);
   if( total + tmp <= money ) return i;
 }
 return -1;
 }
}

得点は236.79/250。定義式が与えられているので、それをコードに変換しておしまい。

TopCoder SRM218 Div2 250Pts

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

コンピュータシステムでは、ユーザごとに異なる資源に対するアクセス権限を持っている。rights[]という各ユーザの権限を表す数値、資源を利用するために最低限必要となる権限を表す数値minPermissionが与えられる。rights[]の各要素に対し、アクセス可能であればA、不可能であればDと変換して文字列を返すメソッドを作成せよ。ユーザが0であれば返すのは""になる。

例えばrights[]={0,1,2,3,4,5}、minPermissionが2であれば、返す値は"DDAAAA"になる。権限が0,1のユーザがD(Deny)されるが、2以上のユーザはA(allow)になる。

私の解答は以下の通り。

public class AccessLevel {
 public String canAccess(int[] rights, int minPermission) {
  if( rights.length == 0 ) return "";
  StringBuffer sb = new StringBuffer();
  for( int i=0 ; i<rights.length ; i++ ){
   if( rights[i] >= minPermission ){
    sb.append("A");
   }else{
    sb.append("D");
   }
  }
  return sb.toString();
 }
}

得点は247.76/250、中央値は約245点。順番に判定するだけなので、特に難しいところはないと思います。

TopCoder SRM217 Div2 250Pts

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

車で長旅をしたいと考えているが、限られた燃料しかない。いま1時間ある速さで車を走らせたときに消費する燃料を知っているので、一番長い距離を走ることができる最適な速度を知りたいとする。時速を表すvelocities[]と1時間に消費するガソリンのリットル量consumptions[]、車に入っているガソリンのリットル量fuelが与えられている。velocities[i]とconcumptions[i]は対応関係にあるものとする。このとき、最大で何キロ車を走らせるかを返すメソッドを作成せよ。

私の解答は以下の通り。

public class FuelConsumption {
 public double maximalDistance(int[] velocities, int[] consumptions, int fuel) {
  double maxKM = -1;
  for( int i=0 ; i<velocities.length ; i++ ){
   double dist = (double)velocities[i]/consumptions[i]*fuel;
   if( dist > maxKM ) maxKM = dist;
  }
  return maxKM;
 }
}

得点は244.73/250。解答提出者の正解率は約96%。気を付けることはdoubleにキャストするのを忘れてはいけないという程度だろう。

Javaの私的まとめ6

Javaのお勉強その6

1. 抽象クラス
   

   抽象メソッドを持つクラスを抽象クラスという。抽象メソッドはサブクラスで実装する。
   

   サブクラスがすべてのメソッドを実装しない場合、そのクラスも抽象クラスになる。
   

   抽象クラスにはフィールドや抽象でないメソッドを宣言することもできる。
   

2. インタフェース
   

   抽象メソッドと定数のみから構成される。抽象でないメソッドは含められない。
   

   インタフェースもすべてメソッドを実装しない場合は抽象クラスになる。
   

   インタフェースのメソッドは自動的にpublicな抽象メソッドになる。
   

   フィールドは自動的にpublic static finalになる。フィールドは宣言時に初期化する必要がある。
   

   多重継承に似たことをする場合にはインタフェースを用いる。
   

   インタフェースを実装するクラスはimplementsを用いる。サブインタフェースを作成する場合はextendsを使う。なお、抽象クラスの実装にはextendsを用いる。
   

3. 可変長引数リスト
   

   int(String ...str)のように...を用いて表す。可変長引数リストは1メソッドに1つだけ許される。
   

   可変長引数リストは仮引数が複数ある場合は、一番最後に書かなければならない。
   

   int m(int a,int b)とint m(char ...c)があり、m('A','B')が入力されると可変長引数リストは優先順位が低いため、前者の呼び出し方が利用される。
   

TopCoder SRM215 Div2 500Pts

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

collectionからaddress[]の各要素の文字列が構成できないのは何ケースあるかを求めて返すメソッドを作成する。例えばcollection="AABC"で、address[]={"AC","BD","ACE","AAAC"}であれば、collectionに"A"じは二つしかなく"AAAC"は構成できない。また、"DE"はないので、2つの文字列"BD"、"ACE"も構成できず、3という値が返されることになる。なお、address[]は空白が含まれるが、それはcollection中にはなくても構成できないとはみなさない。

私の解答は以下の通り。

public class Mailbox {
 public int impossible(String collection, String[] address) {
  int isImpossible = 0;
  for( int i=0 ; i<address.length ; i++ ){
   String tmp = new String(collection); // collectionのコピー
   for( int j=0 ; j<address[i].length() ; j++ ){
    if( address[i].charAt(j) == ' ' ){
     continue; // 空白は無視
    }else{
     int pos = tmp.indexOf(address[i].substring(j,j+1));
     if( pos < 0 ){
      // indexOfが負の値ということはcollecionのコピーに文字がない
      isImpossible++;
      break;
     }else{
      // collectionのコピー変数から存在した文字を1つ削除する
      tmp = tmp.replaceFirst(address[i].substring(j,j+1), "");
     }
    }
   }
  }
  return isImpossible;
 }
}

得点は339.55/500。公式の平均点は378.67。細かいが、StringはStringBufferの方がよかったか。isImpossibleはnImpossibleの方がint型の数値を返すところからより妥当だということに気付いた。

TopCoder SRM216 Div2 250Pts

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

カナダからアメリカに引っ越した二人はZEEという単語に困惑している。文字列textが与えられたときに、列中のZEEという単語をZEDという単語に置き換えるようなアシストをしてほしい。ここで言うZEEは前後に空白が含まれる単語であり、ZEEDという単語があった場合、それは置き換える必要はないものとする。また、単語の前後の空白はスペース一つであるものとする。

私の解答は以下の通り。問題文にtextは50字以内という条件があったので、それを利用した。

public class CultureShock {
 public String translate(String text) {
  for( int i=0 ; i<20 ; i++){
   text = text.replaceAll(" ZEE ", " ZED "); // textの途中の文字を置き換え
  }
  text = text.replaceAll("^ZEE ", "ZED "); // 先頭のZEEを置き換え
  text = text.replaceAll(" ZEE$", " ZED"); // 最後尾のZEEを置き換え
  text = text.replaceAll("^ZEE$", "ZED"); // ZEEだけだった場合の置き換え
  return text;
 }
}

得点は172.22/250、中央値は約190点。上の解答はあまりきれいではないので、見かけた解答をいくつか紹介する。

• splitメソッドで配列に単語を格納し、ZEEをZEDに置き換えてそれらを空白を挟みながら、再結合する。
  
• text.replaceAll("\\bZEE\\b","ZED");とする。
  
• text = " " + text + " "と置き換え、text中の" ZEE "を" ZED "へ置換することを先頭から文字列の長さの分だけ繰り返して text.trim()で前後の空文字を外す。
  

TopCoder SRM215 Div2 250Pts

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

numberが与えられたときに、numberは何回各桁の数で割り切れたかを返すメソッドを作成せよ。ただし、0は割れないとする。例えば12345という整数が与えられたら、12345は1、3、5で割り切れるので、3(回)という数値が返ってくる。

私の解答は以下の通り。

public class DivisorDigits {
 public int howMany(int number) {
  int divisible = 0;
  int target = number;
  while( target > 0 ){
   int divisor = target % 10;
   if( divisor != 0 && number % divisor == 0 ) divisible++;
   target /= 10;
  }
  return divisible;
 }
}

得点は239.87/250、全回答者の中央値は約233点。if文はdivisor!=0を先に書くことがポイント。順番を逆にすると、0割を起こして例外が投げられてしまうのである。

TopCoder SRM214 Div2 250Pts

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

ブログを書く人を楽にするために、htmlのタグの自動補完を行うようにしたい。文字列textが与えられたときに、_と_の間はiを用いたタグで挟み、*と*の間はbを用いたタグで挟むようにするメソッドを作成せよ。

私の解答は以下の通り。タグを開く方か否かを管理する変数inI、inBを導入することによって解いた。

public class bloggoShortcuts {
 public String expand(String text) {
  StringBuffer sb = new StringBuffer();
  boolean inI = false;
  boolean inB = false;
  for( int i=0 ; i<text.length() ; i++ ){
   if( text.charAt(i) == '_' && inI == false ){
    sb.append("<i>");
    inI = true;
   }else if( text.charAt(i) == '_' && inI == true ){
    sb.append("</i>");
    inI = false;
   }else if( text.charAt(i) == '*' && inB == false ){
    sb.append("<b>");
    inB = true;
   }else if( text.charAt(i) == '*' && inB == true ){
    sb.append("</b>");
    inB = false;
   }else{
    sb.append(text.charAt(i));
   }
  }
  return sb.toString();
 }
}

得点は236.88/250、中央値は221.09。提出者の正解率は約91%。textが*をcontainsしているうちは、while文でtext.replaceFirstを2回適用し、1回目はタグを開く方、2回目はタグを閉じる方で置換するという方針で解いているプログラムがあったのが印象に残った(iによるタグ付けについても同様のループを行う)。

Javaの私的まとめ5

Javaのお勉強その5

1. フィールド
   

   static宣言されたフィールドはクラス変数であり、オブジェクトを生成せずに利用できる。staticがついていないフィールドはオブジェクトに付随する。
   

   クラス変数は、インスタンス変数よりも先に初期化される。初期値を指定しないと、デフォルトの初期値が与えられる。0(型によっては0.0などになる)やfalseが与えられる。メソッド内の一時変数は初期化されない。
   

   finalがついたら、コンストラクタが終了するまでに初期化しなければならない。
   

2. コンストラクタ
   

   同じクラスのコンストラクタはthis()で、スーパークラスのコンストラクタはsuper()で呼び出せる。
   

   クラス定義時にコンストラクタを書かないと、引数なしのコンストラクタがコンパイラによって自動的につけられる。引数をとるコンストラクタを書くと、デフォルトコンストラクタは自動的につかなくなる。引数をとらないコンストラクタが必要なのであれば、プログラマが書く必要がある。
   

   super()が明示的に呼び出されない場合、最初にsuper()が実行される。したがって、スーパークラスには引数をとらないコンストラクタを書くか、何も書かないでおく必要がある。
   

3. メソッド
   

   インスタンスメソッドを変数.メソッドのように呼び出すと、変数が実際に参照するオブジェクトの型のメソッドが呼び出される。クラスメソッドの場合は、変数の型のメソッドが呼び出される。
   

4. オーバーロード
   

   同じ名前で、仮引数の並びが異なるメソッドを1つのクラス内で宣言すること
   

5. オーバーライド
   

   スーパークラスと同じシグネチャ(メソッド名と仮引数の並び)を持ち、戻り値型が同じ化そのサブタイプであるものを定義すること。
   

   staticメソッドをオーバーライドして、インスタンスメソッドにすることはできない。
   

   privateメソッドをオーバーライドするつもりでメソッドを定義しても、サブクラスからは参照できないので、スーパークラスのものとは無関係のメソッドになる。
   

   final宣言されたメソッドはオーバーライドできない。
   

TopCoder SRM213 Div2 250Pts

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

2列(first、secondと呼ぼう)のフォーク並びの列がある。これらの列をまとめるときに、男性は女性に先に行かせる。2列の先頭の二人の性別が同じであれば、firstの人が先に並ぶ。2列の男女の順序が文字列で与えられたときに、列をまとめた結果を返すメソッドを作成せよ。文字列のMは男性を、Wは女性を表している。また、列の先頭は文字列の先頭になる。

例えば、1番目の列に"MMWM"、2番目の列に"WMMM"が与えられると、結果は"WMMWMMMM"になる。

私の解答は以下の通り。求められた通りに書いたら愚直なコードになりました。

public class Chivalry {
 public String getOrder(String first, String second) {
  StringBuffer order = new StringBuffer();
  int i=0,j=0;
  while(true){
   // i、jで2列を何番目までチェックしたかを管理している。
   // 最初の2分岐は、どちらかの列の人をすべてまとめ終えた状態である
   // 後半の4分岐は、2列の先頭の性別で2*2=4通りあるので単純な場合分けをしている
   if( i == first.length() ){
    order.append(second.substring(j));
    break;
   }else if( j == second.length() ){
    order.append(first.substring(i) );
    break;
   }else if( first.charAt(i)=='M' && second.charAt(j)=='M' ){
    order.append("M");
    i++;
   }else if( first.charAt(i)=='W' && second.charAt(j)=='W' ){
    order.append("W");
    i++;
   }else if( first.charAt(i)=='W' && second.charAt(j)=='M' ){
    order.append("W");
    i++;
   }else if( first.charAt(i)=='M' && second.charAt(j)=='W' ){
    order.append("W");
    j++;
   }
  }
  return order.toString();
 }
}

得点は186.67、中央値は約183点。ちなみに、Chivalryというのは、騎士道精神という意味らしいです。

TopCoder SRM212 Div2 250Pts

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

問題は5つのサイコロを使うYahtzee(ヤッツイー)というゲームの最初の点数計算についての課題である。サイコロを転がして、値を選び、その値が出たサイコロはアクティブになる。点数はアクティブなサイコロの目の値で決まる。例えばサイコロの目が2,2,3,5,4と出た場合、2をアクティブにすると2+2=4点、5をアクティブにすると5点となる。

サイコロを振った時に上に出た値の入った配列toss[]が与えられたときに、それらから得られるスコアの最大値を返すメソッドを作成せよ。なお、サイコロは5つで、サイコロの目の値は1から6の整数であるものとする。

私の解答は以下の通り。

public class YahtzeeScore {
 public int maxPoints(int[] toss) {
  int max = -1;
  for( int i=1 ; i<=6 ; i++ ){
   int tmp = 0;
   for( int j=0 ; j<toss.length ; j++ ){
    if( toss[j] == i ) tmp++;
   }
   if( tmp*i > max ) max = tmp*i;
  }
  return max;
 }
}

得点は247.01/250、中央値は232.5点。SRM212以前にも出題されている過去問のようです。

Javaの私的まとめ4

Javaのお勉強その4

1. クラスの書き方
   

   クラスの修飾子はpublic、abstract、finalの3種類ある
   

   クラスの書き方は次の通り。5種類あるが、すべてを使う必要はない。
   

   public class Car{
    int fuel=50; // フィールド
    {...} // インスタンス初期化子
    static {...} // 静的初期化子
    Car(){...} // コンストラクタ
    void run(){...} // メソッド
   }

   静的初期化子は、クラスがJava Virtual Machineにロードされるときに実行される。
   

   インスタンス初期化子は、オブジェクトが生成されるときに実行される。
   

   インスタンスを生成するには、Car mycar = new Car();とする。
   

2. 継承
   

   継承によってクラスの機能を拡張できる。基のクラスをスーパークラス、継承して作るクラスをサブクラスという。インタフェースも継承により拡張可能である。
   

   拡張するにはextendsというキーワードを用いる。以下の例ではCarクラスを継承してpatrolCarクラスを作成している。
   

   public class patrolCar extends Car{
    // コンストラクタやメソッドを記述
   }
   

   サブクラスでスーパークラスにあるフィールドやメソッドを宣言できる。サブクラスでその名前を使うと、サブクラスで定義されたものになる。スーパークラスのものにアクセスしたい場合は、"super."を付ければよい。
   

   サブクラスでスーパークラスにあるアクセス可能なメソッドを再定義することをオーバーライドという。
   

   オブジェクトを参照する変数に対し、変数.フィールドとすると、変数の型のフィールドを意味する。staticがついていないメソッドの場合、変数.メソッドは変数の型ではなく、オブジェクトの型のメソッドが呼ばれる。
   

3. final
   

   finalのついた変数は、1回だけ値を与えることができる。以後変更はできない。クラスや配列でも同様。他のオブジェクトを指すようにする変更はできない。ただし、オブジェクトのデータを変更することは可能である。
   

   staticのついていないフィールドは、定義の場所で初期化する以外にコンストラクタや、インスタンス初期化子{...}で初期化する方法がある。staticのついたメソッドは、静的初期化子( static {...} )で初期化することもできる。
   

   finalのついたメソッドのオーバーライドは不可能である。
   

   finalのついたクラスのサブクラスは作成不可能である。
   

TopCoder SRM211 Div2 400Pts

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

candidateに最も近い単語をdictionary[]から選び、その単語のインデックスを返すメソッドを作成する。単語の近さというのは、candidateとdictionary[i]の単語の文字を先頭から順番に比較したときに、一致した回数で定義する。candidateとdictionary[]の単語は長さはすべて同じであるものとする。また、登場する文字はa-zの小文字のアルファベットに限る。1文字もdictionary[]中に一致するものがなければ-1を返すようにせよ。マッチした回数が最大の単語が複数ある場合は、dictionary[]中で先に出てきた単語のインデックスを返すようにする。

私の解答は以下の通り。

public class grafixCorrupt {
 public int selectWord(String[] dictionary, String candidate) {
  boolean nomatch = true;
  int[] nmatch = new int[dictionary.length]; // 要素はすべて0で初期化される
  for( int i=0 ; i<dictionary.length ; i++ ){
   for( int j=0 ; j<dictionary[i].length() ; j++ ){
    // 単語中の文字が一致した回数をカウント
    if( dictionary[i].charAt(j) == candidate.charAt(j) ){
     nomatch = false; // 何度もfalseで上書きしているが問題ない
     nmatch[i]++;
    }
   }
  }
  if( nomatch ) return -1; // dictionary中の単語にcandidateが全く一致しない場合

  int max = -1;
  int idx = -1;
  // 前半のマッチした回数カウントから、もっともマッチした単語を調べる
  for( int i=0 ; i<nmatch.length ; i++ ){
   if( nmatch[i] > max ){ // 先に出てきた単語がidxに入るようにする
    max = nmatch[i];
    idx = i;
   }
  }
  return idx;
 }
}

得点は331.14/400、中央値は約213点。解答提出者のみに限った正解率は約91%。4回目のチャレンジで初めてLevel2の問題を解くことに成功した。

TopCoder SRM211 Div2 300Pts

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

マウスをクリックしたときの、マウスの行方向と列方向の座標値が配列になって与えられる。mouseRows[]とmouseCols[]が座標の配列で、i番目の要素がi番目のクリックに対応しているものとする。何番目のクリックがSaveという画像の中にあったかを示す整数型の配列を返すメソッドを作成せよ。なお、画像の座標は行方向は20以上39以下、列方向は50以上99以下になっている。

私の解答は以下の通り。

public class grafixClick {
 public int[] checkSaveButton(int[] mouseRows, int[] mouseCols) {
  int[] inButton = new int[mouseRows.length];
  int nIn = 0;
  for( int i=0 ; i<mouseRows.length ; i++ ){
   inButton[i] = -1;
   if( mouseRows[i] >= 20 && mouseRows[i] <=39 && 
       mouseCols[i] >= 50 && mouseCols[i] <= 99 ){
    inButton[i] = i;
    nIn++;
   }
  }
  int[] ret = new int[nIn];
  int idx = 0;
  for( int i=0 ; i<inButton.length ; i++ ){
   if( inButton[i] >= 0 ){
    ret[idx] = inButton[i];
    idx++;
   }
  }
  return ret;
 }
}

得点は254.91/300、中央値は約265点、正解率は93.85%。配列のみを用いて解いているが、リストを利用してaddで条件にあてはまるインデックスの集合を求めて、それを配列に入れなおして配列を返すという手法もあるようだ。

7月の学習記録

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

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

クラスタリング、分類について学習。SVMは発想は単純だが数式が難しい...

ソフトウェアテスト HAYST法入門(pp.140～読了)

状態遷移テストは2ステップの遷移をテストするとよいそうです。

よくわかる実験計画法(pp.21～135)

主にデータの値の分解と交互作用の意味について学習。

入門自然言語処理(pp.1～40)

簡単なPythonの使い方について学習