HACK TO THE FUTURE2018予選 参加記録

コンテストページ:

HACK TO THE FUTURE 2018予選 - HACK TO THE FUTURE 2018予選 | AtCoder

1位でした。

やったこと

最初の1時間くらい

大まかな解法について考えた。「貪欲後に山登り」が直感だった。オーダーが落ちるレベルの高速化についても考えたが実装できそうな範囲では何も思いつかなかった。この時点ではコードは書かなかった。

1時間後~4時間後

貪欲を実装。あまりスコアが出なかった。高さ100の山が多くなっていたので、最初に多くとりすぎるのがまずいとおもい、同じ高さの山は10個までしか取れないようにした(99212…点、最終135位のスコア(コンテスト終了後に検証))。山登りを実装。遷移はx±1,y±1,h±1の6つ。無限にバグらせ、実装が終わった時には5時間がたっていた(99975…点、最終20位)。

4時間後~5時間後

 ごはん

5時間後~7時間後

山登りの収束チェックをする。余裕で収束しているようなので焼きなましを考える。

焼きなましを実装(99988…点、最終2位)。意外に得点が伸びる。回数をそんなに稼げないと思っていたので意外だった。

細かな改善をしてスコアを伸ばす(99989…点、最終1位)。高速化については何も思いつけなかった。

7時間後~終了

 パラメータを変えたのをローカルのバッチテストに投げたり、順位表のページでF5を押すマシンと化す。

 

考察、 感想

一般に順序が関係ないならば山登り、焼きなましをしたほうが良いが、問題サイズが大きくて試行回数を稼げないときは、順序を固定するなどして貪欲ベースの探索を行ったほうが良いことがある。この問題の場合、山を配置したり移動させるごとにどうしてもO(N^2)かかって試行回数を多くは取れない可能性があると思い、貪欲と微調整としての山登りを最初に実装した。やってみると山登りが楽に収束することが分かったので焼きなましをした。山登り、焼きなましの近傍は、第一に高速であること、第二にスコア差が小さいことが重要である。焼きなましの場合、局所的なスコアの上り幅の期待値が大きいことや遷移する確率が低そうなところを温度によって近傍から外すことなども重要である。今回の場合、大きく位置を変えても隣へ変えても速度的には大きく変わらないことと、小さく動かしたほうがスコア差が小さそうであることから、x±1,y±1,h±1を近傍にするのが良いと思う.。最終的には貪欲部分には0.5秒も費やさないようになった。ただし、ないよりはあったほうがスコアが良い。

 

結果的にアルゴリズムレベルでの高速化が大して必要ない問題だったのが運がよかった。アルゴリズムレベルでの改善が本質になるような問題もある。

最終1位とはいえ実装が遅かったり最終盤においてアイディアをあまり出せなかったり反省点は多い。本線も1位目指して頑張りたい。

 

Marathon Match 97 PointsOnTheCircle 参加記録

問題文:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17063&pm=14816

順位表:

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

provisional 1位でした。

終結果も変わらず1位でした

問題概要

N頂点の無向グラフが与えられる。各頂点を半径1の円周上に等間隔に配置する。辺を頂点間を結ぶ線分とみなしたときに、辺の長さの総和を最小化せよ。

最終提出の解法

焼きなまし法を使いました。

近傍選択について

 2点swapを行いました。swapする点の組の選び方は、

以下の二通りの方法のうちどちらかを50%の確率で実行するようにしました。

1.一点をN点の中から一様ランダムに選び、もう一点を選んだ点の近くから選ぶ。

2.辺を一様ランダムに選び、「一方の端点」と、「もう一方の端点の近くの点」の二点を選ぶ。

温度管理について

以下のような温度のスケジューリングを考えました。

縦軸が温度、横軸が時間です。

温度が0になるたびに、それまでに見つかった中で最も良い解へ巻き戻しています。

f:id:ats5515:20180201065134p:plain

遷移の条件式について

普通は diff<-T * log(rand())のようにするところを、 diff<T * rand()としています。

考察

問題がいかにも焼きなましだったので焼きなましました。

単純な問題設定の中でいかに差をつけるかを考えると、焼きなましを使うとすれば、工夫するところが近傍選択と温度管理しかないので、この2つについて集中的に考えてました。

