2012年9月29日土曜日

TopCoder SRM430 Div2 275Pts

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

あなたの語学学校は新しいセメスターを始めていて、各生徒は時間割を決めなければならない。groups[]というi番目の要素がi番目のスケジュールの受講者数を表す整数型の配列が与えられる。学校には各スケジュールに割り当てられる受講生の数はminSize以上maxSize以下でなければならないというルールがある。しかしながら、このルールは登録段階では適切に満たされていない。あなたのやることはルールが満足されるように学生のスケジュールを割り当てなおすことである。再割り当てというのは、ある学生の受講スケジュールを別の時間に振り変えることである。さて、再割り当てしなければならない学生の人数の最小値を返すメソッドを作成せよ。ただし、もしそのようなルールを満たすことができなければ-1を返すこと。スケジュールを新しく加えたり、存在しているスケジュールは削除しないことにも注意。

私の解答はこちら。

public class CreateGroups {

 public int minChanges(int[] groups, int minSize, int maxSize) {
  int[] range = new int[2];
  range[0] = minSize * groups.length;
  range[1] = maxSize * groups.length;
  int total = 0; // 総受講者数
  for( int i=0 ; i<groups.length ; i++ ){
   total += groups[i];
  }
  // -1になるのは受講者数の合計がminSize*授業数未満、あるいは
  // maxSize*授業数より大きいをみたすときである。
  if( total < range[0] || total > range[1] ) return -1;
  int[] diff = new int[2];
  for( int i=0 ; i<groups.length ; i++ ){
   if( groups[i] < minSize ){
    diff[0] += minSize - groups[i];
   }else if( groups[i] > maxSize ){
    diff[1] += groups[i] - maxSize;
   }
  }
  // 最少の再割り当て人数は少ない方に埋めなければならない人数と
  // 多い方で減らさなければならない人数の大きい方になる。
  return Math.max(diff[0], diff[1]);
 }

}

得点は176.84/250、1回のsubmitでシステムテストクリア。最後のコメントにあるアイディアを思いつくのに時間がかかりました。

2012年9月25日火曜日

TopCoder SRM429 Div2 250Pts

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

AAAAとBBというポリオミノ(複数の正方形をつなげた図形)が無限に与えられている。"."あるいは"X"という文字で埋められたregionという文字列が与えられる。あなたはこれに対し、Xという文字を与えられたポリオミノで隙間なく覆わなければならない(ポリノミオが重なってもならない)。残された"."はいじることなく、Xという文字はAあるいはBという文字で覆った結果の文字列を返すようにせよ。もし、そのような結果が返せないようであれば、"impossible"という文字列を返せ。もし、複数の解答があるようであれば、辞書順で値が最も小さくなるような文字列を選ぶようにせよ。

私の解答はこちら。

public class LinearPolyominoCovering {

 public String findCovering(String region) {
  StringBuilder sb = new StringBuilder();
  int nX = 0;
  for( int i=0 ; i<region.length() ; i++ ){
   if( region.charAt(i) == '.' ){
    if( nX % 2 != 0 ) return "impossible";
    while( nX > 0 ){
     if( nX >= 4 ){
      sb.append("AAAA");
      nX -= 4;
     }else if( nX >=2 ){
      sb.append("BB");
      nX -= 2;
     }
    }
    sb.append('.');
    continue;
   }else{
    nX++;
   }
  }

  if( nX % 2 != 0 ) return "impossible";
  while( nX > 0 ){
   if( nX >= 4 ){
    sb.append("AAAA");
    nX -= 4;
   }else if( nX >=2 ){
    sb.append("BB");
    nX -= 2;
   }
  }
  return sb.toString();
 }

}

得点は229.55/250、1回のsubmitでシステムテストクリア。辞書順で値が最小になるというのは、できるだけAでregionを埋めろということに言い換えればOKです。同じコードが繰り返しているので、そこはリファクタリングの余地があるかもしれません(速度を競う競技プログラミングではリファクタリングしている余裕が無いといえば無いのですが)。

2012年9月24日月曜日

