2011年9月29日木曜日

TopCoder SRM255 Div2 250Pts

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

数値を文字列としてソートしてしまうというのは、よくある話である。ここでは、sequence[]という、文字列を昇順で並べた文字列型配列が引数として与えられる(ソートの方法は辞書式順序のルールに従う)。これに代わって、配列の要素を数値と見なして配列を昇順にソートしたときの結果を返せ。返す型は文字列型であることに注意。

私の解答はこちら。

import java.util.Arrays;

public class SequenceOfNumbers {
 public String[] rearrange(String[] sequence) {
  int[] intSeq = new int[sequence.length];
  for( int i=0 ; i<intSeq.length ; i++ ){
   intSeq[i] = Integer.parseInt(sequence[i]);
  }
  Arrays.sort(intSeq);
  String[] ret= new String[intSeq.length];
  for( int i=0 ; i<ret.length ; i++ ){
   ret[i] = Integer.toString(intSeq[i]);
  }
  return ret;
 }
}

得点は245.26/250。コンパイルエラー・バグなしの一発回答。素直に実装するだけ。

2011年9月28日水曜日

TopCoder SRM254 Div2 250Pts

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

conflicts[]という文字列型配列が与えられる。配列の各要素は多人数が参加するゲームの1人のプレーヤーを表している。i番目の要素がプレーヤーiを表し、プレーヤーiを表す配列のj番目の要素はiがjに対し、勝つのであれば'W'、同点なら'T'、負けなら'L'という文字になる。やるべきことは、各プレーヤーが他のプレーヤーに対し、少なくともp%勝ち、q%負けるということを保証することである。もしこれらの要求が満たされないプレーヤーがいれば、0を始点としたインデックスでプレーヤーを表したときに、初めて現れる要求を満たさないプレーヤーのインデックスを返し、全員が要求を満たすのであれば、-1を返す。もし全体でN人いるようであれば、少なくともWはceil((N-1)*p/100)(小数点以下切り上げを行った整数のこと)の割合でプレーヤーiを表す配列の要素中に'W'という文字が現れることになる。負けを表す式も同様である。

また、配列全体の要素を数えるとWとLは同数である。また、プレーヤーiのi番目の要素は常にTである(自分自身と戦うわけではない)。

私の解答はこちら。

public class BalancedGame {
 public int result(String[] conflicts, int p, int q) {
  int nPlayer = conflicts.length;
  for( int i=0 ; i<nPlayer ; i++ ){
   int nW = 0;
   int nL = 0;
   for( int j=0 ; j<conflicts[i].length() ; j++ ){
    if( conflicts[i].charAt(j) == 'W' ){
     nW++;
    }else if( conflicts[i].charAt(j) == 'L' ){
     nL++;
    }
   }
   if( (double)nW/(nPlayer-1) < p/100.0 || (double)nL/(nPlayer-1) < q/100.0 ) return i;
  }
  return -1;
 }
}

先頭のプレーヤーから順番にWとLを数えて、条件を満たさないプレーヤーのインデックスを返せばよい。割り算はnPlayer-1であることに注意がいる。当初nPlayerで割っていたので、1回システムテストで落とされてしまった。

2011年9月25日日曜日

TopCoder SRM253 Div2 250Pts

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

長方形の物体といくつかのサイズが異なる箱が与えられる(この問題では箱の高さは考慮しない)。あたなは、物体を詰めるのに十分なもっとも小さい面積の箱を知りたい。箱に物体を詰めるとき、辺は箱と平行にしなければならない。つまり、物体は0度、90度、180度、270度にしか回転させられない(実際には0度と90度だけ考えればよいのは明らかだが)。

物体の縦横のサイズを表す整数値objWidth、objLengthと箱の縦横のサイズを表すboxWidth[]、boxLength[]が与えられる。2つの配列のi番目の要素がi番目の箱のサイズを表している。物体が収まるもっとも面積が小さい箱の、その面積を返せ。どの箱にも収まらないなら-1を返せ。

私の解答はこちら。

public class ObjectPacking {

 public int smallBox(int objWidth, int objLength, int[] boxWidth, int[] boxLength) {
  int s = Math.min(objWidth, objLength); // 物体の短い辺
  int l = Math.max(objWidth, objLength); // 物体の長い辺
  int minVolume = Integer.MAX_VALUE;
  for( int i=0 ; i<boxWidth.length ; i++ ){
   int si = Math.min(boxWidth[i], boxLength[i]); // i番目の箱の短い辺
   int li = Math.max(boxWidth[i], boxLength[i]); // i番目の箱の長い辺
   if( s <= si && l <= li ){ // 箱に収まる条件
    int vol = si * li;
    if( vol < minVolume) minVolume = si*li;
   }
  }
  return minVolume == Integer.MAX_VALUE ? -1 : minVolume; // 箱に収まるものがあればminVolumeになる。
 }

}

結局、箱を回転させて収められるという制約は、物体の縦横の小さい辺と大きい辺がそれぞれ、i番目の箱の小さい辺と大きい辺に収まるという"置き換え"ができるか否かに尽きるような問題でした。

TopCoder SRM252 Div2 250Pts

今日の問題はなぜか検索をかけても出てこないのでリンクは省略。それでは、問題について説明する。

山の離れた地域で交戦中の一族がいる。軍隊をよりよい組織にするために、N個の前哨基地を丘に沿ってまっすぐに建てた。各前哨基地は怪しい動きの監視と、非常事態には知らせを広める役割がある。一旦基地が警報を受け取ると、メッセンジャーは継続的にアルプフォンを吹き、他の基地に警報を知らせる。二つの隣り合う基地に音が届くのに、ちょうど1単位の時間がかかる。ある基地と最も近い警報源からの距離がxだけ間が離れていれば、x単位時間音が届くのに時間がかかるということになる。

いくつかの基地が刑法を鳴らしたとしよう。あなたは、その他のすべての基地が知らせを受け取るのに何単位時間かかるかということを決めるのが課題である。outposts[]というN個の基地の状態を表す文字列が引数で与えられる。i番目の文字がi番目の基地であり、xという文字が警報を、-が静かな状態を表すものとする。

例えば、"--x-x---"であれば、3を返す。これは一番右の-にxからの警報が届くのに3単位時間かかるからである。

私の解答はこちら。

public class WarCry {
 public int alertTime(String outposts) {
  char[] line = outposts.toCharArray();
  int[] dist = new int[line.length];
  // とりうる距離の最大値は配列の長さ-1なので、それ以上に大きい値で初期化
  for( int i=0 ; i<dist.length ; i++ ){
   dist[i] = dist.length;
  }
  // 各xからの距離(インデックスの差)を計算する
  // xが出てきたときが更新するタイミングになる
  // ループの中で距離は最小値に更新されていく。
  for( int i=0 ; i<line.length ; i++ ){
   if( line[i] == 'x' ){
    for( int j=0 ; j<line.length ; j++){
     int tmpDist = Math.abs(i-j);
     if( tmpDist < dist[j] ){
      dist[j] = tmpDist;
     }
    }
   }
  }
  // 全体で最も警報源から離れている場所を調べる
  int maxDist = -1;
  for( int i=0 ; i<dist.length ; i++ ){
   if( dist[i] > maxDist ) maxDist = dist[i];
  }
  return maxDist;
 }
}

