MM94 ConnectedComponent
問題文 https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16958&pm=14678
基本方針
順列の左端N個が確定しているとすると順列の後ろにどんな値を足しても左上N×Nの領域の値は変わらない。なのでこの確定領域の最良コンポーネントのスコアを途中状態のスコアとできる。
そして現在の順列の後ろに値を足して一番途中スコアが大きくなるような順列を次の状態とするgreedy/beamsearchをすると最良コンポーネントが徐々に大きくなり良い解が得られる。
高速化
途中スコアの愚直な計算はO(S2)であるためgreedyですら終わらないが、新しく足す値によって確定するマス(下図赤マス)と接するマス(下図緑マス)は現確定領域の"外周に限られる"ことを利用して差分計算/更新ができ高速になる。
具体的には緑マスそれぞれをノードとしたUnionFind(各ノードはそのマスが属すコンポーネントのsizeとsumを持つ)を現状態として持つ。次に緑UFを元に緑赤UFを作る。次に連結箇所をuf.unite()。最後に赤だけのUFを作ればそれが次状態になる。このとき連結を調べているのが外周付近だけであるためO(S2)がO(S)に落ちてgreedy/beamsearchが実行時間に収まる。また、UFを舐めればsumとsizeを持っているため最良コンポーネントとそのスコアがわかる。
このUnionFindを使って連結情報を右に右に伝えていくというのはこの問題でも使われてるっぽい。 http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2017%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=H.pdf
ビーム幅
同じseedで繰り返し実行したときのスコアの分散が大きめだったので、ビーム幅の増加によるスコア上昇よりも、細いビーム幅で繰り返したときの当たる確立の上昇のほうが強いと踏んで、ビーム幅1のビームサーチを時間いっぱい繰り返した。だけど1stと2ndは大きなビーム幅で1回ビームサーチらしいので外したっぽい。分散が大きいというのが違うのか、分散が大きいときは~のほうが強いというのが違うのか。
評価関数
最良コンポーネントの近くに他のコンポーネントがあって繋がると大きなスコアのプラスになるとき積極的に繋がりにいきたい。
これを評価関数に加える。他のコンポーネントはsumが大きいほど、sizeが大きいほど、近いほど(繋がりやすいことと連結に近づくため)良いとしたい。なので最良ではないコンポーネントそれぞれに対して、仮に最良コンポーネントと繋がったときのスコアの上昇量にpow(0.9, 最短距離)をかけたものを途中スコアに足した。
文章だとわかりづらいので擬似コード
double maxComponentScore = maxComponent.sum * sqrt(maxComponent.size); double score = maxComponentScore; for (auto& c : nonmaxComponents) { double connectedScore = (maxComponent.sum + c.sum) * sqrt(maxComponent.size + c.size); double diff = connectedScore - maxComponentScore; if (diff > 0) score += diff * pow(0.9, manhattanDistanceNearest(c, maxComponent)); } score; // これがビームサーチの評価値として使われる
1st, 2nd, 3rdまでの評価関数のプラスアルファがバラバラなのおもろい。
山登り
Sがごく小さいときはビームサーチの結果を山登り。ランダム解から登るより、ビームサーチからのほうが良かった。近傍は2つをswapと、1つを別のところにinsert(つまりrotate)の2種類。左上からビームサーチする都合、左上が高密度のコンポーネントができるので左上へのinsertで改善しやすかった。なのでその近傍を先んじて試すようにした。2つの近傍自体に優劣はないと思うんだけど、初期解が影響して優劣が生まれるというのがおもしろかった。
評価関数はO(S2)だがy_kawanoさんがchokudai contest(本問題と似ていて連結数を大きくする問題)で使っていたテクで数倍早くした。自力で思いつける類ではないので感謝
得点計算の高速化はDFSの基点となる位置をキャッシュしたのが効いた #chokudai_003
— y_kawano (@y_kawano) 2017年2月21日
やりたかったけどできなかったこと
非0マスの割合によって連結の容易さがテストケースごとにかなり変わる。最終コンポーネントがスッカスカだったりミッチミチだったり。この特徴に注目して何かヒューリスティクスを刺したかった。
Example scores:
0) 232.826115373684 1) 23147.483599734984 2) 7426823.502824272 3) 121935.2517568238 4) 148933.58515123444 5) 2259336.504998536 6) 733271.118536657 7) 3257617.5326836635 8) 4670802.284891322 9) 1676018.7939363925
Image
seed=2, score=21907 pic.twitter.com/iIdLh9hhtg
— hakomo (@hakomof) 2017年8月24日
seed=3, score=7488480 pic.twitter.com/sYuESDhLFf
— hakomo (@hakomof) 2017年8月24日
seed=7, score=726365 pic.twitter.com/oJEr6GoE1l
— hakomo (@hakomof) 2017年8月24日