TCO18 MM R2 CrystalLighting 参加記録

問題文:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17179&compid=64279

 

 順位表:

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

 provisional8位でした。

記事にするようなことをしていないので一般的な話も含めて書きます。

やったこと

焼きなまし。

近傍

遷移は各アイテムを置くor消す、ランタンを自分の発する光が通るマスへ移動。

 

焼きなましの近傍の選び方の基本は、高速に動作すること、解空間が滑らかになること(遷移によるスコアの変化量が小さい、任意の状態から別の状態への遷移回数が少ない)。そもそも焼きなましが有用かはそういう近傍が存在するかで判断できると思う。

各アイテムを置くor消すは自然で思いつきやすい。移動が有用なことも焼きなましに慣れていれば割と思いつくと思う。光線に沿った移動は、基本的に変化が4方向(2光線の削除+2光線の追加)になるので、設置、削除の近傍に劣る理由がほぼない。

評価関数

 

各アイテムのコストを0から真値に線形に変化させた。

一般に、焼きなましの評価値が真のスコアであるという保証はない。だから、設計の最初の段階でそれを意識した方が良い。意識しないと、「真のスコアで焼きなましてベストスコアを保持してロールバックしたりする」みたいな工夫をした後で、真のスコアでない値で焼きなましをしようと思った時に無駄に実装コストがかかるようになってしまう。

僕はこれが原因で、上位陣がやっていた、2色のうち一方のみで照らされるクリスタルのコストを変化させるということを試さなかった。正確には、試したけどスコアが改善しないと勘違いした。試したとき、実装上の都合でイテレーション回数の増加という副作用が起きていて、スコアが改善しなかった。この副作用は時間をかけて実装をやり直せば起こらないものだった。

遷移の実装

実装は、各マスを通る光線を愚直に(差分計算はするが)シミュレートするというもの。ランタンが置ける位置のリストなどを保持することができる。遷移回数は6千万程度になった。

反省

遷移の実装に関して、一本の光線が通るマスでグループ化し、各マスからある方向へ行ったらどこでぶつかるかを保持しておけばもっと高速に同じ遷移を達成できた。ランタンが置ける位置のリストを保持などはできないが、アイテムの移動が遷移として有用なので、遷移提案のオーバーヘッドはほとんどなくなると思う。

とりあえずのつもりで愚直な実装をしたら費やせる時間の9割を消費してしまい、これを試す余裕がなかった。最初、実装が思いとは思わなくて両方試せば良いと考えた(やってみるとややこしい要素が多い)。もっと最初に構想を練っておけば良かった。

使わないコードをほとんど書かなかった割に2000行とかになったので、今まで参加したMMの中で一番実装重かったかもしれない。

最初に思いついたことをコンテスト中に消化できなかった。コンテスト開始直後の自分に、実装する前に紙に書いて整理することと、めんどくさがらず考えたことを試すことをアドバイスしたい。

 

TCO18 MM R1 RoadsAndJunctions 参加記録

問題文:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17153&pm=14907

順位表:

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

問題概要

平面上にN個の点が与えられる。一点当たりコストCで最大2N個の点を加えることができる(位置を重複させてはならない)。新たに加えた点は、それぞれ確率Pで消滅する。(最終的に得られる点群の最小全域木のコスト)+C×(追加した点の数)をraw scoreとし、(best/your)^2を最大化する。

やったこと

点をばらまき最小全域木をもとめる。次数が2以下のものを取り除き、木構造を固定した状態で山登りをする。ないほうがよさそうな点を削除し、評価値を求める。

以上までを1遷移として焼きなました。

同じ位置に点を重複させた方がいいこともあるので1つずらすなどして配置した。

評価関数は、

(すべての点を使った時の最小全域木のコスト)+  各点ごとの、(C×(その位置に置く点の数)+(P^(その位置に置く点の数))×(消滅したときの最小全域木のコストの増量))の和  

とした(各点ごとに独立に考えても真の期待値とそんなにずれないという仮定を置いた)。

ローカルでの評価は、モンテカルロ法によってE(1/rawscore^2)を求めた。

感想、反省

ローカルの評価がずっとバグっていて期間のほとんどを無駄にした。それ以外にもいろいろバグが多かった。そもそも順位表があまり信用できないこともあってスコアが落ちても致命的なバグがあることに気づけなかった。最終結果はともかく全期間通じて動きが過去最悪だった。結局最初に書いたものを少し改善したものを最終提出とした。

 

やはりコードはきれいに書くべきだ。

 

 

TCO18 MM Lightning Round Map Recoloring 参加記録

問題文:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17149&pm=14893

順位表:

https://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=17149

終結果3位でした。

問題概要