得点は220.84/250。xが出るたびに何度も更新しないといけないので、もう少しうまくかけないかなと思いました。一番簡単な解答ではあると思います。

2011年9月24日土曜日

TopCoder SRM251 Div2 250Pts

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

国の大統領になる二人の候補者によるキャンペーンが行われている。新聞の世論調査では、各州で何パーセントの人が各候補者に投票するかということがはっきりしている。候補者1は最後の宣伝をしたく、どこの州に行くべきか知る必要がある。likelihoods[]という文字列型配列が与えられる。各文字列は1つの州を表している。文字列は1と2からなり、1は1に投票する数を、2は2に投票する数を表している。最も1に対する投票率が低い州のインデックスを返せ(インデックスは0から始まる)。もし最低投票率の州が複数あるようであれば、最初に現れた州のインデックスを返すようにせよ。

私の解答はこちら。

public class Elections {
 public int visit(String[] likelihoods) {
  int visit = 0;
  double ratio = 1.0;
  for( int i=0 ; i<likelihoods.length ; i++ ){
   char[] aState = likelihoods[i].toCharArray();
   int n1 = 0;
   for( int j=0 ; j<aState.length ; j++ ){
    if( aState[j]=='1' ) n1++;
   }
   if( (double)n1/aState.length < ratio ){
    visit = i;
    ratio = (double)n1/aState.length;
   }
  }
  return visit;
 }
}

charの配列に1文字ずつに分解するか、Stringのi番目の文字として逐一取り出す方が良いのか悩ましいところ。

2011年9月22日木曜日

TopCoder SRM250 Div2 250Pts

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

電機メーカーがあなたに抵抗の色コードを解読するプログラムを書くように呼んだ。code[]という、抵抗に刻まれた3つの色帯が文字列型配列として与えられる。その抵抗が表す抵抗値(オーム)を返せ。最初の2つの色が値を、最後の1つの色が先頭2つの値に対して掛ける値を示している。

例えば、code[]={"red","brown","red"};であれば、返すべき抵抗値は21*10^2=2100になる。

抵抗に用いる色については一般的な抵抗と同じである。例えば、こちらを参考されたい。

私の解答はこちら。

public class ColorCode {
 public long getOhms(String[] code) {
  String[] color = {"black","brown","red","orange","yellow",
                    "green","blue","violet","grey","white"};
  int val = 0;
  for( int i=0 ; i<2 ; i++ ){
   for( int j=0 ; j<color.length ; j++){
    if( code[i].equals(color[j]) ){
     val = val*10 + j;
     break;
    }
   }
  }
  int p = 0;
  for( int i=0 ; i<color.length ; i++ ){
   if( code[2].equals(color[i])){
    p = i;
    break;
   }
  }
  return (long)(val*Math.pow(10,p));
 }

}

得点は181.20/250、中央値は約195点。方針を立てるのは容易でしたが、とんでもない勘違いで、大幅にタイムロスしてしまいました。

TopCoder SRM249 Div2 250Pts

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

チャットの会話を受け取った。会話の1要素は1行に対応する。nameという人が何回発言したかを知りたい。このために、nameで会話が始まり、直後にコロンが来た回数を数える。この比較は大文字と小文字を区別するものとする。

私の解答はこちら。

public class ChatTranscript {
 public int howMany(String[] transcript, String name) {
  int cnt = 0;
  // コロンで会話のテキストを区切って、先頭の要素とnameを比較する
  for( int i=0 ; i<transcript.length ; i++ ){
   if( transcript[i].contains(":") == false) continue;
   String[] sp = transcript[i].split(":");
   if( sp.length>0 && sp[0].equals(name) ) cnt++;
  }
  return cnt;
 }
}

得点は約85点。splitした後のif文でsp!=nullなどと書いていたのですが、提出までできてもシステムテストで落とされること数回。ようやく解答にたどりついたけど、何がダメなのか...

2011年9月19日月曜日

Javaのthreadの呼び出し方2

複数のスレッドが動いているときに、1つのスレッドがある変数Aをいじっている最中に、スレッドが切り替わって別のスレッドからAを書き換えるようなことが起きると不便なことがある。勝手にスレッドは動作するため、スレッドを制御する方法としてsynchronizedという修飾子を用いた、排他制御の仕組みが用意されている。排他制御はその名の通り、スレッドが実行している間、synchronized修飾子がかかっている箇所にロックをかけて、他のスレッドはロックがかかっているうちはアクセスができないようにすることである。

以下の例では、複数のスレッドが、計算を繰り返し、その結果をBadのvalueに記録するというものである。スレッド1が1を足して、スレッド1が抜ける前にスレッド2が1を足すということになると、エラーで停止してしまう。排他制御を行わないと、スレッド1がadderを実行している最中に、スレッド2がadderを実行してしまうのである。

BadTest.javaの中身

public class BadTest extends Thread{
 Bad test;
 public BadTest(Bad bd){
  this.test = bd;
 }
 public void run(){
  for( int i=0 ; i<10 ; i++ ){
   test.adder(1);
  }
 }
 public static void main(String[] args){
  Bad bd = new Bad();
  new BadTest(bd).start();
  new BadTest(bd).start();
 }
}

Bad.javaの中身

public class Bad{
 private int value = 0;
 public void adder(int v){
  int tmpValue = value;
  System.out.println(Thread.currentThread() + " is at adder");
  value += v;
  if( tmpValue + v != value ){ // 単純に足しただけだが...
   System.out.println(Thread.currentThread() + " conflicted!");
   System.exit(-1); // 異常終了
  }
  System.out.println(Thread.currentThread() + " get out of adder");
 }
}

上のコードをコンパイルして実行すると次のようになり、矛盾が発生していることが分かる。

d:\java>javac BadTest.java Bad.java // ファイルをまたいでいるので、まとめてコンパイル
javac BadTest.java Bad.java

d:\java>java BadTest
java BadTest
Thread[Thread-0,5,main] is at adder
Thread[Thread-1,5,main] is at adder
Thread[Thread-0,5,main] get out of adder
Thread[Thread-1,5,main] conflicted! // ここで矛盾
Thread[Thread-0,5,main] is at adder
Thread[Thread-0,5,main] get out of adder

この矛盾を解決するのがsynchronized修飾子である。synchronizedは以下のようにadder関数に修飾するとよい。

