TCCC06 Qualification Round 1

Program

TopCoderから送られてくるメールが出ろ出ろとうるさいので、
2006 TopCoder Collegiate Challengeなるものにも出てみました。
なんだかルールの記述がやたらに長いのであんまり読めてなくて
参加資格があるのかどうかも良く分かっていませんが…。
レートが高い人はQualification Round免除、
他の人はいずれかのQualification Roundで勝ち抜ければ良い、でOKなのでしょうか。
なんだか、Qualification Roundはまだ2回あって、
参加登録もまだ受け付けているみたいなので、興味のある方はどうぞ。
私はレートが低いのでQualification Roundから参加しました。


http://fxp.hp.infoseek.co.jp/img/tccc_2006_qr1.png
普通のTopCoderのルールと同じで、3問75分、チャレンジありでした。
上位450位が次に進出なのに、参加者が700人弱しかいなかった…。


250点問題
http://www.topcoder.com/stat?c=problem_statement&pm=6698&rd=10093
よく考えると、ソートして、前半を加算、後半を減算すれば良いだけ。
サイズが非常に小さいので、ナイーブに再帰的にとか書いても良いけど、
ナイーブに書かないほうが楽なんではないでしょうか。


500点問題
http://www.topcoder.com/stat?c=problem_statement&pm=6505&rd=10093
男女交互に身長順に並べよ、解が複数あるならレキシコ順、という問題か。
男女それぞれ分離してソートして、インターリーブして(高々二通りの方法で)、
それが条件を満たしているか調べるだけのような感じ。
レキシコグラフィカルというのが、辞書順なのか、アスキー順でいいのか
良く分からなかったので、びくびくしつつも面倒なのでアスキー順で提出。


1000点問題
http://www.topcoder.com/stat?c=problem_statement&pm=6667&rd=10093
15パズルの円筒版のような問題ですが、
有効なヒューリスティック関数がわからないので、IDA*で解くのは厳しそう。
そもそもIDA*は計算量の上限が見積もりづらいですが…。
イラストに反してサイズが3*4までなので、
幅優先で解いてしまってよいと思うのですが
(状態数が40万ぐらいにしかならないので)
あとでいろいろ試したのですが、この問題はそれでも厳しいです。
最後のサンプルが手元で6秒ぐらいで解けるのが精一杯というところ。
本番中はなんか勘違いして単にキャッシュつき深さ優先探索をしてしまって、
どう考えてもスタックがあふれるような状態で提出してしまい、
当然のごとく一瞬でチャレンジされてしまいました。
いずれにせよ、これはかなり難しい問題では無いでしょうか。
高レートの人が参加していないとはいえ、一人も正解者がいませんでした。


出したコードは
http://www.topcoder.com/stat?c=problem_solution&rm=249604&rd=10093&pm=6698&cr=22627322
http://www.topcoder.com/stat?c=problem_solution&rm=249604&rd=10093&pm=6505&cr=22627322
この辺から見られるようです。
こっちも出来るだけ進めるように頑張ってみますか…。