がはじまったので、今年も参加しています。

Aの small/large 、 C の small が解けてなんとかパスしました。 スコアは。

A : Alien Language

正規表現で一発だよなーということで Ruby に丸投げ。我ながらこれはひどい。

C : Welcome To Code Jam

再帰っぽいよねー、でもふつうに再帰でやると問題サイズに耐えられなくて時間切れだろうなー、とか思いつつ再帰で書いた。

small set は OK だったけれど、案の定 large set の計算がぜんぜん終わらないので次へ。

B : Watersheds

ちまちま机上で考えてコードに落としてみたところ、サンプルケースは通ったのでさっそく small set に書けるとアウト。そのあとしばらくあれやこれやいじってるけどだめげなのでふて寝。

---

けっきょく、去年からあんまし変わっていないなーというのはよくないですね。 力任せのアルゴリズムしか浮かばないか、まるで見当違いのところをぐるぐるしているだけで時間が過ぎるという。 DP とか日常で使わないので、なかなか身に付かないというのがあるかな。

次のラウンドまでに、他の参加者のコードをみて勉強べんきょうですね。

に参加してます。

Qualification Round は A,B を解いて Score:50、Rank:2246 でした。Cむずいよ。 Rubyで書いてます。irbがつかえるこの幸せ。 irbでインタラクティブにデバッグしつつ、本番の入出力をケアするためのコードを最終行にいれてます。

A. Saving the Universe

