本履歴

購入した古本の履歴と時々プログラミング

GCJ 2009

GCJ Round2で負けたので忘れないうちにまとめ(長め)。

結果

2009→http://www.go-hero.net/jam/09/name/uru
(2008→http://www.go-hero.net/jam/08/name/uru
去年はRound2を手を出すことすらできずただ呆然と指を咥えて終わったので、今年Round2で点を取れて終わったのはかなりうれしい。

まとめ

  • やっぱり上位はスーパーサイヤ人、あたしゃ戦闘力5の一般人。
  • 問題を理解するスピードが上がっていた。Space Alc(http://www.alc.co.jp/index.html)ほとんど使わなかったし。
  • Ruby1.9のArray##permutation,combinationは使えるので、みんな1.9にしましょう。1.9速いし。
  • 本を読んでいるだけではダメ。手を動かさないと身に付かない。
  • どんな手が出ない問題でもsmallはがむしゃらに取りに行かねば。ハングリー精神重要。
  • Golfやってて良かったな。
  • みんな参加しようよ!

環境

Notepad++(http://notepad-plus.sourceforge.net/uk/site.htm)と言うエディターを使ってコーディング。去年同様Rubyで参戦。irbも常駐。ちょっと試すときに何かと便利。後は、紙とペンを用意。sampleを解いたり考えた結果をまとめるのに使用。
解答の作成は、入力用の*.inファイルをダウンロードしたら、そのファイルをNotepad++で開き改行をWindowsに変更し、ctrl+A,ctrl+cでコピーする。コマンドプロンプトから

ruby source.rb >> ans.txt

とし(事前にしとく)、コマンドプロンプトに入力データを貼り付けてans.txt作成。source.rb, ans.txtをsubmitという流れでした。
また、前回からの反省点として、GCJ用の出力メソッドを事前に作っておいた。名前はPascal風。

def write(s)
       @@n||=0
       @@n+=1
       puts "Case \#%d: "%@@n+s.to_s
end

他の人のを探せばもっとクールな方法があるかもしれない。ソースコードが公開されるのもうれしい点だよね。

Qualification Round 2009

木曜会社から帰ってきて、夕食を食べてから取り組む。次の日会社お休みなのでゆっくり考えられる。メールで終了時間2時間延びーの連絡が来ていた。

A. Alien Language

問題を読んですぐに入力文字を変形し正規表現にしてマッチングすればいいじゃん、と気付く。
smallを通るプログラムはすぐに作れた。あなごるに感謝。ほっと一息付く。

C. Welcome to Code Jam

これも問題はすぐ理解でき、再帰的にプログラムを書いてみたらsmallが通った。そのままLargeにtryするけど、
通らず(そりゃそうだ)ちょっと意気消沈。

A. Alien Language

Aに戻って、正規表現でLargeも通るか思案する。しかし、組み込みの正規表現よりすごいものを自分で作り出すことができるとは思えなかったので消去法でLargeにsubmit。8分で処理が終わるかどうかドキドキタイムでした。

B. Watersheds

次に残ったBに取りかかる。elevation mapを高い壁で覆っておいて、左上のセルからそれぞれどの方向に流れていくか色を塗っていき流域作成。別の流域に流れ込む流域が出てきたら、2つの流域を同じ色で塗る、sampleを通すものが作れずドツボにはまる。色々直している内にソースコードが汚くなったので、気分転換に散歩に行く。もう一度落ち着いて(深呼吸)一から書き直したら、今度はいい線。sampleの一部で解答が異なる。問題を読み直したら、EとWを西と東と勘違いして生きて来た事が判明(Alcで確認!)。優先順序をEとWで変えてsmallを通せた。largeも8分で処理できた。

結果、76点で予選ラウンド通過!
通過メールでRound1は3回チャンスがあることが分かり、いい改善点と喜ぶ。

Round 1A 2009

土曜朝。ざっと全問題に目を通し、Aが一番簡単そうだったのでAから。

A. Multi-base happiness

各基数毎に、2..9999の間でhappy数を生成しておき、intersectionの最小値という方針で実行するがうまくいかない。どうも9999では小さいらしい。次に、与えられたn桁の数は各桁の平方和を取ると高々81*nとかなり小さくなるので、2..9999はそのままhappy数リストとしておいて、10000..99999まで各桁の平方和がhappy数リストに落ちるか?で各基数で2..99999までhappy数を生成し、同じようにintersectionをするもsmallでさえ通らず。時間だけが過ぎていく。落としたsmallのインプットで色々試行錯誤するも、数例出力がブランクになるものがあり99999以上必要らしい、けどどこまで事前に求めておけばよいか分からなかったので、保留すること決定。

C. Collecting Cards

次にCに移動。こんなの検索すれば出てきそう、ということで色々ググってみる。ようやくhttp://en.wikipedia.org/wiki/Coupon_Collector%27s_Problem を探し当てたが、カードが一枚の場合じゃん。ということで幻の公式を探しにググり続行。あっという間に1.5時間過ぎてしまう。その時カシオの数値計算ページ発見。カシオってこんなことやってるんですねぇ。

B. Crossing the Road

Bの問題を詳しく読んでみる。最短経路の本を読んでおけばアイデアが書いてあったかも、と後悔しつつBは自分には解けない子と判断。この時点でスコアを見ると、AのsmallとLargeを通せば1000位に入れそうなので、Aに全力投球決定。

A. Multi-base happiness

探索範囲をどんどん増やしていくが、プログラムの実行時間がどんどん遅くなり、色々考えた末、全ての基数のhappy数を生成する方法が頭悪い事が判明。例えば、2,3,5の基数だったらNが2進法でhappy数でなければ、3,5は調べなくていいから。というわけで、2..9999のリストはまず用意して一番大きい基数のhappy数を順次調べていき、それが他の基数でhappy数になっているかという方針でhappy数と分かったらstoreしておけば次回役に立つよねとぐちゃぐちゃ書いていたらタイムオーバー。0点。超凹みました。

Round 1B 2009

土曜深夜。Aはすぐには意味が分からず、後回し。Bは理解。Cも理解したが、解き方が全く思いつかないのでBから。

B. The Next Number

permutationを使える問題だけど、permutationの使い方が分からないので、ヘルプで調べる。digitsリストに0を追加し、pemutationでsmallを通せた。ヘルプ参照で時間を食ったが、いい感じだ。Largeもチャレンジしたが、プログラム全然終わる気配無しで撃沈。うまくpermutationのnextを取り出す方法があるんだろうなあ。

A. Decision Tree

次にCよりAをみんな解いていたので、Aの問題を読む。ふむふむカンタンじゃんというわけでしこしこ書いていくが、急にGolf神の天啓を得、インプット文字列evalすれば木が出来るんじゃね?と方針転換。うまくsubで入力文字列をRubyのプログラムへ置換し木を生成、木をトラバースしsmallが通った。Largeも通るだろうと落としてみたが、ここでeval時にエラー発生。文字列置換でどこかミスっていた! 8分内に修復を試みたが気が動転して果たせず。えーsmallでもそのパターン用意しておいてよーと心の中で叫ぶのであった。

C. Square Math

残り時間が30分ちょっとということで色々紙の上で考えるが、アイデアが出ずに終了。
19点で通過ならず。

Round 1C 2009

日曜の夕方。ざっと問題に目を通す。あのー、問題が明らかに簡単なんですけど・・・。ググるさんの優しさに感謝しつつ。Cの意味が飲み込めなかったのでA,B,Cの順決定。

A. All Your Base

最初に出てきた文字列から順に1,0,2,3,4...を割り当てていくだけじゃん、とプログラムを書くがsmall通らず。入力される数字を見ると1文字の場合もあることが判明。焦って3回間違えるがsmall通った。Largeも通りそうなのでそのままsubmit。間違っても、4分しか(?)ペナルティにならないので、とりあえず試してみるのは重要。

B. Center of Mass

燃えてるハエ?ほたるですよとAlcさんに教えていただく。簡単な物理の問題じゃんということで原点と直線上の点の最小距離を求める公式をググるさんに聞くがうまく出てこない。しかたがないと自分で紙上解くことに。t秒後の位置の原点との最小値ということでtで微分して出てきた。tがマイナスの場合は0にすることに注意して、small、Largeともsubmit。この時点で80分残っていて、かなり余裕ができた。

C. Bribe the Prisoners

よく読むと、問題を理解できたけど設定が不自然じゃね? なぜ両隣囚人全員に金貨を与えなければならないのだ、おまいは看守だろ! まず、smallを通すためpermutationで全パターンを調べる方針でsmall通す。この方法ではLargeは通らないことは重々承知の介。予習した動的計画法を使って紙上考えてみる。sampleの20,[3,6,14]での最小枚数をCoin(20,[3,6,14])とする。3,6,14どれを選んでも19枚(20-1)は必要。3を選んだ場合Coin(17,[3,11])、6を選んだ場合Coin(5,[3])+Coin(14,[8])、14を選んだ場合Coin(13,[3,6])それぞれ3つの中の最小値と19を足したものが求めるもの、と言うように再帰にし、一度求めたCoin関数はメモしておく方針で紙上で解けた!さっそくこれのプログラムに取りかかるが時間内に終わらず終了。DPってこんな感じかー
で、65点でRound1通過!

GCJ 2009 Round 2

土曜深夜。この日はあいにく会社があったので、帰宅後仮眠しGCJに備えた。ざっと問題を読む。4問か。Bはロードランナーだけど方針が分からず(チャンピオンシップ50面解いたのは遠い昔)。Cは問題の意味がすぐには分からず後回し。一番簡単そうなDから解く。

D. Watering Plants

2円で与えられた円集合をカバーするときの2円半径最小値。最初、Max[a,b]とかやっていてエラーになりあせる。[a,b].maxが正解。smallの場合が円の数が3だったので、combinationを使って2:1に分けて解くもsmall通らず。インプットファイルを見ると円の数が1,2の時もあるじゃん、というわけで場合分けをしてsmall通す。Largeはこの方法で通らないので別の問題に。Aが次に簡単そう。

A. Crazy Rows

問題をよく読むと右上三角を0にするswap最小値が求めるもの。ということは必ず、どこかの行に10000...か0000...があるはずだよね、それをまず一番上に持ってきましょう。という方針。(これが最小なのはなんとなくで気持ち悪いが、数学科はとうの昔卒業したので)。行列にせず正規表現で一行毎上からマッチさせることにした。次に、一番上に持って行った後は1行目と1列目を削ってn-1行列にし同じ事をすればOK。この辺、行列の行列式を求める時10000...の行を作ってラプラス展開した記憶が蘇る。small、Largeともにsubmit。さて、BかCか。

B. A Digging Problem

Bは人間系で解けば解けるのでは?と思われるので何もコード書いていないけどインプットファイルを落としてみる(この辺成長の跡)。びっしり50問あるじゃん。内容は5秒くらいで解けるものばかりだけど。一問もミスせず4分だとちょっと足りないか・・・。Cへ

C. Stock Charts

それぞれのgraphがタッチするかは最初の座標の差の符号が途中で変わるかを追えば良い。で、しこしこcontact flagのリストを作っていたら、ん??これってグラフの問題か? で紙に色々書いていてどうやってつながっているものを分けるのか検討していたら時間切れ。
21点で通過ならず。シャワー浴びていたら、これってグラフの彩色??ということが分かってきた。後日調べたい。
以上


通過した皆さん頑張ってください。ご活躍をお祈りします。
来年受ける方はご参考になれば幸いです。私もまたチャレンジしますので、uruをfriendに追加いただけるとうれしいです!