Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2009-08-10SRM446 DIV2

SRM446 DIV2 Level Three(1000pt.) TopSubmissionコードリーディング

| 21:18

http://www.topcoder.com/stat?c=problem_statement&pm=10573

私が本番で解けなかった問題を1人だけJavaで回答した方がいらっしゃったのでコードを拝見してアプローチを調べました(Thank you, Mr.god_shiva!)。結果として探索全般に適応できるアルゴリズムであることが分かり、非常に大きな収穫となりました。今までのコーディングではTreeSetを使ったことはあまりなかったのですが、今後はPriorityQueueと合わせて積極的に使いたいと思います。

コードリーディングメモ(Twitterまとめ)

「良く分からないから総当たりするけど、優先度の高そうな方法から試してみる。優先度の判断はこっちでやるけどソートはTreeSetが勝手にやってね!」ということらしい。探索系の課題で応用が効く考え方では。

  • package private なクラスとして定義されているposクラスは、特定の世界(釘と円盤の組み合わせ)を表している模様。
  • pos#compareTo(Object)は「どちらがより完成形に近いか」を比べるメソッドであり、ステップ数の少なさと確定した円盤の枚数で決定される。
  • このcompareTo(Object)があるおかげで、TreeSetはよりゴールに近い操作を自動的に選択することができる。
  • 既に確定した(動かす必要のない)円盤は、String#substring(int)でデータとして削除してしまうのがおもしろい。確かに答えを得る上では既に必要の無いデータ。