Marathon Match 94 ConnectedComponent 参加記録

問題:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16958&compid=57152

順位表:

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16958

 

provisional2位でした。

現在システムテストが行われています。

最終順位も変わらず2位でした

 

問題概要

S×S行列Mが与えられる。行列の各要素は-9から9までの整数である。

0からS-1の順列pに対し、行列MPを、MP(i,j)=M(P_i,P_j)と置く。

 MPの、0以外の要素からなる連結成分ごとに、(要素の合計)×(要素数)^(0.5)を求める。その最大値を最大化するようなpを求める問題。

方針

端から決めていくビームサーチ。

評価関数

答えの順列の最初のn個が決まっているとき、行列MPの左上n×nは固定される。

この領域において、ある連結成分の要素の合計や要素数などの量を計算して、評価値を計算する。

 

具体的には、深さをdepthとして、

(評価値)= (要素の合計)×(要素数)^(0.5+(Sの1次式)×(1-(depth/S))^(定数))

(Sの1次式)=0.4+0.3×(S-50)/(500-50)

(定数)=0.1

ポイントは、合計値より要素数に重みを置いたこと、探索が進むにつれて真のスコアの式に近づくこと。

ただし、真のスコアと同じ式をそのまま使った場合と比べても改善幅は大したことない

状態遷移

答えの順列のn+1番目を、(S-n)通りの候補に対し全探索します。連結成分をUnionFindで持っておき、必要な部分だけ書き換えれば一つの状態を作るのをO(S)でできる。

f:id:ats5515:20170824145053p:plain

↑必要な情報は右図のように圧縮できる。

ビームサーチ全体では、深さO(S)、一つの状態に対する遷移先O(S)個、一つの状態を作るのにO(S)で全体でO(S^3)でできる。

時間管理

 ビーム幅をうまく調整しながら、ちょうど時間を使い切ることに挑戦した。

nターン目では、(S-n)通りの候補に対して、O(n)で状態を更新するので、かかる時間は、(ビーム幅)×(S-n)×nに比例すると考えられる。これまでのかかった時間からこの比例定数を求め、時間ちょうどに終わるためのビーム幅を毎ターン計算した。

考えたこと

最初に問題を見て思ったのは、焼きなましたいが時間がきつそうということ。

一般に時間が十分にあるときは、焼きなましのように文脈無し問題として解くのがいいと思うが、今回は問題サイズが大きく、時間が足りないと感じた。

実際書いてみると、解の要素をランダムにswapするのを近傍とする山登りは、時間内に収束させることができそうにない。

次に他の可能性として、近傍を工夫する、文脈ありとして解くなどを考えた。結局は、どういう方針をとるにせよ、ただの高速化勝負でないとすれば、計算量レベルでの改善が必要だと考えた。解の順列の値を順に定めていくことで、差分計算が利くことに気付きBeamSearchを実装。大きいケースでは山登りを10分続けたときと同じくらいのスコアが出て、方針が間違っていないことを確信した。

その後は時間管理や評価関数の細かいところを調整しただけで本質的な改善はできなかった。

2位になってからローカルで15パーセントくらいスコアを上げたが、1位の順位表の得点は全く削れていなかったので、1位とはかなり差があると思われる

終結果ではかなり僅差となったので、1位まであとちょっとだったらしい。

実行結果

seed=2, score=22740.49

f:id:ats5515:20170824161118p:plain

seed=5, score=203385.38

f:id:ats5515:20170824161431p:plain