TopCoder SRM428 Div2 250Pts

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

ジョンとブラスは文字列の理論について大学で学んでいる。ブラスはパリンドローム(訳注:回文のこと)が大好きである。パリンドロームというのは前からも後ろからも同じように読める単語のことである。ジョンはsという文字列を受け取った時に、0文字以上の文字をsの後ろにつけてパリンドロームを作ることで、ブラスを驚かせたいと思っている。ジョンはパリンドロームはできるだけ短くしたいと考えている。sという文字列が与えられたとき、ジョンが生成できるもっとも短いパリンドロームの文字列の長さを返すメソッドを作成せよ。

私の解答はこちら。

public class ThePalindrome {

 public int find(String s) {
  StringBuilder sb = new StringBuilder(s);
  String rev = sb.reverse().toString(); // sをひっくり返した単語
  for( int i=0 ; i<s.length() ; i++ ){
   String s1 = s.substring(i, s.length()); // sの先頭i文字目以降と
   String s2 = rev.substring(0, rev.length()-i); // ひっくり返した文字列の最後の方を比較して
   if( s1.equals(s2) ) return s.length() + i; // 一致したときの最短パリンドロームの長さを返す
  }
  return s.length()*2-1;
 }

}

得点は243.03/250、1回のsubmitでシステムテストクリア。ひっくり返した文字列との比較の方法がポイント。

2012年9月23日日曜日

TopCoder SRM427 Div2 250Pts

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

女の子が好きな男の子の一人とデートしたいと思っているが、誰を選んでいいか分かっていない。幸いにして、女の子はLove Calculatorという、二人が愛し合っている確率を計算できるものを持っている。Love Calculatorは二人の名前を受け取り、以下のアルゴリズムに沿って、愛し合っている確率を計算する。

  • Lは二人の名前に登場する'L'の出現回数
  • Oは二人の名前に登場する'O'の出現回数
  • Vは二人の名前に登場する'V'の出現回数
  • Eは二人の名前に登場する'E'の出現回数
以上のように置いたとき、二人の愛し合っている確率は((L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E))%100で求めることができる。女の子の名前を表すgirlという文字列型変数と、彼女の好きな男の子の名前が含まれるboys[]という配列が与えられたとき、女の子と最も愛し合っている可能性が高い男の子の名前を返すメソッドを作成せよ。もし、複数の男の子が候補にある場合は、アルファベット順に並べたとき最初に来る名前を返すようにすること。

私の解答はこちら。

public class LoveCalculator {

 public String findBoy(String girl, String[] boys) {
  long maxprob = -1;
  int[] freq_girl = new int[4]; // LOVEという文字の出現回数を記録

  String bestBoy = "";
  for( int i=0 ; i<girl.length() ; i++ ){
   if( girl.charAt(i) == 'L' ) freq_girl[0]++;
   if( girl.charAt(i) == 'O' ) freq_girl[1]++;
   if( girl.charAt(i) == 'V' ) freq_girl[2]++;
   if( girl.charAt(i) == 'E' ) freq_girl[3]++;
  }
  for( int i=0 ; i<boys.length ; i++ ){
   int[] freq_boy = new int[4];
   for( int j=0 ; j<[i].length() ; j++){
    if( boys[i].charAt(j) == 'L' ) freq_boy[0]++;
    if( boys[i].charAt(j) == 'O' ) freq_boy[1]++;
    if( boys[i].charAt(j) == 'V' ) freq_boy[2]++;
    if( boys[i].charAt(j) == 'E' ) freq_boy[3]++;
   }
   int[] fr = new int[freq_girl.length];
   for( int j=0 ; j<.length ; j++ ){
    fr[j] = freq_girl[j] + freq_boy[j];
   }
   long prob = ((fr[0]+fr[1])*(fr[0]+fr[2])*(fr[0]+fr[3])*
                (fr[1]+fr[2])*(fr[1]+fr[3])*(fr[2]+fr[3]))%100;
   if( prob > maxprob ){
    bestBoy = boys[i];
    maxprob = prob;
   }else if( prob == maxprob ){
    if( bestBoy.compareTo(boys[i]) > 0 ){
     bestBoy = boys[i];
    }
   }
  }
  return bestBoy;
 }

}

