Marathon Match 34

http://www.topcoder.com/longcontest/stats/?module=ViewOverview&rd=12200

1位ゲット。名前赤くなっちゃいました。
GWだったせいか、上位に日本人が多数。

http://d.hatena.ne.jp/wata_orz/20080507/1210178014
http://d.hatena.ne.jp/EmK/20080507/1210177466
http://d.hatena.ne.jp/shinichiro_h/20080509#1210291122

多くの人は最初に左右を繋いでから肉付けする戦略だったようですが、私のはちょっと違ってて、結果的にこちらが当たりだったようです。
こんな感じの戦略でした。

  1. 左側のアクティブなノードを繋ぐパターンをたくさん作る
  2. 右側の(ry
  3. 1. と 2. の組み合わせで、スコアが最大になる繋ぎ方を探す

利点は 3. で結構枝刈りできること。

  • アクティブなノードの数が同じ始点から同時に探索できる
  • 現在の最大スコアを超えないことが分かった時点で探索を打ち切れる

など。欠点は 3. にかかる時間を見積もれないんで、制限時間を目一杯使えないこと。

で始点と終点のパターンのうまい生成法が見つからなくて悩んでました。探索のパラメータ変えるとスコア変わってくるけど決定版が見つからんなーと。そうこうしてるうちに wata さんに抜かれてしまったので、3. まで終わった後パラメータを変えてもう一度試すようにしたら抜き返せて、そこで終了。
全体的に時間余り気味なので、もう少し点数上がる余地はあったと思います。