MarathonMatch94

MM94お疲れさまでした。

まず全体的な方針として左上から詰めていく(順列を表すvector(以下ansとする)に前から順番に要素を追加していく)ことにした。

理由としては以下の2点

①どこに一番得点が高い組み合わせを置いても同じだと思ったから。

②左上にそろえることでansにi個目の要素を加えたときに実際に行列を並べ替えやすいと思ったから。

あと、Sによって場合分けをした。

S>300のとき、

ビームサーチをしようと思ったらめちゃくちゃ時間がかかったので諦めて重みをつけて貪欲を何種類か回して一番スコアがいいものを採用した。

S>200のとき、

ビーム幅2でansをビームサーチした。愚直にビームサーチをしようと思ったらTLEしそうだったので、遷移は明らかに効率の高いものから1/2~1/20ほど試した。

それ以外のとき、

ビーム幅～80ぐらいでビームサーチ。愚直に回した。

ビームサーチ時には、左上からの累計スコアを鍵にしたが、ansに値が付け加えられるごとに毎回スコアを求めていたら身がもたないので、ansのi要素目まで加え終わったときのできるだけ右の点、下の点の中で左上と連結なものを保持しておき、i+1要素目を加えた際には、それらの点からのみBFSすることによって軽量化ができた。

seed 1~10の得点

1:191.83

2:14569.48

3:855662.71

4:114065.16

5:132683:85

6:52594.78

7:212035.44

8:485259.06

9:1312646.12

10:235352.26

コードのURL

https://github.com/olphe/MM/blob/master/MM94.cpp