TCO2017 MM R1 参加記
TopCoder Open 2017 MarathonMatch Round1に出た。
暫定順位：26位、暫定スコア：760227.81
最終順位：25位、最終スコア：759141.67、獲得ポイント：6
問題：GraphDrawing
問題概要
グラフの情報が与えられて、各辺にはそれぞれ適切な長さがある。スコアは、各辺における「適切な長さに対する実際の長さの比率」のうちの「最小比率 / 最大比率」で出される。これを最大化するように頂点をグラフに配置する。
グラフは700*700のサイズ
10 <= NV(頂点数) <= 1000
NV-1 <= NE(辺の数) <= NV * min(10, (NV-1) / 4)
やったこと
- 初期配置はランダム
- 辺の比率はセグメント木で管理、更新O(logNE)
- -----ループ(1)-----
- 一番比率の悪い辺につながっている頂点(A)を動かす
- 頂点(A)はなるべく前回や前々回に動かしたのとは別の頂点を選ぶ
- スコア(C)=0を用意する
- -----ループ(2)-----
- 頂点(A)につながっている辺を除いた辺だけでのスコア(B)を出す
- 最初のほうはスコア(B)を1とする確率を高くする(スコアが一番よくなるとこに進むようになる)
- グラフの範囲をいくつかに分割
- 分割の数は時間とともに大きくする
- 頂点(A)を含む部分とその8近傍それぞれでランダムに配置
- スコアがスコア(B)よりよくなるならば、スコア=スコア(B)とする
- スコアがスコア(C)よりよくなるならばスコア(C)を更新する
- スコア(C)が更新されていれば、スコアが一番いいやつからランダムに選んで頂点位置を更新
- (2)に戻って配置される分割された範囲内で同じことをする
- スコア(C)が更新されていなければ(1)へ
感想
今回は比較的複雑なことをしなくてよかったので楽だった。楽だったのに、この順位ではダメな気がする。
ほかの人のやり方を見てるとそっちのほうがよかったと思えてくる。
まともなローカルのテストができるようになった(コンテストが終わった後)ので、次からはTestやsubmitの回数が減るはず。今までは１つのケースに２mとかかけてたが、ちゃんと10sでできるようになった。
公式のビジュアライザは画像を保存してくれなかったので、MM93のをもとに保存するようにしたが、見てもあまりわからない。
今回はギリギリ正のポイントをとれそうだが、Tシャツ得るためのポイントのボーダーどれくらいになるんだろうか？
圧倒的説明力不足を感じた。
ローカルテストのスコアをプロットしてみた。
次からはこういうのも確認しつつやっていこう。
