TopCoder Open 2017 Marathon Round 1

2017/04/27 (Thu) MM

問題文

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16903&pm=14565

グラフが与えられる.頂点を平面に配置したい.ただし各辺には希望する長さが与えられて,それに近い長さになるようにせよ.スコア = 比の最小/最大 である.

Submission 1

問題がシンプルで神。 読んですぐ CS Academy のグラフエディターを連想し、辺をバネだと思ってシミュレーションする方針を思いつく。また、確か graphvis に焼きなましの実装があったはずでそれもよさそうだと何となく考える。

「全ての辺の desired と現在の長さの差分に比例する力を各頂点に加え、累積された力の大きさに比例する距離だけ移動させる」を時間いっぱい繰り返すのを実装する。 いろいろやってみると、バネ定数は、大きすぎると頂点が四隅に偏ってスコアがほぼ 0 になり、0.2 から時間がたつほど小さくなるようにするとよい結果になる。焼きなましと同じノリなんだろうか? 時間の調整が難しかったから小さいループを何度か回すようにしてみたらなぜかスコアも上がる。

提出しようとするが register のリンクが壊れていてできなくてクソ。Twitter で検索したらそれらしき情報があって解決する。

サンプルの方に提出してみると seed = 1, 2 のときだけ “Failed to get result from plot.” になる。なんだこれは… また 1 時間近く悩んだが、サーバー環境では clock 関数を呼びすぎるとこうなるらしく、 rdtsc に変えたら動いた。

出すまでがつらかったが、意外と良かったらしく3位でビビる。

生スコア : 384461.28 なお、この後スクショで実行中の tomerun さんに一瞬で抜かれた。

seed = 3 での各辺の長さはこんな感じ。

submission1

Submission 2

Psyho が意味不明なスコアをとっているので別の方針なんじゃないかと考えるが、よく分からないのでビジュアライザを作って色々と様子を見ることにする。

入力に長い辺は少なめらしい。generator の実装的にそれはそう。 長い辺の両端を動かすとそれに接続する短い辺が伸びまくってスコア激落ち。 短いと良くしやすいが数が多く厳しい。 長い辺と短い辺に分け、長い辺を調整した後、短い辺を調整するとよさそうに思ったが、いまいちスコアが上がらない。 さっぱり分からないので、ループ変数 mod 3 を見て、短い辺の改善:長い辺の改善を 2 : 1 にするとスコアが約 20% も良くなる。 やっぱり分けるのは良いらしいけどそんなによくなるものなのか???

gnuplot つらいので、グラフ描画を matplotlib に書き換える。Python の環境構築にめっちゃ時間がかかった。

生スコア = 490598.6
図は seed 3。赤が y=x でオレンジは y={最大,最小}x。

submission2

Submission 3

この問題,スコアはボトルネック (=最小/最大) で計算されるんだよなー. ということは図のオレンジの線付近のプロットをどうにかしないといけない(今更).

あと,実験してみると,やはり mod 3 で場合分けは単に撹拌してやりなおしている以外の意味が無さそう. 今までのは決定的だから乱数要素入れたほうが良さそう.

どう改善していいかわからないので,「かかる張力の二乗和が大きい頂点上位30個を一様ランダムな場所に移動 -> バネシミュレーション -> スコアが上がっていたら遷移」を繰り返す山登り法を書いてみるとスコアが上がった. 焼きなましをやってみたが,毎回のバネシミュレーションが重くてループが200回しか回らないせいか,たいして山登りとスコアが変わらない. でもなんとなく期待を込めて焼きなましで提出.

生スコア = 666716.88

図は seed 3。

submission3

もう諦め

終了後

最終結果 -> https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16903
41位でした.

agwさんが作ってくれたまとめ https://togetter.com/li/1099931

以下はすごいと思ったもの