近傍選択に関しては、swapする点を上に書いたように二通りの方法で選んでます。一つ目の方法はスコアの差が小さくなるようにという発想に基づき、二つ目の方法は局所的にスコアが改善される可能性が高くなるようにという発想に基づきます。

一つ目の考え方はよく見るのですが、二つ目の考え方はあまり見ないような気がします。swap以外にはinsertベースのものを考えましたがうまくいきませんでした。

温度管理について、最終的に特殊なスケジューリングになったのは、時間を延ばしてもそこまでスコアが改善しないことから複数回同じ焼きなましを行うようになり、さらに初期温度を線形に減少させていくことでスコアが改善されたという経緯をたどります。

 焼きなましを繰り返した方が有効なのは、厳密解付近での解の多峰性によるものだと思います。前回までに得た良い解をどうにかして利用したいと考えた結果、解を巻き戻しながら初期温度を減少させていくアイディアを得ました。この方法は、「焼きなましを100回やる。そのうえで初期値を減少させる」という見方のほかに、「1回の焼きなましがある。これを100等分し、それぞれの部分で一旦温度を0へ収束させるようにする」という見方ができると思います。全体としての焼きなましの機能を保ちながら、解の多峰性に対処するというのがこの手法の特徴だと思います。

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

Tco17 mm r1 GraphDrawingに参加しました

問題:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16903&compid=55119

順位表:

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

最終順位 5位でした。

 

問題概要

無向グラフが与えられ、各辺に対し要求長さが設定される。頂点を700*700の2次元正方形領域の格子点上に配置し、要求長さとの比の(最小)/(最大)を最大化する。

最終submit概要

2段階焼きなまし(もどき)したあと微調整

1段階目SA

頂点座標をdoubleでもち、要求長さとの差の2乗の和をエネルギーに設定

z方向への自由度を新たに設け、各頂点ごとのz座標の2乗の総和をエネルギーに加えた。こちらは時間の経過とともに重みを増すようにして、最終的にグラフがz=0の平面付近に来るようにした。

遷移は1つの頂点をランダムに動かす。動かし方はだんだん小さくなるようにする。

2段階目SA

2次元上で、エネルギー関数は、各辺に対しその辺の実際の長さをx,要求された長さをLとして、

E(x)=pow(A*abs(1-(x/L)),B)

を計算し、その全辺にわたる和をとったものとした。

この関数E(x)の値は、Bを大きくにしていくとxがある範囲より外側は限りなく大きな値で、内側は0に限りなく近い値という形になる。実際には、Bは100くらいの値に固定した。Aを調節すればこの範囲を狭めたり広げたりできる。Aを調節して現在のmin.maxより少し内側にこの範囲が来るようにした。

遷移は1段階目と同様一つの頂点をランダムに選び、ランダムに動かす。動かし方は1段階目より小さくした。

微調整

頂点を格子点に割り当てる。

辺の比が最も悪いもの(最大、最小の二つ)から1つをランダムに選び、さらにその辺の両端の頂点から1つをランダムに選ぶ。x座標かy座標またはその両方を選び、最大辺なら縮めるように、最小辺なら伸ばすように±1することで解を改善を図る。最良解が見つかるたびに解を保存しながら時間まで繰り返す。

全体的なこと

1段階目は5秒、2段階目は4秒、のこり微調整という時間配分にした。

遷移において700*700の範囲に常に収まるようにした。

最初入力された要求長さに0.95くらいかけたものを使った。

