2010-07 << 2010-08 >> 2010-09

2010-08-23 (月)

*GDD 2010 DevQuiz

日曜日にやろうと思っていたのだけど,どういうわけか起きたら夕方だったり,しりとり解いてたら眠くなってきたりしたので,時間的に厳しかった.

一応最低限の問題は解いたのでこれで大丈夫だといいなぁ.Super Hackers枠以外で点数取れる気がしなかったので他はスルーする.

三択問題

ぐぐればOK.

2-legged OAuth

rubyのOAuthの使い方が良く分からなかったのでPerlで.

Shiritori

1,2はPerlで一瞬.全探索して必勝条件を求める.もしかしたら,相手のミスが無いと勝てないのではないかと心配したけど,必ず勝てる問題だった.

3は時間かかりそうだったので,C++で書き直して駄目もとで走らせながら,スマートにとく方法を考える.けっこう悩んでも良い方法が出てこなかったのですが,辞書の中身を見ていたら簡単な問題だと気づいた.

PAC-MAN

手動で解くのは面白くないので避ける.

パックマン.これも1,2は最適解がすぐ出る.自機と敵機の状態を適当に配列に詰め込んでmapにメモ化しつつ,幅優先で書いた.

3色々考えたけど,最適解を求めようとしなければ,大丈夫だった.根本的な改善をするのは面倒なので,1と2を解いたプログラムに定期的に効率悪そうな経路をバッサリ切るコードを入れる.メモリが溢れてスワップするとWindowsごととても重くなってPCを再起動する羽目になるので慎重に調整.枝刈りが不十分なので,すぐに状態数が大変なことになってしまう.

少し心配.

…終わる直前で2が最適解じゃないことに気づいた.本来より長くなってしまう場合があったので,無理やり修正.少しよくなった.

gdd_devquiz.png

↑結果

パックマンはまだかなり改善の余地がある.

2010-07 << 2010-08 >> 2010-09