public synchronized void adder(int v)

これによって、一つのスレッドがadder関数を実行している間、同じインスタンスを利用する別スレッドからはadder関数が利用できなくなり、矛盾(=conflicted!の表示)は発生しなくなる。また、synchronized修飾子はメソッドにもブロックにもかけられる。ブロックにsynchronized修飾子をつける場合は、ロックをかけるオブジェクトを指定する必要がある。

public void adder(int v){
 synchronized(this){
  ...
 }
}

TopCoder SRM248 Div2 250Pts

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

英語では音節は遮られない音の集まりとゆるやかに定義される。発音された数で音節を定義するということもある。ただ、一般には単語の音節を数えるプログラムを書くのは容易ではない。ここでは、音節を数えるのに次の手続きを踏むものとする。それはA、E、I、O、Uという母音の集まりを1つの音節とし、単語の音節の総数に1つ加えるということである。
母音の集合は子音(母音でない21の文字)、もしくは単語の先頭または最後尾によって区切られる。例えば、FOOBARは2つの音節がある。OO、Aの二つが音節になる。

inputという文字列が引数に与えられたときに、上の音節の数え方で、単語にいくつ音節が含まれているかを返すメソッドを作成せよ。

私の解答はこちら。

public class SyllableCounter {
 public int countSyllables(String word) {
  boolean inVowel = false; // 注目している文字が母音ならtrue
  boolean prev = false; // 直前の文字が母音ならtrue
  int cnt = 0; // 音節の登場回数
  for( int i=0 ; i<word.length() ; i++ ){
   if( word.charAt(i) == 'A' || word.charAt(i) == 'I' ||
    word.charAt(i) == 'U' || word.charAt(i) == 'E' ||
    word.charAt(i) == 'O' ){
    inVowel = true;
   }else{
    inVowel = false;
   }
   if( inVowel == true && prev == false ){
    cnt++; // 新たに母音が現れた
   }
   prev = inVowel; // 注目している文字は注目する文字の直前の文字になる
  }
  return cnt;
 }
}

得点は238.15/250。C言語にはないbooleanが大活躍するプログラムですね。

2011年9月18日日曜日

TopCoder SRM247 Div2 500Pts

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

互いに素な整数から0と1の間の既約分数を作成することができる(つまり無限に分数が存在していることを示している)。それらを表す時は、通常次のように表す。

1/2 1/3 2/3 1/4 3/4 1/5 2/5 3/5 4/5 1/6 5/6 1/7 ...

2/4というのは数列中にはないが、これは1/2に約分できるからである。既約分数が与えられたときに、上のような順序の数列の何番目に現れるかということが知りたい。例えば、1/3であれば2というインデックスが知りたい。FracCountという分子と分母の互いに素な整数が与えられたときに、その2数から作られる分数が何番目に現れるかを返すメソッドを作成せよ。

私の解答はこちら。

public class FracCount {
 public int position(int numerator, int denominator) {
  int idx = 0;
  for( int i=2 ; i<=denominator ; i++ ){
   for( int j=1 ; j<i ; j++ ){
    // 最大公約数が1であれば、約分不可なので、初登場の分数になる
    if( gcd(i,j) == 1 ) idx++;
    // 求めている分数が現れた時点で処理は終了
    if( i==denominator && j==numerator)break;
   }
  }
  return idx;
 }
 private int gcd(int a, int b){
     return b == 0 ? a : gcd(b, a % b);
 }
}

得点は419.40/500。500点問題にしては、全体の解答者が50%と高めだったので解いてみたところ、予想よりすんなりと解けました。breakに関連した処理を入れ忘れて再提出したのですけどね。

TopCoder SRM247 Div2 250Pts

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

ユークリッド幾何において、三角形は角度で3種類に分類される。もし、三角形のすべての角が90度以下であれば、鋭角三角形である。もし1つの角が90度を超えていれば鈍角三角形である。もし90度の角があれば直角三角形という。また、3つの整数が与えられたとき、その数で三角形を構成できないこともある。それは1つの辺の長さが他の2辺の長さの和以上に長いときである。端点がくっつけられなくなり、三角形が構成できなくなる。3辺が引数に与えられたときに三角形を構成できなければ"IMPOSSIBLE"、鋭角三角形であれば"ACUTE"、鈍角三角形であれば"OBTUSE"、直角三角形であれば"RIGHT"を返すメソッドを作成せよ。

私の解答はこちら。Noteの項目には判定方法が載っているので、それを活用している。Noteが与えられなければ、余弦定理で3つの角度をすべて求めて判定しようと考えていました。

import java.util.Arrays;

public class TriangleType {
 public String type(int a, int b, int c) {
  int[] array = {a,b,c};
  Arrays.sort(array);
  if( array[0]+array[1] <= array[2] ){
   return "IMPOSSIBLE";
  }else if( array[0]*array[0]+array[1]*array[1] < array[2]*array[2]){
   return "OBTUSE";
  }else if( array[0]*array[0]+array[1]*array[1] > array[2]*array[2] ){
   return "ACUTE";
  }else{
   return "RIGHT";
  }
 }

}

得点は238.84/250なのですが、提出したコードが汚いので、ちょっとだけ改良しました。ソート前のa、b、cだけで可能な限り判別しようとしたのですが、a、b、cをソートした配列だけでコードを書いてみたところ、読みやすいので、それを採用して載せました。途中から判定方法を変えず、一貫性があるから読みやすくなったのだと思います。

2011年9月17日土曜日

TopCoder SRM246 Div2 250Pts

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

新しい計算ソフトウェアの開発をしている。ソフトウェアのテストの段階において、小数点の文字が場合によっては違うというということに気付いた。さらに、テストケースにおいて、役に立たない空白文字が含まれていることもある。そのような数値はフォーマットを統一したい。数値はnumbers[]という文字列型の配列で表されている。空白(アスキーコードで32)をすべて取り除き、数字の桁でない文字は"."に置き換えよ。それ以外は変更を加えてはならない。

なお、numbers[]は少なくとも1つ以上の桁(数値)を持ち、空白でも数字でもない文字は高々1であるものとする。本当はもう少し条件があるのだが、実装上はこれで問題無い。

私の解答はこちら。

public class CalcTest {
 public String[] uniform(String[] numbers) {
  for( int i=0 ; i<numbers.length ; i++ ){
   numbers[i] = numbers[i].replaceAll(" ", ""); // 空白は取り除く
   // 数字でない文字は.に変換。[^0-9]は\\Dに代用可能
   numbers[i] = numbers[i].replaceAll("[^0-9]", "."); 
  }
  return numbers;
 }
}

得点は242.70/250、中央値は約226点。否定の正規表現を調べながら解きました。Javaの利用者はこのような正規表現による置換を利用して解答をしている人がちらほらといました。

2011年9月15日木曜日