さいしょ、レポートの出力形式を間違っていて (#0から出力してた)、なんでこれで違うんだろうと首をかしげてた。1回ぶんのmiss submit。

戦略は以下:

• 入力を先頭から順になめて、エンジンを set に追加
• すべてのエンジンが set にはいったら、カウンタをあげて、setをリセット

電車の中で、この単純な解法に気づいたときはうれしかった。

!/usr/bin/env ruby

Saving the Universe

at Google Code Jam 2008, QR A

#

use Ruby 1.8.6 (2008-03-03 patchlevel 114) [universal-darwin9.0]

#

author:mootoh

#
require 'logger'


$log = Logger.new(STDOUT)
$log.level = Logger::ERROR
$log.datetime_format = ''


def test(engines, queries)
  state = []
  count = 0


queries.each do |query|
    state.push query
    state.uniq!
    if state.size == engines.size
      $log.debug("change !")
      count += 1
      state = [query]
    end

$log.debug(state)

end


count.to_s
end


def main(file)
  n = file.gets.chomp.to_i
  n.times do |i|
    s = file.gets.chomp.to_i
    engines = []
    s.times {|j| engines.push file.gets.chomp}

q = file.gets.chomp.to_i
queries = []
q.times {|k| queries.push file.gets.chomp}

puts "Case ##{i+1}: " + test(engines, queries)

end
end


main(ARGF) unless $PROGRAM_NAME == 'irb'

Train Timetable

これも電車で解いた。 オブジェクト指向っぽく考えてたら、できそうな気がして。 遅いけど、実行時間は今回問われてないのでおk。

!/usr/bin/env ruby

Train Timetable

at Google Code Jam 2008, QR B

#

use Ruby 1.8.6 (2008-03-03 patchlevel 114) [universal-darwin9.0]

#

author:mootoh

#
require 'logger'


$log = Logger.new(STDOUT)
$log.level = Logger::ERROR
$log.datetime_format = ''


class Arrow
  attr_accessor :from, :to
  def initialize(from, to)
     = from;  = to
  end


def start_at?(at)
     == at
  end
  def to_s; "#{from} -> #{to}"; end
  def inspect; to_s; end
end # Arrow


class Train
  attr_accessor :available_at


def Train.tt=(x); @ = x; end
  def Train.tt; @; end


def initialize(at)
     = at
  end


def departure(to)
     = to + @
  end


def to_s; "Train@:#{}"; end
  def inspect; to_s; end
end # Train


class Station
  attr_accessor :trains, :arrows, :count


def initialize(arrows)
     = []
     = arrows
     = 0
  end


def train_available_at(at)
    t =  { |train| train.available_at <= at }
    if t
      (t)
      t
    else
       += 1
      Train.new(at)
    end
  end


def to_s
    'Station: ' + [
       {|x| x.to_s},
       {|x| x.to_s},
      
    ].join(' : ')
  end
  def inspect; to_s; end
end # Station


def parse(n, file)
  ret = []
  n.times do |i|
    x = file.gets.chomp.split(/\s+/).map do |x|
      h, m = x.split(/:/).map {|y| y.to_i}
      h * 60 + m
    end
    ret.push Arrow.new(x[0], x[1])
  end
  ret
end


def main(file)
  n = file.gets.chomp.to_i
  n.times do |j|
    tt = file.gets.chomp.to_i
    Train.tt = tt
    na, nb = file.gets.chomp.split(/\s+/).map {|x| x.to_i}

arrows = [na,nb].map {|x| parse(x, file)}
starts = (arrows[0] + arrows[1]).map {|x| x.from}.sort.uniq
stations = arrows.map {|x| Station.new(x)}

starts.each do |start|
  $log.debug("start at #{start} --------------------")
  2.times do |i|
    st_i = stations[i]
    st_o = stations[(i+1)%2]

    departures = st_i.arrows.find_all {|x| x.start_at?(start)}
    $log.debug("departures=#{departures.size}")
    departures.each do |d|
      train = st_i.train_available_at(start)
      train.departure(d.to)
      st_o.trains.push train
      $log.debug(train)
    end
    st_i.arrows -= departures

    $log.debug("#{i == 0 ? 'A' : 'B'}: #{st_i}")
    $log.debug("#{i == 0 ? 'B' : 'A'}: #{st_o}")
  end
  $log.debug('------------------------------------')
end
puts "Case ##{j+1}: #{stations[0].count} #{stations[1].count}"

end
end


main(ARGF) unless $PROGRAM_NAME == 'irb'

---

つぎからが本番ですね。がんばろう。

に登録しておきました。 来月ですね!

前回とちがって、TopCoderのアプリを使うわけではなさそうです。 自分はRubyを言語として選んでみました。できるのかな。

2006年に挑戦し、自分のふがいなさを思い知らされ、 そこからTopCoderで練習を積んできました。 2年経ったいま、自分はちゃんと進歩しているのだろうか。

当時のエントリ:

• Google Code Jam 2006
• Google Code Jam 2006 Practice 500
• Google Code Jam Practice
• Google Code Jam 2006 日程
• CodeJam Practice : 1000点問題
• CodeJam Qualification Round開始
• CodeJam Qualification Round 結果
• CodeJam Qualification Round 750点問題
• Google CodeJam 2006 で使ったテンプレート
• CodeJam Qualification Round : SystemTestとおった

よかったー。 これでこのRoomでは11番ということになりました。750点問題が悔やまれてなりません。

しかし、こんなにもSystemTestでFailする人がいるとは… 早撃ちガンマンなだけではだめということなのですね。スピードと正確さでバランス良く解くのって難しそうだなぁと。

ランキングのスクリーンショット

ちょっと気になったのでとってみました。

Set 3の順位:

Set 3 Room 27の順位: ‘

こんな感じでした。

惨敗に終わったCodeJam 2006ですが、ちょっとだけTipsとか。

問題内容を公開してしまうのはルール上違反なのかもしれないので、問題とその解答は書きません。ですが、自分がCodeJamに望むにあたり、ちょっとでも早くコードを書き始めることができるようなテンプレートをつくっていました。 何かの役に立てればと思い公開してみます。

コードは続きにて。

工夫

• 問題のクラス、メソッドなどをマクロにして差し替え可能に
• テストケースをちょっとは簡単に記述できるように

使い方

• XXXが書かれているコメントのところを、問題に合わせて書き直し
• コンパイルオプションに -DLOCAL_TESTを加えて

やれば、動くんではないでしょうか。

---

/*
 * Google CodeJam 2006
 *
 * Template Code
 *
 * $Id: template.cc 320 2006-09-06 12:28:58Z takayama $
 */




/* ---------------------------------------------------------
 * XXX: 1. modify for each case
 */

define CLASS Hoge

define METHOD_RET int

define METHOD_NAME hoge

define METHOD_ARG_T vector < string >

define METHOD_ARG ss

// ---------------------------------------------------------

include

include

include

ifdef LOCAL_TEST

include

include

endif // LOCAL_TEST

define NELM(arr) ( sizeof((arr)) / sizeof((arr[0])) )

using namespace std;
typedef vector  VS_;
typedef vector ::iterator VSI_;
typedef vector  VI_;
typedef vector ::iterator VII_;


/* ---------------------------------------------------------
 * XXX: 2. Problem Solution
 */
class CLASS {
   public:
   METHOD_RET METHOD_NAME (METHOD_ARG_T METHOD_ARG);


private:
};


METHOD_RET CLASS::METHOD_NAME (METHOD_ARG_T METHOD_ARG) {
   return 0;
}


/* ---------------------------------------------------------
 * Test
 */

ifdef LOCAL_TEST

template 
void test (T &test_case, METHOD_RET assumption) {
   CLASS obj;
   METHOD_RET ret;


ret = obj.METHOD_NAME (test_case);


cout << "assumption = " << assumption << ", "
        << "result = " << ret << endl;


assert(assumption == ret);
}


void print_VS_(VS_& vs) {
   for (VSI_ i= vs.begin(); i != vs.end(); i++) {
      cout << *i << endl;
   }
}


/*
 * XXX: 3. add test cases here
 */
const int test_cases_length[] = {
   2,
   3,
};


const char *test_cases_arr[][256] = {
   {"hoge", "fuga"},
   {"moge", "yoga", "daru"},
};


/*
 * XXX: 4. add expected result here
 */
const int assumptions[] = {
   0,
   0,
};


vector  test_cases;


int main(int argc, char**argv) {
   size_t i;


for (i=0; i < NELM(test_cases_arr); i++) {
      VS_ vs = VS_(
            test_cases_arr[i],
            test_cases_arr[i] + test_cases_length[i]);

  test_cases.push_back(vs);

}


for (i=0; i < test_cases.size(); i++) {
      test(test_cases[i], assumptions[i]);
   }


return 0;
}

endif // LOCAL_TEST

---

C++のtemplateをつかったら、もっときれいに書けるんだろうなぁとか思いますが、時間がなかったのでついついマクロにしてしまったり、テストケースの書き方がstring専用になってしまっていたりと美しくありません。 でもまぁ今回に関しては実用に足りたかなと。

ぬおおっ、こっちの方が素早く解けてしまったっっっ!! しかも解答内容に自信あるし。テストケースちゃんと全部通るし。

しまったなぁ、こっちを最初からやっとけば300点くらいはとれたかもだなぁ。

とか言っても、けっきょく300点くらいではこのRoomのベスト10に入れるか入れないかくらいの成績でしかないわけで。きびしいなぁ。

あと、いま割とさっくりとできたのは時間外だからプレッシャーが少なかったというのもあると思います。やはりまだまだです。

ちなみに問題は、Permanentに関するものでした。

---

追記 :Official Rules and Regulations を読んでも特に問題なさそうなので、問題の概要を加えました。

91.62pts

だめだ… OTZ

詳細

• Qualification Set 3 Room 27
• C++で
• 250点問題のみ
• 問題の理解に11分
• ようやく全てのテストケースが通ったのでSubmitしたのが残り1分21秒、ぎりぎりすぎ
• そんなに難しい問題ではなかったのにぃ
• コードの行数 : 213 (テストコード含む)
• 750点問題は覗いただけ
• 現時点で自分のRoomの23番なのでだめでしょう
• 1位の得点がずばぬけてる (955.78 / 1000)。ありえない
• 2, 3位の得点は660-700とまだありえるレベル

これでSystem Testing Phaseで落とされたらさらにげんなりだなぁ。

もう少ししたら (あと1時間) 終了の時間です。 最終結果はどうなることやら。いちおう終わりのときを待ってみることにします。 待つ間に750問題をやってみよう。

反省

• 問題の理解遅すぎ
• いきあたりばったり
• gdbとかつかってると遅すぎ
• 普段からエラーチェックをコンパイラまかせにしてコードを書いてるから、一発で通るまともなコードが書けない
• 頭の回転遅め
• 解き方が2つあって、やや迷ってしまった
• Python覚えることにしよう
• というか、いまさらman atoiとかしてる時点でアウトかも >_< (どのヘッダをincludeしないといけないか忘れていた)

---

とにかく頭の回転を速くしないといかんと痛感しました。猛烈にトレーニングしないとまずすぎです。

しかし、決められた時間内で問題を解くなんて久しぶりでした。やっぱりこういうの好きなのかも。TopCoderで鍛え直そうかな。

いそいそと準備のためのコードとか書いてるうちにこんな時間になってしまいました…

今から参戦してきます。結果は1時間後に。

いままでのことは忘れ、最後の練習問題である1000点問題に取り組んでいます。むずい!

ハノイの塔の変形なのだろうけどなぁ。むー。

他の人を見ても、あまり高得点者はいないみたい。そんなものなんかしら。

いよいよGoogle CodeJam 2006だーーーっっ。 意気込んで有給休暇を頂き、準備を整えることにしました。のですが、どうも時差の計算を間違えたのか何なのか、一日ずれていました。 てっきり今日の深夜から始まって、明日一日の勝負かと思っていたのに …

…ま、明日一日存分に予習をしてカンを取り戻しておくことができて良かったのかもしれません。本戦は明後日の夜 (締切ぎりぎり) にやるしかないかな。

いずれにせよ、この前みたいな無惨な結果にならないよう、がんばらないと。

ルール

ここで要項をおさらいしておきます。

Qualification Round Coding Phase

• 24時間オープン
• 問題は2問。難易度/得点が異なる2問
• 制限時間は2問合わせて60分 (><)
• 早ければ早いほど高得点
• 問題をオープンした瞬間からカウントダウン
• ラスト1時間 (日本時間で9/6の24:00-25:00) の途中から始めると損をする

Qualification Round System Testing Phase

• 提出したコードが自動的にテストされる
• まちがっていたら得点はゼロに

2問を60分かー。できるかしらん。

---

なんか受験の頃を思い出してきました。ちょっとワクワク。