ツイートを転載しておく。元々、別の場所に書いてからツイートしているので、まとめてあった方が読みやすいかな、という気持ちもある。
・コンテスト後のツイート
AtCoder Heuristic Contest 011 25Mに乗らず。
・最初は、AOJの15パズルをやってた（けど応用できなかった）
・木を探すパート：頑張って探す（乱択DFS）とN=6のときはそこそこ、7のときは時々見つかる。それより大きいときの見つけ方が分からなかった。
・15パズルパート：左上から頑張って変えた。
木の見つけ方が分からなかったのが致命的。
木を見つけることができないと、その後が敗戦処理みたいになるため虚しさがつのった。15パズルパートはもっと改善できたと思うけど、あまり木が見つかっていない状況でこっちを改善してもなぁ、という気持ちになってしまった。
・反省
結局、木を探すパートを乱択DFSでやったのが筋が悪くて、（大きい盤面でもDFSで木を見つけることは可能らしいが、難しそう）全部のマスに仮置きした後に調整していく、という方針を思い付かなくちゃいけなかった。
なんで思いつかなかったかというと、最初かなり長いこと（五日くらい？）、全てのマスのパネルについて隣のマスのパネルとの条件が満たされていれば完成盤面になると勘違いしてたんだよね。（複数サイクルが現れるので、ダメ）
勘違いに気付いたときに、木であることを満たしたままDFSする方法（leafへたどりついていないedgeの個数を記憶してDFSする）を思い付いたため、それでいける気がして実装を始めてしまったせいかと思う。
仮置きして調整していく場合でもこの考え方は使えるから間違ったことを考えていたわけではないんだけど、成功体験と結びついてしまったために思考を戻せなくなってしまっていたのかと。
あと、木を探すパートは初日にDFSかその類似でいけそうと思っていて、その後しばらく15パズルパートを考えてから戻ったせいで、DFSでいけそうという考えが自分の中で固定化していたかもしれない。
まあだから、終盤でも思考に余裕がないと……って話になるけど、それは難しいねー。
残り時間が少なくなると焦ってしまうし。時間が迫ってるのに順位が悪いとつい目先のことに飛びつきたくなるのはまあ仕方ない。
0 件のコメント:
コメントを投稿