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;
 }
}