TCO13 MM R2
-
masashinakata
- 10608
- 1
- 1
- 0
-
- いいね！0
tomerun
@tomerun
いやまあビームサーチはいいとして重要なのは評価関数の設計ですが。今回はここが全く自明じゃなくて難しかった（もちろんスタート地点としてのgreedyはありますがそこから先が）
2013-05-16 02:06:09
chokudai(高橋 直大)@AtCoder社長
@chokudai
50～100の各Nに対して、最低手数が即答できない人、結構いると思ってるのだけど、もし即答できなかったらちょっと調査不足なので反省しましょう＞＜ #TCO13MMR3
2013-05-16 02:06:53
Komaki
@Komaki__
手元で点数あげても高速化しても微動だにしない点数に恐れおののいた。手元では1.0くらい上がって、最後に結構高速化してTLE避けの減速も回避したのに-0.01点されてしまった。
2013-05-16 02:08:22
とーらす🌸📦🌕✨🍀
@torus711
残りの数で評価関数にしても割と妥当っぽいとするとビーム幅の問題という話になって、もっと多くのアレを次に残しつつ探索できればよかったのかにゃー
2013-05-16 02:08:51
かわてぃー
@kawatea03
最初は完全に探索だけの方針だったけど、途中で解を複数持てばいいことに気付いてかなり点数が伸びた。けどよく考えたらただのビームサーチだった。
2013-05-16 02:08:58
chokudai(高橋 直大)@AtCoder社長
@chokudai
評価関数は、まぁ差分で取れる要素ってかなり少ないので、・残り個数 ・各列、行の残り個数あたりから頑張ってくださいな、って感じになるのかな。Nが奇数と偶数で評価関数分けるのも多分大切 #TCO13MMR2
2013-05-16 02:09:05
tomerun
@tomerun
評価関数の要素は ・残っている鏡の個数 ・行・列ごとの残っている鏡個数の偶奇（偶数の方が良い） ・空になった列の数（多い方が良い） を使った
2013-05-16 02:10:39
ぷち＠プログラマ日本一です
@takapt0226
なるほどー上位陣が言ってる評価関数のポイントは少し気になってはいたけど、結局関係ないやろｗｗで片付けていた （偶奇とかは全く気づかなかった
2013-05-16 02:12:26
Komaki
@Komaki__
評価関数は各列に対して、光が鏡に当たって出ていく期待値X(N) = 1 / n * (X(N - 1) + 1) + (n - 1 / n) * X(N - 2)にした。
2013-05-16 02:15:22
chokudai(高橋 直大)@AtCoder社長
@chokudai
2*8にいっぱい敷き詰められた状態と、4*4にいっぱい敷き詰められた状態で、差別化出来ないとちょっと辛い気がする。後者の方がだいぶ良い。 #TCO13MMR2
2013-05-16 02:16:15
かわてぃー
@kawatea03
評価関数は残りの鏡の個数と鏡の縦と横の関係を使った。偶奇もちょっと考えて試したけど、ほかの要素との関係かうまくいかなくてやめた。
2013-05-16 02:16:41
chokudai(高橋 直大)@AtCoder社長
@chokudai
ちなみに最初のツイートですが、偶奇性を考えて、Nが奇数のとき最低でもN回の試行が必要です。Nが偶数なら多分1回でOK #TCO13MMR2
2013-05-16 02:17:17