点数は183点台でした。配列よりもハッシュの方が綺麗に書けるんでしょうかね。probを計算するときは、6つの値を順に掛ける度に100で割っておけばオーバーフローを気にしなくてもよさそうです。すべて掛け算すると、最大で40^6まで値を取り得るので、上の実装では念のためlongにしています。

2012年9月21日金曜日

Pythonで独自ソートの実装

Pythonのリストにあるsortメソッドは、自然な順序でソートしてくれるものであるが、そうではないソートを行いたいときがある。そのようなソートを行うには、sortメソッドに比較のための関数を渡してやればよい。まずは、比較によく用いられる関数を見てみよう。

>>> help(cmp)
Help on built-in function cmp in module __builtin__:

cmp(...)
    cmp(x, y) -> integer
    
    Return negative if xy.
>>> help(list.sort)
Help on method_descriptor:

sort(...)
    L.sort(cmp=None, key=None, reverse=False) -- stable sort *IN PLACE*;
    cmp(x, y) -> -1, 0, 1
>>> help(sorted)
Help on built-in function sorted in module __builtin__:

sorted(...)
    sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list

cmp関数は2つの引数を評価した結果を返すというものである。第1引数が第2引数より小さければ負、同じなら0、大きければ正の値を返すようになっている。

リストのsortメソッドには3つの引数を与えることができる。cmpは比較のための関数である。keyはソートの基準となる対象を指定するものである。例えば文字列のソートで2文字目以降でソートしたいという場合にはlambda x:x[1:]とすることになる。この場合、xはソート対象となるオブジェクトに相当する。reverseは昇順・降順を指定するものである。デフォルトでは昇順に並べることになる。

sortedは反復可能なオブジェクトであれば、ソートすることができる。例えば、辞書のvalueで辞書をソートするときにはこれを利用するとよい。cmpなどのオプションはlist.sortと同様の意味を持つ。

これを踏まえて、以前Javaでも書いた文字列の長さ順にソートするということを行ってみる。なお、sortメソッドはstable sort(安定なソート)なので、同じ値(=文字列の長さが同じ)が複数ある場合は、先に出てきたものが先に並べられるようになっている。

# -*- encoding: utf-8 -*-

def cmp_len(s1, s2):
    return cmp(len(s1), len(s2)) # 文字列の長さで比較するための関数

langs = ["Python", "LISP", "Haskell", "C", "Java"]

langs.sort(cmp=cmp_len, reverse=True)
print langs #徐々に文字列の長さが短くなっていくリストになる

dic = {"NumPy":"numerical analysis",
       "sphinx":"documentation generator",
       "django":"web"}

sdic = sorted(dic.items(), cmp=cmp_len, key=lambda x:x[1])
# 説明文が短い順に並べ替えられている
print sdic

表示される結果は次の通り。

['Haskell', 'Python', 'LISP', 'Java', 'C']
[('django', 'web'), ('NumPy', 'numerical analysis'), ('sphinx', 'documentation generator')]

2012年9月17日月曜日

TopCoder SRM425 Div2 250Pts

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

nという正の整数がproper factorであるというのは、nがaの倍数で、かつaが1でもnでもないということを指す。ある数nのproper factorのすべての要素が含まれている、factors[]という2以上の整数が含まれるリストが与えられる。このとき、nを求めて返すメソッドを作成せよ。

私の解答はこちら。

public class InverseFactoring {

 public int getTheNumber(int[] factors) {
  long proper = 1;
  long max = -1;
  long min = Long.MAX_VALUE;
  for( int i=0 ; i<factors.length ; i++ ){
   proper = lcm(proper, factors[i]); // 全部の数の最小公倍数を計算
   max = Math.max(max, factors[i]);
   min = Math.min(min, factors[i]);
  }
  // factorの全要素の最小公倍数が最大値そのものになったら、
  // 最大値はproper factorではないので、最小値だけ掛けてproper factorを求める。
  return proper == max ? (int)proper * (int)min : (int)proper;
 }

