GCJ Qualification Round まとめ

結果はこんな感じになりました: http://www.go-hero.net/jam/09/name/k.kojima

どの問題も、基本的な知識があれば large まで解けるといったところ。Qualification Round にはちょうどいいレベルの問題じゃないかと思いました。A は特にアルゴリズムの知識がなくても解けそうですけど。

入力サイズがそんなに大きくなかったので、brute force でも間に合うかなー、と思いかけたけど trie 作りました。 CLISP なのであんまり速くないしもう少し頑張ったほうが安全かな、と考えて。

trie の実装にえらく手間取ったのとパターンの parse で変なことをした以外は簡単。

ちなみに後でやってみたら trie 使うより brute force の方が速かったりして残念でした。

グラフの連結成分を求める問題だな、と思ったので普通の DFS で。高度からグラフを作る部分と、グラフから連結成分を埋めていく部分とに分けました。書き慣れてない種類のコードだったのと、動けばいいやと思いながら書いたのとで汚い汚い。

テストケースごとに与えられるパラメータはグローバル変数にしてしまったほうが書きやすいと思いました。

どう見ても DP と思ったので適当に漸化式作って解きました。この問題が一番楽に解けました。

最後に答えを取得するための配列アクセスで添え字ずれててしばらく悩んだけど。