TopCoder SRM245 Div2 250Pts

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

ストレートの数に関するトランプゲームで遊んでいる。値が連続したカードの集合が手の強さを決める。hand[]という整数型配列のi番目の値が手の中のiという値の数を表している。長さkのストレートの数を返せ。

例えば、hand[] = { 0, 3, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0 }という手が与えられると、k=2のストレートの数(強さ)は5になる。これは2のカードと3のカードの組が3通り、3のカードと4のカードの組が2通りあるので、長さ2のストレートの数は3+2=5になるわけである。

私の解答はこちら。

public class Straights {
 public int howMany(int[] hand, int k) {
  int cnt = 0;
  for( int i=0 ; i<hand.length-k+1 ; i++ ){
   int perm = hand[i];
   for( int j=1 ; j<k ; j++ ){
    perm *= hand[i+j];
   }
   cnt += perm;
  }
  return cnt;
 }
}

得点は229.00/250、中央値は約190点。英語の読解と実装に同じぐらいの時間かかったかな?IndexOutOfBoundsExceptionにだけ注意しましょう(コンパイル後のテストでhand[i+j]で何度か例外を投げられてしまった)。

2011年9月14日水曜日

Javaのthreadの呼び出し方1

Javaのスレッドの基本的な呼び出し方法についてのまとめ。スレッドというのは複数の動作を平行して行うようにするための仕組みである。呼び出し方は大きく2種類ある。

  1. Threadクラスの拡張
  2. Runnableインタフェースの実装

スレッドというのは、特に指定がないと実行されるタイミングを制御することはできない(synchronizedなどを付けない限り)。例えば、Threadクラスを拡張して作成した次のスレッドを含むプログラムを実行すると、mainと書かれた行とrunと書かれた行はランダムに現れることが確認できる。runとmainが交互に現れることや、runが先に10行現れてmainが10行現れるといったことには必ずしもならない。

class countTen1 extends Thread{
 public static void main(String[] args){
  countTen1 ct = new countTen1(); // スレッドを実行するインスタンスを作成
  ct.start(); // スレッドの実行開始
  for( int i=0 ; i<10 ; i++ ){
   System.out.println("main i = " + i);
  }
 }
 public void run(){
  for( int i=0 ; i<10 ; i++ ){
   System.out.println("run i = " + i);
  }
 }
}

参考までに、手持ちの環境で実行した結果の例は次の通り。最後にmainとrunが連続で発生しており、規則性がないということが分かる。

d:\java>java countTen1
java countTen1
main i = 0
run i = 0
main i = 1
run i = 1
main i = 2
run i = 2
main i = 3
run i = 3
main i = 4
run i = 4
main i = 5
run i = 5
main i = 6
run i = 6
main i = 7
run i = 7
main i = 8
main i = 9
run i = 8
run i = 9

スレッドの実行はスレッドクラスのインスタンスが持つstartメソッドで開始する。また、スレッドの実行内容はrunメソッドに記述する。このとき、呼び出し方は必ずpublic void run()になる。

次にRunnableインタフェースを実装するスレッドの作成方法を示す。上のスレッドを拡張した場合と同じように動作するプログラムである。

class countTen2 implements Runnable{
 public static void main(String[] args){
  countTen2 ct = new countTen2();
  // スレッドインスタンスの生成時にRunnableを実装したインスタンスを渡す
  Thread t = new Thread(ct);
  t.start(); // スレッドの実行開始
  for( int i=0 ; i<10 ; i++ ){
   System.out.println("main i = " + i);
  }
 }
 public void run(){
  for( int i=0 ; i<10 ; i++ ){
   System.out.println("run i = " + i);
  }
 }
}

特徴は、Runnableインタフェースを実装したクラスはスレッドクラスではないので、スレッドクラスのインスタンスを作成するときに引数にクラスを入れてしまうということである。

2種類のスレッドの呼び出し方の使い分け方は、クラスの拡張を繰り返して作成された下の階層に属するようなクラスはRunnableを利用し、手軽にスレッドを利用したいのであれば、Threadを拡張して利用するということになる。

TopCoder SRM231 Div2 450Pts

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

多くの画像編集プログラムでは、二つの画像を縫い合わせて大きな画像を作るということができる。この問題では、二つの画像を表す文字列が与えられる。文字列はビットマップ(非圧縮画像ですね)を表しており、文字列のi番目の要素の値jというのは、画像においてはi行j列の色を表している。二つのイメージを縫い合わせることを行え。この問題では画像A[]を画像B[]の左に置き、Aの右側とBの左側を重ねる。明らかな人工物であることを防ぐために、縫い合わせた領域はAからBに向けて徐々に色が混ざるようにしたい。重なっている領域の左からi番目(i=1から始まるとする)の値は次式のようになる。

((overlap+1-i)*a+(i*b))/(overlap+1)

ここで、aとbはそれぞれAとBの画素値である。overlapは重ねた画素数である。したがって、重なっている領域の一番左の画素値は次のようになる。

(overlap*a+b)/(overlap+1).

なお、どの場合でも値は最も近い整数値に変換せよ(四捨五入せよ)。画素値は文字のASCIIコードの値で与えられる。

私の解答はこちら。

public class Stitch {
 public String[] stitch(String[] A, String[] B, int overlap) {
  String[] blended = new String[A.length];
  for( int i=0 ; i<A.length ; i++ ){
   blended[i] = A[i].substring(0, A[i].length()-overlap);
   for( int j=1 ; j<=overlap ; j++ ){
    double val = ((overlap+1.0-j)*A[i].charAt(A[i].length()-overlap+j-1)+j*B[i].charAt(j-1))
      /(overlap+1);
    char cval = (char)Math.round(val);
    blended[i] += cval;
   }
   blended[i] += B[i].substring(overlap);
  }
  return blended;
 }

}

2011年9月13日火曜日

TopCoder SRM244 Div2 400Pts

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

典型的な電話機の番号の配列は次の通りである。

123
456
789
*0#

指の動きの量を二つのボタンのマンハッタン距離で定義する。電話番号を表す文字列が与えられたときに、電話番号を押すのに必要な指の動きの最小値を返せ。なお、指の初期位置は5に設定されているものとする。

私の解答はこちら。

public class PhonePad {
 public int fingerMovement(String phoneNumber) {
  // 2次元配列の座標で番号を表現
  String[][] pos = {{"1","2","3"},{"4","5","6"},{"7","8","9"},{"*","0","#"}};
  // 1文字ずつに分解
  String[] pushedArray = phoneNumber.split("");
  // 直前の指の座標、yが縦方向、xが横方向(画像処理的に)
  int x = 1;
  int y = 1;
  int totalMove = 0; // 指の動いた距離の合計
  for( int i=0 ; i<pushedArray.length ; i++ ){
   String current = pushedArray[i];
   for( int j=0 ; j<pos.length ; j++ ){
    for( int k=0 ; k<pos[j].length ; k++ ){
     if( pos[j][k].equals(current)){
      int aMove = Math.abs(y-j) + Math.abs(x-k);
      totalMove += aMove;
      y = j;
      x = k;
     }
    }
   }
  }
  return totalMove;
 }

}