 static long gcd(long a, long b){ // 最大公約数
  return b == 0 ? a : gcd(b, a % b);
 }

 static long lcm(long a, long b){  // 最小公倍数
  return a * b / gcd(a, b);
 }
}

得点は200.54/250、2回目のsubmitでシステムテストクリア。仮定としてfactorsは妥当なものしか入らないので、上のような実装は不要で、factorsの最小値*最大値で導出ができるとのこと。

2012年9月16日日曜日

ウォリスの公式

PythonでWallisの公式を書いてみました。Wallisの公式は円周率を多項式を利用して近似するものです。元ネタはPython Scientific lecture noteの英語版(2012年8月リリース)19ページの練習問題になります。実行結果を見てみると、引数の値を大きくするにつれて、円周率に近づいている様子が確認できます。ちなみにnumは数字というよりもnumerator(分子)のつもりです、念のため。

def wallis_formula(n):
    mypi = 1
    for i in range(1, n):
        num = 4*(i**2)
        mypi *= float(num)/(num-1)
    return 2 * mypi

'''
>>> wallis_formula(1000)
3.1408069608284657
>>> wallis_formula(10000)
3.1415141108281714
>>> wallis_formula(100000)
3.141584799578707
>>> wallis_formula(1000000)
3.1415918681913633
'''

2012年9月15日土曜日

TopCoder SRM424 Div2 250Pts

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

古代の呪文を含んだspellという文字列が与えられる。その呪文は暗号化されているいるが、暗号はかなり単純なものである。呪文を解読するために、AとZという文字をすべて見つける必要がある。そして、その順序を判断させるのである。例えば、暗号化された文字列が、"AABZCADZA"であれば、AとZを見つけ出し、それらの順序(A->A->Z->A->Z->A)を反転させて、"AZBACZDAA"という解読結果を得る(AとZの位置だけに注目すると反転していることが分かる)。与えられたspellという文字列に対し、解読した結果得られる文字列を返すようなメソッドを作成せよ。

私の解答はこちら。

import java.util.ArrayList;

public class MagicSpell {

 public String fixTheSpell(String spell) {
  // 出現した文字と出現した位置を記録しておく
  ArrayList<Character> list = new ArrayList<Character>();
  ArrayList<Integer> pos = new ArrayList<Integer>();
  for( int i=0 ; i<spell.length() ; i++ ){
   char c = spell.charAt(i);
   if( c == 'A' || c == 'Z' ){
    list.add(0, c); // 0の位置にcを入れることでAとZの出現順序を反転させている
    pos.add(i);
   }
  }
  StringBuilder sb = new StringBuilder();
  int idx = 0;
  for( int i=0 ; i<spell.length() ; i++ ){
   if( idx == pos.size() ){ // 全部AとZが出てきたら終了
    sb.append(spell.substring(i));
    break;
   }
   if( pos.get(idx) == i ){
    sb.append(list.get(idx));
    idx++;
   }else{
    sb.append(spell.charAt(i));
   }
  }
  return sb.toString();
 }

}

得点は150.26/250、3回目のsubmitでシステムテストクリア。中央値は約229点。idxが最後まで来た時にbreakで終了するように仕向けないと、pos.get(idx)の評価でエラーを起こすことに気付かず嵌る。

2012年9月13日木曜日

Pythonでクイックソート実装

Scipyを学習するためのノートPython Scientific lecture notesというものが公開されています。英語版pdfはこちらの右上にあるDownloadsのところにあるpdfへのリンクを、日本語版pdfはこちらの上部にある印刷用のダウンロード書かれた横のpdfへのリンクをクリックすると読むことができます。ただし、(記事執筆時点では)日本語版は最新版ではないようです。

本日は英語版のノート24ページにある、Wikipediaのクイックソートの説明文(擬似コード)を実際のプログラムに変換せよという問題を解いてみました。以下、私の解答です。

# -*- encoding: utf-8 -*-

