本履歴

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

GCJ 2011

残念ながらRound1通りませんでした。まあ、楽しかったのでヨシとしますか。

Round 1A

土曜朝。ちゃんと起きられた。Rubyでやる。問題文をざっと読んで、Cが理解できなかった・・・Aから。

A. FreeCell Statistics

解法が全然わからず、紙の上でいろいろやって時間を費やす。
そもそも、今日の勝敗と全体の勝敗がどう関連するのかが分からない・・みんな解いていてかなり焦る。
30分くらいいろいろやって、今日の勝率が100%じゃなければ、全体が100%になるわけがない、からやっぱ関連があるよねー、ということに気づく。
今日の勝ち数・負け数と今日以外の勝ち数・負け数で式を作って変形したらax+by=dのユークリッドアルゴリズムっぽくなった。
でも、この時点で既に1000人がA解いているので、みんなが解けていない問題を解こうと、Bへ。

B. The Killer Word

問題文を読解するのに時間がかかる。4度くらい読み返してようやく理解でき、プログラム開始。
smallをとりあえず通したい(この時点でAとB smallでOKな感じ)。
単語リストは長さでグループを作っておいて、各アルファベットのオーダーごとに一番スコアがゲットできるのを見つける愚直な方法。
3回くらい書き直し(問題文勘違いもあり)、ようやくテストケースをパスするものが作れる。で、small correct!
Largeは解けそうもないのでAへ。

A. FreeCell Statistics

最後の30分でAに全力。でも残念ながら、果たせず。2312位!

Round 1B

仮眠をとって準備万端。土曜深夜スタート。問題文を読んで、全部理解できた。Aは配列操作がRubyだとめんどいので、後回し。
C->B->Aの順。

C. House of Kittens

紙上で色々実験したところ、分割された多角形の最小辺数が求めるものCっぽい。
これを求めるプログラムを書く(n=4角形、2-3結ぶ壁が与えられたら、[[1,2,3],[2,3,4]]を返す関数)。
色々はまって1時間くらいかかる。
次に、その数字を各頂点にうまく割り当てて解答としたいのだが、ここでもはまりまくる。
分割多角形の辺のお隣どおしは違う色で塗ったほうがいいよね、ついでに最大の色も使いたいよねーを両立するプログラムが書けない!
どうも、最小辺数を返す関数の中で隣接しているかどうかの情報が欠落しているようだ・・・
2時間はまって、最終的に各頂点にランダムで色を付け、それが条件(分割多角形内で)を満たすかという方向に変更。
N=8で壁なしの時とか時間内に終わらなくね?とか考えて変な最適化をしていたら、Time up。1問も解けず。

Bがバイナリサーチと後で知り、目から鱗でした。4557位!

Round 1C

日曜18時。Aの問題文を読んで、簡単なのでAから行く。みんなどんどん解いていく、速すぎ。

A. Square Tiles

まず#の数を数えておいて、4の倍数でないならImpossible。
次に左上から順番に、正方形4マスが#なら#の数を-4&&その4マスを'/' '\'で置き換える。
最終的に#の数が0になればそれを出力。そうでなければImpossibleという方針で解けた。
Impossibleの出力が改行するというところでWA食らったが、25分で解けたのはかなり上々。

C. Perfect Harmony

GCD関数を用意するが、とりあえずで書いたLowからHighを全部調べる方法でsmallは通った!

B. Space Emergency

ブースターがいつどういうタイミングで作ることができるのかが分からず、時間が無駄に流れる。
テストケースも、片方合うともう片方が合わないという感じ。
結局、最初出発するときにオーダーできるとするとテストケースが合うのでその方針でコーディング。
1WAの後、なんとかsmallが通った。この時点で900位くらいだったのでどうしようか検討していたところ、
1000位以下に落ちたので、ダメ元でC Largeに突撃!撃沈!

結果は1013位!あとちょっと、でした。んがんぐ