得点は328.80/400、提出者の正解率は約90%。マンハッタン距離をどうやって表すかということがポイントで、2次元配列にすれば、インデックスの差がそのまま距離にできるというところがポイントだと思いました。レベル2の問題にしては簡単だったと思います。

2011年9月11日日曜日

TopCoder SRM243 Div2 250Pts

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

あなたはいくつかアルゴリズムのテストをしており、一番早いものを見つけたいと思っている。アルゴリズムの計算量というのは、三つからなる。constant、power、logPowerである。これらは配列で与えられており、i番目のアルゴリズムは、次式で与えられる。

constant[i]*N^power[i]*log(N)^logPower[i]

上の3つの配列と、サイズを表すNが与えられたときに最も速い(計算量が少ない)アルゴリズムのインデックスを返せ(先頭は0から始まるものとして)。タイのものがある場合には、インデックスが最も小さいものを返せ。

私の解答はこちら。

public class ComputationalComplexity {
 public int fastestAlgo(int[] constant, int[] power, int[] logPower, int N) {
  // こういう風に定義するのもあり。こちらを利用する場合、int i=0からループを開始することになる。
  // 解答の美しさを考慮すると、minはコメントにあるものの方が好きです。
  // double min = Double.POSITIVE_INFINITY;
  double min = constant[0]*Math.pow(N, power[0])*Math.pow(Math.log(N),logPower[0]);
  int idx = 0;
  for( int i=1 ; i<constant.length ; i++ ){
   double ith = constant[i]*Math.pow(N, power[i])*Math.pow(Math.log(N),logPower[i]);
   if( ith < min ){
    idx = i;
    min = ith;
   }
  }
  return idx;
 }
}

得点は205.78/250。数式をコードに落とすのに間違いがあり、解答にやや時間がかかってしまった。次の問題はSRM182 Div2 300Ptsと同じなので省略。

TopCoder SRM242 Div2 250Pts

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

ゲームで二つのチームにメンバーを分けるということをしたい。分けるためにまずはキャプテンを決める。そして交互にチームを作るためにプレーヤーを選択する。それぞれのターンでは一人ずつメンバーを選ぶ。キャプテンは強いメンバーが欲しいので、残っている中でベストなプレーヤーを選ぶ。プレーヤの強さはstrengths[]という配列で与えられており、値が大きいほど良いプレーヤーである。全員選び終えたところで、チームの強さというのはプレーヤーの強さの総和で計算される。二つのチームの強さの絶対値を返せ。

人数が奇数の時は先に選ぶキャプテンがとることになるため、2チームの人数は同じとは限らないことに注意。

私の解答はこちら。

import java.util.*;

public class TeamSplit {
 public int difference(int[] strengths) {
  int diff = 0;
  Arrays.sort(strengths);
  for( int i=0 ; i<strengths.length ; i++ ){
   if( i % 2 == 0 ){
    diff += strengths[strengths.length-i-1];
   }else{
    diff -= strengths[strengths.length-i-1];
   }
  }
  return diff;
 }
}

得点は236.44/250。ソートを楽にする方法がArrays.sortだった。最初から逆順から並べるにはコンパレータ使わないとダメかな?

TopCoder SRM241 Div2 250Pts

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

ブラックジャックでは、プレーヤーはディーラーよりも数字が大きいか、もしくはディーラーがバースト(21を超える)し、プレーヤーが21を超えない場合、掛け金と合わせて、同じ額を余分に受け取ることができる。もし、プレーヤーが21以下で、ディーラーと同じ数になったらプッシュという状態になり。掛け金はそのままになる(プラスマイナス0の状態)。もしプレーヤーがディーラーの数より小さいか、21を超えてしまった場合、掛け金を失う。

ブラックジャックというのは21ポイントの状態で、すべての手を負かす。この場合、プレーヤーは掛け金の1.5倍を得ることができる。もし、プレーヤーもディーラーもブラックジャックであれば、プッシュになる。もし、ディーラーがブラックジャックで、プレーヤーがブラックジャックでないものの21であった場合は、ディーラーの勝ちで、プレーヤーは掛け金を失う。

プレーヤーの掛け金betと、ディーラーのスコアdealer、プレーヤーのスコアplayerと、2人がブラックジャックかそうでないかを表す状態(dealerBlackjack、blackjack)が与えられている。ブラックジャックである状態は1、そうでない状態は0で表す。このとき、プレーヤがの収支を返せ。勝てばプラス、負ければマイナス、プッシュは0になる。

私の解答はこちら。

public class BlackjackWinner {
 public int winnings(int bet, int dealer, int dealerBlackjack, int player, int blackjack) {
  if( dealerBlackjack == 0 && blackjack == 1){
   // プレーヤーのみブラックジャック
   return (int)(bet*1.5); // 掛け金は常に偶数
  }else if( dealerBlackjack == 1 && blackjack == 1){
   return 0; // 両者ブラックジャック(プッシュになる)
  }else if( dealerBlackjack == 1 && blackjack == 0 ){
   return -bet; // ディーラーのみブラックジャック
  }else{
   // どちらもブラックジャックではない
   if( player > 21 ){ // プレーヤーがバースト
    return -bet;
   }else if( player <= 21 && dealer > 21 ){
    return bet; // ディーラーがバースト
   }else if( player <= 21 && dealer <= 21 ){
    // どちらもバーストしてない
    if( player > dealer  ) return bet;
    if( player == dealer ) return 0;
    if( player < dealer  ) return -bet;
   }
  }
  return 0;
 }
}

得点は183.25/250。場合分けが細かいですね。

TopCoder SRM240 Div2 250Pts

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

ピーターは難しい単語の発音に難がある。特に子音が3つ以上連続する単語が発音できない(streetとか)。さらに、異なる母音が2つ以上続いている単語も発音できない(goalとか)。同じ母音が2つ続いているものについては発音できる(needとか)。

母音はa、i、u、e、oであり、その他は子音である。単語の集まりwords[]が与えられる。もしピーターがwords[]をすべて発音できるのであれば空文字を返せ。そうでなければ、発音できないもののうち、最初に現れたものを返せ。

私の解答はこちら。