def quick_sort(array):
    if len(array) < 2:
        return array
    # 特に指定が無いのでほぼ中央の位置にある値をピボットとする
    pivot = array.pop(len(array)/2)
    less = []
    greater = []
    for x in array:
        if x < pivot + 1:
            less.append(x)
        else:
            greater.append(x)
    return quick_sort(less) + [pivot] + quick_sort(greater)

ピボットの選び方は簡単のため、リストの中央の位置にある値にしていますが、それ以外にも方法があります。例えば、中央の位置と両端の3つの値に対する中央値をピボットにするという方法があります。これは、クイックソートの性能はピボットの選び方に依存するためです。

極端ではありますが、毎回ピボット以下の値になるグループのデータ数が0、ピボットより値が大きいグループのデータが残り全部となった場合に効率が悪くなります。この場合、ソートのオーダはデータ数をnとしたときO(n^2)になります(1個ずつソート済になるため、バブルソートなどのソートと同じ程度の計算量になる)。クイックソートのオーダは平均してO(n*log(n))となるので、nが大きいとき非効率になってしまいます。

データを大きいもの、小さいもので半分ずつに分けられるようなピボットを選ぶのが理想的なのですが、データを大量に利用してピボット選択の計算をすること自体にも時間がかかってしまいます。このようなときは、ソートしたいデータの性質に依存したピボット選択を考えましょう。例えば、ほぼ昇順であるが、数パーセントのノイズが入ってくるデータの場合は、数パーセントのノイズには目をつぶって、中央の位置にある値(=ほぼ中央値と期待される)をピボットにするという方針を選ぶことが考えられます。

2012年9月14日追記

データの破壊はないほうがよいということなので、popメソッドを利用しない方針で書き直してみました。

# -*- encoding: utf-8 -*-

def quick_sort2(array):
    if len(array) < 2:
        return array
    # 特に指定が無いのでほぼ中央の位置にある値をピボットとする
    pivot_pos = len(array)/2
    pivot = array[pivot_pos]
    less = []
    greater = []
    for idx, x in enumerate(array):
        if idx == pivot_pos: continue
        if x < pivot + 1:
            less.append(x)
        else:
            greater.append(x)
    return quick_sort(less) + [pivot] + quick_sort(greater)

2012年9月12日水曜日

Rで実験計画法 後編

4ヶ月ほど前に開かれたTokyo.R #22にて発表に利用した、実験計画法の話題に関する後編のスライドです。ソフトウェアのテストと絡めて、直交表の使い方などについて話をしてきました。前編についてはこちらからご覧ください。

2012年9月10日月曜日

TopCoder SRM423 Div2 250Pts

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

n*nの盤面とその上にいくつかチェッカーの駒がある。i番目の駒は盤面のx[i]行、y[i]列のセルにある。すべての座標は1から始まるものとする。一つのセルには複数の駒がある可能性もある。一つの駒を動かすことは、駒を座標の上下左右に動かすことからなるものとする。あなたは各駒を盤面の4つの角に置きたいと思っている。その目標を達成するのに必要な最小の移動回数を返すメソッドを作成せよ。

私の解答はこちら。

public class TheSimpleGame {

 public int count(int n, int[] x, int[] y) {
  int nMove = 0;
  for( int i=0 ; i<x.length ; i++ ){
   int xx = x[i]-1 < n-x[i] ? x[i]-1 : n-x[i]; // x座標方向の最小移動量
   int yy = y[i]-1 < n-y[i] ? y[i]-1 : n-y[i]; // y座標方向の最小移動量
   nMove += (xx + yy);
  }
  return nMove;
 }

}

得点は236.60/250、1回のsubmitでシステムテストクリア。中央値は約229点。

2012年9月6日木曜日

TopCoder SRM422 Div2 250Pts

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

