Hatena::Grouptopcoder

shinichiro_hの日記

 | 

2009-01-09

Marathon Match 47

01:25

tanakh さんがマラソンについて書いてたので私もこっちに書くことに。

めどいので問題について詳しくはこちら。

http://topcoder.g.hatena.ne.jp/tanakh/20090107/1231356535

やる気あまり起きないけど間を空けて2日くらいはやった。

アプローチはなんかたぶん全然違って、 trie を作ってその trie 使いながら回転しない面に適当に単語が途切れずにできるように探索して、色々できた可能性の中で一番得点が良いものを採用、とか。が確か初日。

間を空けてもうちょい頑張るかと思ってやったのが、180度回転した面は回転しない面と逆から進んでくので、単語を逆向きにつっこんだ trie を作って両方とも単語できるように作ってくようにした。あと適当な枝刈りつき再帰だったのを priority queue な探索にした。

そのへんでやめた。なんか discussion board とか見てると tanakh さん的なやりかたが多いみたいだなぁ。うむむ。さすがに適当すぎてレート下がらないか。

 |