考察

 実際のスコアで焼きなましをやるのは解空間に高い壁ができてしまうので無理があると考えた。テストケースの生成において、最初にグラフを配置し長さを測ってからその値を少しずらすという方法を使っているため、この最初に配置された原型をまず再現しようとおもった。1段階目SAの発想ではそこから来ていて、差の二乗を使えば解空間はなだらかだし、最終的に良い解を得やすい頂点配置になってくれるはず。グラフを3次元空間内で動かしたのは、こうすることで局所解が緩和されるから。ただし正しい方向へ向かう割合は減るのでいいことばかりではない。

 2段階目焼きなましはコンテスト終盤に書いたもので、焼きなましを本来のスコア関数で使えるようにしようとしたものだが、最終的に焼きなましもどきになった。というのも、動かしてみたらエネルギー関数のBの値を大きな値で固定するのが最も良いという結果になったため、悪い方向への遷移はほとんど起きていないように思う。しかしこれでスコアは10K近く上がった。Bが大きな値固定になるくらいならわざわざこんなエネルギー関数用意する意味がなかったと思うが、検証している時間はなかった

 実は焼きなましが12日目くらいまで正しく動いていなかった(エネルギーの上昇がある値以下なら必ず遷移し、その値がだんだん小さくなるというベター山登り)。しかしスコアはそれほど悪くなかった(正しく直してもスコアは微増にとどまった)。焼きなましはあまりちょうどいい方法じゃなかったかもしれない。例えばよくモンテカルロ法の例として円周率の計算が出てくるが区分求積とかしたほうがよっぽど精度は高く出るといったように、確率的シミュレーションはほかの適切な問題固有の発想に基づくヒューリスティックスに比べて効率が悪いという可能性が常にある。

 doubleで管理している間は700*700おさめなくても後で平行、回転、拡大縮小すれば問題ない。しかし焼きなましの精度が悪くなったり、一部の点が外側に行き過ぎて、700*700に当てはめたとき狭い範囲に点が集まり、格子点に割り当てたときのロスが大きくなってしまうなどの問題がおきた。そのため、状態遷移において常に700*700におさめるようにした。代わりに要求長さをあらかじめ0.95倍しておくことで、適度に柔軟に頂点を配置できるようにした。なお焼きなましの精度が悪くなる理由として、テストケースの生成でははじめに原型を作るので、700*700に収まるというのは良いヒントになっているからだと思う。

考えたこと(時系列順)

日記などをつけていないので細かいところは覚えていないですが。

・コンテスト開始直後

なぜか1000K付近の高得点勝負になると思っていた。頂点をdoubleで持つ発想、微調整のアルゴリズムの発想はこの時点であった。

・3日目~6日目くらい

初めてコードを書く。山登りが全然だめと分かったので、焼きなましを書く。微調整パートも書いて720Kくらい。この時点で焼きなましはバグってる。

順位表の1位が780K強で飽和しているように見え、100K付近の高得点勝負ではないとこの時点で気づく。

要求された長さに1より小さい一定数をかけておくとスコアが上がるのに気付いた。

・7日目~11日目くらい

焼きなましと微調整の間に物理シミュレーションを置く。比が最大、最小付近の辺に特別に大きな力が加わるようにした。それ以外は時間がなかったため流れ作業でできるようなパラメータの調整しかしていない。780Kくらい

12日目

焼きなましがバグっているのに気づく784K

13日目

最後の「微調整」パートだが、実はこの時点では全然微調整ではなく、この部分で大幅にスコアが伸びるという感じだった。ただ「微調整」パートの内容的にやはりこれは字義通り微調整であるべきだと思い、物理シミュレーションの上位互換を考え始める。

2段階目SAの発想に至り実装。パラメータの調整、高速化を少々。788K

14日目

大学のレポート類がやばくて何もできなかった。完全にスケジュール調整ミス。あると思ってたパラメータ調整にかける時間がなかった。最後改善しているかどうか定かでないものをやけくそで提出し終了。791K

反省点

・最後パラメータ調整をしている時間がなく、適当に決め打ったまま最終提出まで行ってるパラメータが結構ある。テストケース数も100ケースだけで判断していたのでシステムテストでは順位が落ちそう。実際終了後ローカルで500ケースだけ実行したところ、794K点くらいでprovisional6位のtomerunさんは796K出ているそうなので少なくともここの順位は入れ替わりそう。しかも、僕の実行環境は(おそらく)topcoder鯖より性能がいいので、もっと低く出そう。いくら時間がなくてもちゃんとケース数をとってテストするべきだと思った。どうせ差が微増にとどまるから、改善しているかどうか判断できないので、パラメータの組み合わせ数を稼げても意味がない。

追記:システムテストが終わり、provisional6位のtomerunさんには抜かれたがprovisional4位のpsyhoさんを抜いて順位変わらず5位でした。

・パラメータ調整をもっと機械的に、あるいは自動でやってくれるものを作っておくべきだったのかもしれない。

・焼きなましをバグらせているのに12日間程気づかなかった。明らかにパラメータを最適化するとおかしい値になっていたので、原因を探しに行くべきだった。

・コードが汚い。

さいごに

反面教師でもなんでもいいので何かの参考になればと思います。

round2も出ると思うのでよろしくお願いします。