ある数字がmulti numberであるというのは、その数字の10進数の表現を2つの数字に分けたときに、二つの数字の各桁の積が等しくなるものがあるということである。例えば、1221という数字は12と21に分ければ、各桁の積は共に2となり、これはmulti numberである。同様に1236もmulti numberとなるが(訳注:123と6に分ければよい)、1234はそうはならない。なお、2つの数に分けるとき、どちらの数も少なくとも1桁以上でなければならないことに注意。つまり12345という数字があれば、1-2345, 12-345, 123-45, 1234-5という4通りの分け方が存在することになる。さて、numberという数字が与えられたとき、multi numberであれば、"YES"、そうでなければ"NO"を返すようなメソッドを作成せよ。

私の実装はこちら。

public class MultiNumber {

 public String check(int number) {
  String snum = "" + number;
  for( int i=1 ; i<snum.length() ; i++ ){
   int left = multiplyDigits(snum.substring(0, i));
   int right = multiplyDigits(snum.substring(i));
   if( left == right ) return "YES";
  }
  return "NO";
 }

 private int multiplyDigits(String s){ // 分けられた数字の各桁の積を計算
  int ret = 1;
  for( int i=0 ; i<s.length() ; i++ ){
   ret *= (s.charAt(i) - '0');
  }
  return ret;
 }
}

得点は241.10/250、1回のsubmitでシステムテストクリア。中央値は約169点。

2012年9月4日火曜日

TopCoder SRM421 Div2 250Pts

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

あなたはジムにおり、トレーニングをしたいと思っている。トレーニングは1分間単位に分けられる。1分間ごとに、運動あるいは休憩のどちらかを取ることができる。もし、トレーニングを1分間することにすれば、心拍数がtrainChangeだけ上昇する。つまり、もし、ある時点での心拍数がXであれば、運動した1分後にはX+trainChangeになrということである。心拍数はmaxPulseという上限を超えて欲しくはないので、X+trainChangeがmaxPulse以下になるときに限って運動を行うことができる。もし、1分間休憩することにすれば、restChangeだけ心拍数を下げることになる。つまり、ある時点の心拍数がXであれば、休憩を1分した後には心拍数がX-restChangeになるということである。しかしながら、心拍数はminPulseを下回ることはなく。X-restChangeがminPulse未満になるようであれば、心拍数はminPulseになる。初期状態におけるあなたの心拍数をminPulseとする。そして、needToTrainという時間だけ運動を行いたいものとする(連続で行う必要はない)。それだけのトレーニングを行うのに最小限必要となる時間を返すメソッドを作成せよ。なお、needToTrain分間の運動ができないようであれば、-1を代わりに返すようにすること。

私の実装はこちら。

public class GymTraining {

 public int trainingTime(int needToTrain, int minPulse, int maxPulse, int trainChange, int restChange) {
  int currentPulse = minPulse;
  int currentTime = 0;
  int currentTrainTime = 0;

  // 失敗する場合の条件チェック
  if( minPulse + trainChange > maxPulse ) return -1;
  while( true ){
   // 休憩と運動の選択
   // maxPulseを上回らないようであれば、運動を選択することで、時間を最小化できる
   if( currentPulse + trainChange <= maxPulse ){
    currentPulse += trainChange;
    currentTime++;
    currentTrainTime++;
    if( currentTrainTime >= needToTrain ) break;
   }else{
    int next = currentPulse - restChange;
    currentPulse = next >= minPulse ? next : minPulse;
    currentTime++;
   }
  }
  return currentTime;
 }

}

得点は230.67/250、1回のsubmitでシステムテストクリア。中央値は約188点。

2012年9月3日月曜日

TopCoder SRM420 Div2 500Pts

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

あなたは大みそかをとても楽しみにしている。次の大みそかはそんなに遠くなく、あなたはそれを楽しみにしている。そして、ある日、ある疑問で目が覚めることになる。「待てよ、大みそかはどのぐらい離れているんだ?」

この質問に答えるため、今年がどの程度終わったかを示すプログレスバーという、簡単なアプリケーションを作成することにした。この問題においては、目標はこのアプリケーションのもっとも重要なパートを実装することである。つまり、現在時刻を示すcurrentDateという文字列を受け取ったときに、百分率でその年の進捗状況を返すというものである。currentDateという変数は"Month DD, YYYY HH:MM"という文字列で与えられる。ここで、Monthは月の名前を表し、YYYYは西暦、DD、HH、MMは日、時間、分を二桁の数値で表したものである。なお、0埋めされる可能性がある(訳注:例えば5月の場合MMは05ということになる)。

