Google Code Jam 2009 Qualification Round

September 4th, 2009  |  Published in Uncategorized

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

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

A : Alien Language

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

C : Welcome To Code Jam

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

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

B : Watersheds

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


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

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

Tags:

Google Code Jam 2008 Qualification Round

July 19th, 2008  |  Published in Uncategorized

に参加してます。

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'


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

Tags: ,

Google Code Jam 2008

June 19th, 2008  |  Published in Uncategorized

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

前回とちがって、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とおった
Tags: ,

CodeJam Qualification Round : SystemTestとおった

September 7th, 2006  |  Published in Uncategorized

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

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

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

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

Set 3の順位:

Set 3 Room 27の順位: ‘

こんな感じでした。

Tags: ,

Google CodeJam 2006 で使ったテンプレート

September 7th, 2006  |  Published in Uncategorized

惨敗に終わった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専用になってしまっていたりと美しくありません。 でもまぁ今回に関しては実用に足りたかなと。

Tags: , ,

CodeJam Qualification Round 750点問題

September 7th, 2006  |  Published in Uncategorized

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

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

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

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

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


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

Tags: ,

CodeJam Qualification Round 結果

September 6th, 2006  |  Published in Uncategorized

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で鍛え直そうかな。

Tags: ,

CodeJam Qualification Round開始

September 6th, 2006  |  Published in Uncategorized

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

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

Tags: ,

CodeJam Practice : 1000点問題

September 5th, 2006  |  Published in Uncategorized

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

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

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

Tags: ,

Google CodeJam 2006 日程

September 4th, 2006  |  Published in Uncategorized

いよいよ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分かー。できるかしらん。


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

Tags: ,