public class Pronunciation {
 public String canPronounce(String[] words) {
  for( int i=0 ; i<words.length ; i++ ){
   int consonants = 0;
   int vowel = 0;
   char prevAlphabet = '\0';
   for( int j=0 ; j<words[i].length() ; j++ ){
    // 母音の処理
    char currentAlphabet = words[i].toLowerCase().charAt(j);
    if( currentAlphabet == 'a' ||
     currentAlphabet == 'i' ||
     currentAlphabet == 'u' ||
     currentAlphabet == 'e' ||
     currentAlphabet == 'o' ){
     consonants = 0;
     vowel++;
     if( vowel >= 2 && prevAlphabet != currentAlphabet ){
      return words[i];
     }
     prevAlphabet = currentAlphabet;
    }else{ // 子音の処理
     consonants++;
     vowel = 0;
     if( consonants >= 3 ){
      return words[i];
     }
    }
   }
  }
  return "";
 }

}

得点は197.52/250、中央値は82点。母音と子音に分けて処理を書くことでスムーズに実装できた。

TopCoder SRM239 Div2 300Pts

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

家族でバーベキューをし、肉は皆に1切れずつということになっていた。肉を食べる前にサッカーをしてバーベキューをする場所に戻ってきたところ、犬が肉を1切れ食べてしまっていた。そこで、長兄は投票をして、1人犬を散歩に連れて遊ばせることにし、その他の人は肉を食べるということにした。家族はn人で0からn-1の添え字で一人一人を表す。voter[]は投票者を表す配列であり、値は家族のメンバーを表す0からn-1の数字が入っている。excluded[]はバーベキューから追い出したい人を表す。こちらも家族のメンバーを表す0からn-1の数字が入っている。

バーベキューからの追い出すルールは、次のルールに従う。

  1. 最多得票者が追い出される
  2. 最多得票者数が複数いたら、最多得票者の中で最も多く投票した人が追い出される
  3. 最多投票者が複数いたら、添え字の小さい方が追い出される

このとき、追い出される人を表す添え字を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.*;
import java.lang.*;

public class Barbecue {
 public int eliminate(int n, int[] voter, int[] excluded) {
  int[] nVote = new int[n];
  int[] nVoted = new int[n];
  for( int i=0 ; i<voter.length ; i++ ){
   nVote[voter[i]]++;
   nVoted[excluded[i]]++;
  }
  int maxVoted = maxArray(nVoted);
  //int maxVoter = maxArray(nVote);
  ArrayList<Integer> maxVotedList = new ArrayList();
  ArrayList<Integer> maxVoterList = new ArrayList();
  for( int i=0 ; i<n ; i++ ){
   if( nVoted[i] == maxVoted ){
    maxVotedList.add(i);
   }
  }
  System.out.println("-------");
  for( int i=0 ; i<n ; i++ ){
   System.out.println(nVote[i]);
  }

  // 最多得票者
  if( maxVotedList.size() == 1) return maxVotedList.get(0);
  // 得票最多数がタイだった場合
  // 該当者の中で投票数が最多だった人が選ばれる
  // それでも同じなら先に出てきた人。
  Collections.sort(maxVotedList); // ソートしておく
  //ArrayList<Integer> maxVoterVotedList = new ArrayList();
  int[] candidate = new int[maxVotedList.size()];
  int idx = 0;
  for( Integer i : maxVotedList ){ // 得票を得た人を対象に出現回数を集計
   candidate[idx] = nVote[i.intValue()];
   idx++;
  }
  int maxVoter = maxArray(candidate); // 最多得票数
  boolean flg = false;
  int res = 0;
  for( int i=0 ; i<candidate.length ; i++ ){
   if( candidate[i] == maxVoter ){
    maxVoterList.add(i); // 一番投票した人一覧作成
    if( flg == false ){
     flg = true;
     res = maxVotedList.get(i);
    }
   }
  }
  return res;
 }
 private int maxArray(int a[]){
  int max = -1;
  for( int i=0 ; i<a.length ; i++ ){
   max = Math.max(max,a[i]);
  }
  return max;
 }
}

得点は90/300。結局2時間かけて解きました。正解率は私の予想よりも高く、約72%もあるようです。

2011年9月6日火曜日

Rで実験計画法 前編

Tokyo.R#16にて、実験計画法の話題について話をしてきました。ソフトウェアテストに使われる直交表について学ぶついでに、本や資料をいくつか読んだので、それらをまとめました。

2011年9月4日日曜日

Javaの私的まとめ18

Javaのお勉強その18

  1. NavigableSetとTreeSet

    TreeSetはNavigableSetを実装したものである。TreeSetに格納されるデータは自然順序付けによってソートされている。順序付けのないものにはComparableを実装するか、Comparatorを渡して順序付ける。

  2. NavigableMapとTreeMap

    TreeMapはNavigableMapを実装したものである。TreeMapに格納されるデータは自然順序付けによってソートされている。順序付けのないものにはComparableを実装するか、Comparatorを渡して順序付ける。

  3. ジェネリックス

    以下のコードはすべてコンパイルはできる。

    ArrayList a1 = new ArrayList();
    ArrayList a2 = new ArrayList();
    ArrayList a3 = new ArrayList();
    ArrayList a4 = new ArrayList();
    

    a1は古い書き方、リストに入れるときの型に注意が必要。a2は現在のJavaの書き方。安全。a3は型が定まらないので、String str = (String)a3.get(0);のようなキャストが必要になる。getで戻す型はObjectである。a4はStringとそのサブクラスしか入れられない。

    関数の引数にリストを渡す場合、int method(List list){ ... }のような書き方がある。

    class Super{ ... }
    class Sub extends Super { ... }

    に対して、以下のようにすると、a1にはSuper、Subのどちらのオブジェクトも格納できる。

    ArrayList<super> a1 = new ArrayList<super>;
    Super[] a1 = new Sub[10]; // エラーにならない
    ArrayList<super> a1 = new ArrayList<sub>(); // エラーになる
    // Superかそのサブクラスのコレクションを参照する変数
    // 要素の追加ができない
    ArrayList<? extends Super> a2 = new AraryList<sub>(); // OK
    // Subかそのスーパークラスのコレクションを参照する変数
    // 要素の追加はできる
    ArrayList<? super Sub> a3 = new ArrayList<super>(); // OK
    

Javaの私的まとめ17