私の実装はこちら。

public class YearProgressbar {

 public double percentage(String currentDate) {
  int[] days = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  // 現在時刻の解釈
  String[] date = currentDate.split(" ");
  int year = Integer.parseInt(date[2]);
  int month = monthInt(date[0]);
  int day = Integer.parseInt(date[1].substring(0, 2));
  int hour = Integer.parseInt(date[3].substring(0, 2));
  int minutes = Integer.parseInt(date[3].substring(3));
  boolean leap = isLeap(year); // 今年はうるう年か?
  int daysInYear = leap ? 366 : 365;
  int secondsInYear = daysInYear * 24 * 3600; // 1年間の秒数

  int alreadyPassedDays = 0;
  for( int i=0 ; ilt;month ; i++ ){
   alreadyPassedDays += days[i];
   if( leap && i == 1 ) alreadyPassedDays++; // 経過した日数を計算
  }
  int alreadyPassedSeconds = minutes * 60 + hour * 3600 +
          (day - 1 + alreadyPassedDays) * 24 * 3600 ; // 今年の経過秒数を求めている
  return alreadyPassedSeconds * 1.0 / secondsInYear * 100;
 }

 private boolean isLeap(int year){
  if( year % 400 == 0 || (year % 4 == 0 && year % 100 != 0) ){
   return true;
  }
  return false;
 }

 private int monthInt(String month){ // monthという文字列から月の値を返す。失敗すれば-1。
  String[] monthString = {"January", "February", "March", "April", "May", "June",
            "July", "August", "September", "October", "November", "December"};
  for( int i=0 ; i<monthString.length ; i++ ){
   if( month.equals(monthString[i]) ){
    return i;
   }
  }
  return -1;
 }
}

得点は315.02/500、1回のsubmitでシステムテストクリア。中央値は150点。愚直な実装ではありますが、これで問題なし。分単位までで良かったので、秒単位に変換する必要はありませんでしたね。

2012年9月1日土曜日

2012年8月の学習記録

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

情報セキュリティスペシャリスト試験のテキスト(pp.89~211、249~284)
10月の試験に向けて、テキストを読書中。気になったことを気軽に実験しやすい分野であれば、もう少し学びやすくもなりそうなものですが。攻撃を実際に試すというわけにもいかないですし(苦笑)。
入門・演習 数理統計(pp.97~161、演習問題74問)
確率変数の分布に関する性質について学ぶ。前章の確率変数変換の知識を利用して分布関数を導出する方法が頻出。負の二項分布、超幾何分布など、あまり聞きなれない分布がどのようなものか理解できた。また、それぞれの分布がどのような関係にあるかということについて、代表的なものについて知ることができた。
テキストデータの統計科学入門(pp.135~233、読了)
後半はちょっと詰め込みすぎかな?あまり手の動かしようがなかった。
これなら分かる最適化数学(pp.1~97)
ヘッセ行列が今まで天下り式に与えられていたのを利用していたが、この本でなぜヘッセ行列で極値判定ができるかを理解できた。順を追って理解させるようにしている。一からやるなら、なかなかの良書。
統計解析入門(pp.148~192)
推定、検定の手法について。
入門自然言語処理(pp.111~186、演習問題34問)
第3章では正規表現の他、トークン化、生テキストの文分割などの手法について学んだ。第4章は一般的なプログラミングの技法に関しての内容で、プログラムの基本的な話題が多め。
初めてのPython(第27章)
例外について。with~as構文は初見でした。

その他、NHK実践ビジネス英語を聞く、情報セキュリティスペシャリスト試験の過去問題を解くなどした。プログラミングに関しては、PythonでMecab(形態素解析ソフト)を動かす方法の調査の他、Project Euler、TopCoderの過去問を解いている。

フォロワー

ページビューの合計