2次元グリッドがNR個の領域に分けられている。領域には飛び地もあり得る。また、各マスには色が塗られている。同じ領域に属するマスが同じ色で塗られ、隣り合う領域に異なる色が塗られるように色を塗り替えるとき、(使った色の数)×(色を塗り替えたマスの数)を最小化せよ。

考えたこと

色を最初に固定した。validな解を見つけるため同色隣接領域のペアの数を目的関数とする焼きなましを書いた。ほとんどのケースで6色解が見つかったが、7色使った方がいいケースもあった。解が得られたら、ランダムに一部の色の割り当てを変え、再度解を見つけるための焼きなましをした。得られた解は塗り替えマス数で評価し、もし解が悪くなるなら、前に得られた解に戻した。この部分にも焼きなましの遷移式を用いた。

反省

6色か7色かの判断を適当にやりすぎた。ちゃんと探索してやるべきだった。forumの統計によると、1位、2位に比べて6色でやりすぎらしい。

色を変えるたびに隣接する同色の領域の色を消し、色のついてない領域の数で焼きなます様な方法もあった。その方がよさそうに思える。

validな解を探す焼きなましの遷移において、塗り替えコストの情報を使っていないの点が良くなかった。

invalidな状態を許し、同色隣接領域を禁止する条件をペナルティで表現する方法もあった。コンテスト中考えたがとてもうまく気がしなかったので試してもいなかった。

 

Marathon Match 99 BrokenSlotMachines 参加記録

問題文:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17092&pm=14853

順位表:

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

 

問題概要

numMachines台のスロットマシーンがある。一つのスロットは3つの回転胴からなり、それぞれに’A’から’G’で表される図柄が一周するようにいくつか描かれている。スロットを回すと、3つのリールは回転し、それぞれ独立ランダムな位置で停止する。このとき、正面に見える3つの図柄が一致すれば、図柄に応じた数のコインを獲得できる。また、正面の図柄以外にも、リールごとに正面の前後1つずつの図柄が見える状態になる。スロットをプレイするときは、以下の2種類の方法を選べる。

quickPlay: 1枚のコインと1単位時間を消費。何の図柄が見えているかを知ることができず、リターンのみが知らされる。

notePlay: 1枚のコインとnoteTime時間を消費。何の図柄が見えているか知ることができる。

最初にcoins枚のコインとmaxTime時間が与えられるので。うまい順番でプレイして、最終的なコインの枚数を最大化しよう。

 やったこと

概要

最初にnotePlayでスロットの中身を見て期待リターンを予測し、一番良いと思ったものを(期待リターン1以上ならば)時間いっぱいquickPlayする。

期待リターンの予測

リールごとの連続する3文字が1回のnotePlayで得られる情報である。

まず、各リールについて独立に考えることにする。リールがある特定の文字列である確率の比は、事前確率×尤度で計算できる。すべての組み合わせでこの確率を計算すれば、各文字が含まれている割合の期待値が計算でき、スロットとしての期待リターンを求めることができる。実際には、すべての文字列について計算することはできないが、ほとんどの場合で尤度が0もしくは相対的に小さな値になることに注意し、尤度の大きいものだけをサンプリングする。

得られた3文字のうち、登場しないものが存在すれば、尤度は0である。また、試行回数が十分大きいとき、長い文字列ほど尤度は小さくなる。

そこで、得られた3文字集合を連結し、できるだけ短い文字列を作る。作り方は貪欲+スワップベースの探索とした。サンプリングしたいだけなのである程度雑にやっていいい気がする。

各リールごとに独立に考えていたが、1つのスロットのすべてのリールは長さが同じことは利用できる。他のリールより短い文字列が得られた場合、実際より短すぎるのかもしれないので、適当に文字列をのばしたりしたものもサンプリングする。

どのような順番でプレイするか

多腕バンディット問題におけるUCBの式を参考に、期待リターンが高いほど、試行回数が少ないほど選ばれやすいように評価関数を書いた。

台iの評価 = (台iの予測期待リターン) + (定数)×sqrt(log(総試行回数)/(台iの試行回数))

また、quickPlayに切り替えるタイミングは、上式の第二項がある値を下回る時とした。

性能評価

実行結果のよさは、期待リターン最大の台を選び続けたときの最終的なコインの期待値との相対スコアによって測った。3000ケースを使ってプログラムとしての性能を測った。これをもとにパラメータの調整を行った。これでも結果のばらつきは大きく、調整が大変だった。

やりたかったこと

評価関数に、リールの長さが長いほど予測の不確実さが大きいなど要素を取り入れたかった。

実行時間があまり大きくならないようにしていたので、サンプリングの方法が雑になったのを何とかしたかった。実行時間がかかるとパラメータ調整が大変になるので、このトレードオフが難しかった。

 

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