Javaのお勉強その17

  1. コンパレータ

    コレクションや配列を自分が決めた順序でソートしたい場合には、Comparatorを実装するクラスを書く。C言語で言うところのqsort関数に渡す関数ポインタみたいなもの。コンパレータは次の形式である。

    public int compare(値1,値2)

    値1が値2より小さい場合は負、等しい場合は0、値1が値2より大きい場合は正の整数を戻すように定義する。

    自分で順序を決めたいものの型をXとするとき、コンパレータは次のようになる。

    class MyComparator implements Comparetor{
     public int compare(X x1, X x2){
      return (x1,x2の比較結果);
     }
    }

    例えば、数値を絶対値の小さい順に並べるコンパレータは次のようになる。このようなコンパレータをArrays.sortの引数や、Collections.sortの引数に与えることで、自分の基準でソートができる。

    class MyComparator implements Comparetor{
     public int compare(Integer x1, Integer x2){
      return Math.abs(x1)-Math.abs(x2);
     }
    }
  2. java.util.comparable

    Comparatorとの違いは、自分自身と引数に与えられた値を比較するという点である。次のような形をしており、引数は1つだけになる。

    public int compareTo(値)

    Xというクラスに自分で定義した順序を与える場合、次のように書く。

    class X implements Comparable{
     public int compareTo(X x1){
      return (自身とx1との比較結果);
     }
    }

    Comparableを実装しているクラスにはラッパークラス、String、DateCalenderなどがある。

    Comparableでは1つのクラスに1つの順序しか与えられないが、Comparatorでは、比較するクラスから独立しており、必要なだけ順序付けを定義することができる。

    Comparableを実装した場合、Arrays.sortなどの第2引数の指定は必要なくなる。

  3. 反復子

    コレクションの要素の繰り返しを扱うためのインタフェース。IteratorやIteratorを実装したクラス、オブジェクトを反復子という。List、Setにはiterator()というIteratorを返すメソッドがある。

    Listの主なメソッド
    boolean hasext() さらに要素がある場合にtrueを返す
    next() 反復子が指している要素を返し、反復子に次の要素を指すようにさせる。
    void remove() 反復子によって最後に返された要素を削除する

    反復子のサンプルプログラム。要素がそのままの順で1行につき1単語ずつ出力される。

    import java.util.*;
    class ite{
     public static void main(String[] args){
      List list = Arrays.asList("This","is","a","pen");
      Iterator it = list.iterator(); // 反復子の設定
      while(it.hasNext()){ // リストに次の要素があるうちは
       System.out.println(it.next()); // 注目している値を表示して、次を指すようにせよ。
      }
     }
    }
  4. Hash関連

    HashMap、Hashtableでは、ハッシュと呼ばれる、値を識別キーに対応させる方法を使う。検索の高速化が目的である。

    キーはObjectのメソッドであるequalsとhashCodeを使う。hashCodeはハッシュコードというint型の値を返すメソッドである。これらを正しく実装しないクラスのオブジェクトはHashtableなどのキーにすることはできない。

    hashCodeはequalsで等しいとされるオブジェクトは同じハッシュコードを戻すようにしなければならない。等しくない場合は任意であるが、異なるハッシュコードにする方が検索等が速くなる。

    import java.util.*;
    class A{
        int weight;
        A(int w){ weight = w; }
        public boolean equals(Object obj){
    	if( (obj instanceof A) && weight == ((A)obj).weight ){
    	    return true;
    	}else{
    	    return false;
    	}
        }
        public int hashCode(){
    	return weight % 10;
        }
    }
    
    class hashtest{
        public static void main(String[] args){
    	Hashtable ht =
    	    new Hashtable();
    	ht.put(new A(3),"hello");
    	ht.put(new A(5),"world");
    	System.out.println(ht.get(new A(5)));
    	System.out.println(ht.get(new A(2)));
        }
    }

    実行結果は次の通り。2に対応するオブジェクトがないので、nullが返ってくる。

    world
    null

Javaの私的まとめ16

Javaのお勉強その16

  1. コレクション

    コレクションクラスのオブジェクトの作成方法は次の通り。昔は<Integer>は不要であったが、今は型を明示するのが一般的。

    ArrayList<Integer> list = new ArrayList<Integer>;
    Listの主なメソッド
    add(値) 値を要素に追加
    add(インデックス,値) リストの指定したインデックスの位置に値を追加
    contains(値) 値がリスト中にあればtrueが返される
    get(インデックス) リストのインデックスの位置にある値を返す
    indexOf(値) 指定した値がある位置を返す(一番最初に現れるものに限られるが)
    remove(インデックス) 指定したインデックスを削除
    remove(値) 指定した値を持つ要素を削除(先頭のみ)
    toArray() リストの全要素を格納する配列を返す(Object[]型で)
    iterator() イレテータを返す
    Mapの主なメソッド
    containsKey(値) Map中にキーがあればtrue
    containsValue(値) Map中に値があればtrue
    get(キー) キーで指定される値を戻す
    put(キー、値) Mapの要素を追加
    remove(キー) キーで指定される要素を破棄
    Set keySet() マップに格納されているキーの一覧を得る
    Setの主なメソッド
    add(値) 値をSetの要素に追加
    contains(値) Set中に値があればtrue
    remove(値) 指定した値を持つ要素を削除
    toArray() すべての値を持つ配列を返す(Object[]型で)
    iterator() イテレータを作成する
    Set keySet() マップに格納されているキーの一覧を得る
    List、Map、Hashの共通メソッド
    clear() 全要素の削除
    isEmpty() 要素が空の場合にtrueを返す
    size() 要素数を返す
    Queueの主なメソッド
    add(値) 値をキューに入れる
    offer(値) 値をキューに入れる。addとの違いはaddは入れられない場合に例外を投げるのに対し、offerはfalseを返すだけである。
    peek() キューの先頭の値を返す。キューが空だとnullが返される。
    poll() キューの先頭の値を返し、先頭の要素を削除する。キューが空だとnullが返される。
  2. CollectionsとArrays
    Collectionsの主なメソッド(全部staticメソッドである)
    binarySearch(リスト,値) リストを2分探索し、値のインデックスを返す
    binarySearch(リスト,値,コンパレータ) リストを2分探索し、値のインデックスを返す。要素の比較はコンパレータに従う。
    reverse() リストを反転させる
    shuffle() リストをランダムに並び変える
    sort(リスト) リストを型にとって自然な順序で昇順にソート、文字列なら辞書順、数値は昇順。
    sort(リスト,コンパレータ) リストをコンパレータに従ってソート
    emptyList()、emptyMap()、emptyHash() 空のリスト、マップ、ハッシュの生成

    java.util.Arraysは配列を扱うためのstaticメソッドを持っている。

    Ararysの主なメソッド
    asList(要素の型... a) リストを生成する。aは可変長引数リストや配列を想定している。
    binarySearch(配列,値) 配列を2分探索し、値の見つかった位置を返す。
    binarySearch(配列,値,コンパレータ) 配列をコンパレータに従って二分探索し、値の見つかった位置を返す。
    equals(配列1、配列2) 二つの配列のデータが一致するとtrueが返される。
    sort(配列) 配列を昇順でソート。
    sort(配列、コンパレータ) 配列をコンパレータに従ってソート。
    toString() 配列の内容の文字列表現を返す。

    ここまでの二分探索メソッドで見つけようとした値がコレクションの中にない場合は負数が返される(-1とも限らない)


Javaの私的まとめ15

Javaのお勉強その15

  1. シリアライズ・デシリアライズ

    オブジェクトのデータを書き込み、読み込みすることをそれぞれシリアライズ、デシリアライズという。

    シリアライズできるクラスはインタフェースSerializeableを実装したものである。インタフェースはメンバを持たないので、特別な実装は不要。

    aというファイルにあるクラスAAのオブジェクトAを書き込む方法はつぎのようになる。

    FileOutputStream fos = new FileOutputStream("a");
    ObjectOutputStream oos = new ObjectOutputStream(fos);
    oos.writeObject(A);
    oos.close();
    

    逆にファイルを読み込む方法は次のようになる。aというファイルからオブジェクトを読み込む。

    FileInputStream fis = new FileInputStream("a");
    ObjectInputStream ois = new ObjectInputtStream(fis);
    AA aa = (AA)ois.readObject(); // Object型で読み込まれるのでキャストする
    ois.close();

    transientなフィールド、staticなフィールドはシリアライズされない。

    DataInputStreamのreadInt、DataOutputStreamのwriteIntなどでも特定の型のデータの読み書きができる。

    スーパークラスがSelializableを実装している場合、そのサブクラスもSelializableを実装していることになる。サブクラスのオブジェクトのシリアライズ・デシリアライズはスーパークラスの部分も対象とする。

    スーパークラスがSerializeを実装していない場合、サブクラスのシリアライズ・デシリアライズではスーパークラスのシリアライズ・デシリアライズは行われない。オブジェクトのスーパークラス部分はスーパークラスの引数を取らないコンストラクタで初期化される。

  2. コンソール

    コンソールはGUIを使わない入出力を簡単・安全にする。次のようにするとConsoleオブジェクトが得られる。

    Console c = system.console();
    printfの書式(フラグ)
    String readLine() キーボードから1行テキストを読みこむ
    String readLine(String format,Object...args) 書式設定したうえで1行読み込む
    char[] readPassword エコーを無効にしたコンソールから1行テキストを読み込む
    char[] readPassword(String fmt,Object ...args) 書式設定したうえで、エコーを無効にしたコンソールから1行テキストを読み込む
    Console format(String fmt,Object... args) 書式付文字列をコンソールに書き込む
    void flush() コンソールをフラッシュして出力を直ちに書き込む
  3. コレクション

    コレクションとは、複数のオブジェクトを格納しておくクラス、インタフェースのことである。java.utilパッケージに属する。

    主なインタフェースの種類
    Collection コレクションのルート。順序も重複も規定されていない
    List 順序づけられたコレクション。任意の位置に対する要素の挿入・削除が速い
    Map キーとデータを対応させたコレクション。キーはユニークになる。
    Set 重複のないコレクション、数学の集合に相当。
    Queue キュー(FIFO)
    主なコレクションクラス
    ArrayList 要素を変えられる配列のようなもの。スレッドセーフでないがVectorより高速。(Listの実装)
    Vector 要素を変えられる配列のようなもの。スレッドセーフ。(Listの実装)
    HashMap ハッシュを使ったマップ。nullが利用できる。(Mapの実装)
    Hashtable ハッシュを使ったマップでnullが使えない。スレッドセーフ。(Mapの実装)
    HashSet ハッシュを使ったセット(Setの実装)

2011年9月2日金曜日

Javaの私的まとめ14

Javaのお勉強その14

  1. 表示
    String a = "small";
    String A = "large";
    System.out.printf("a = %2$s, A = %1$s",A,a);
    とすると、a = small, A = largeと表示される。番号$は省略できるが、その場合は埋め込む文字の順序は変更できない。後ろにつけたものから順に埋められる。

    printfの書式をいくつか示す。

    printfの書式(フラグ)
    - 左揃えにする
    + 符号をつける
    0 空きを0で埋める
    , コンマ区切りを使う
    ( 負の値をかっこで囲む
  2. File

    java.io.Fileはファイルやディレクトリ(!)を表すクラスである。

    Fileオブジェクトはいくつかのコンストラクタを持つ。

    File(String name)
    File(String dir, String name)
    File(File dir, String name)

    Fileオブジェクトを生成してもファイルはすぐに作成できない。createNewFile()でファイルを作成する。ただし、ファイルが生成できない場合はjava.io.IOExceptionがスローされる。

  3. ReaderとWriter

    java.io.Readerとjava.io.Writerは文字の入出力に使うためのクラスである。

    FileReader/Writerはファイルの入出力に使う。

    BufferedReader/Writerはバッファを使い、効率よく入出力を行う。BufferedReader/WriterはReader、Writer(入出力のためのクラス)から生成できる。

    Print.Writerは文字・文字列の入出力に使う。System.outのクラスである。File、Writer、Stringなどから生成できる。

    Reader、Writerのメソッド(失敗時にIOExceptionが投げられる)
    int read() 文字を1文字読みだして戻す
    void write(char c) cを書き込む
    void write(String s) sを書き込む
    void flush() フラッシュする
    void close() 閉じる
    閉じる

    BufferedReaderはString readLine()という文字列を1行読み込んで返すメソッドを持っている。

    BufferedWriterはvoid newLine()という文字列を1行書き込むメソッドを持っている。

    import java.io.*;
    class file{
     // IOExceptionを投げると書かないとコンパイルエラーになるよ。
     // readLineメソッドなどは例外を投げる可能性があるので。
     public static void main(String[] args)throws IOException{
      File f = new File("test.txt");
      PrintWriter pw = new PrintWriter(f);
      pw.write('x'); // 書き込み
      pw.println("hello"); // これも書き込み
      pw.flush();
      pw.close();
      // ReaderからBufferedReaderを生成する。
      BufferedReader br = new BufferedReader(new FileReader(f));
      System.out.println(br.readLine());
     }
    }

8月の学習記録

2011年8月に学習した本一覧。Javaの試験勉強と統計勉強会のスライド作りであまり進んでないですが...

よくわかる実験計画法(pp.136~読了)
バランスが取れている実験(ある水準に注目したときに、他の因子は水準数が均等に登場する)しか登場しないのだけど、直交表ってまさにその性質を満たしていて、意外と使える範囲は広いのだなと思いました。次の実験計画法関連の本を読むとしたら、田口玄一氏の実験計画法あたりかな?高いけど...
Java言語プログラミングレッスン下(pp.1~142)
結構読みやすい。Javaはもう少し手を動かして理解したい。
遺伝的アルゴリズム(pp.1~30)(著:坂和)
遺伝的アルゴリズムはナップサック問題のように、組み合わせが指数的に増える問題を近似的に解くのに使える。テキストを通じて、突然変異や交差といった用語がようやく理解できた。演習がもう少しあればいうことがないのだが。
わかりやすいパターン認識(pp.1~20)
まだパーセプトロンの初歩的な話だけど、もう少し熟読してから先に進みたい。

フォロワー

ブログ アーカイブ

ページビューの合計