TCO18 MM Lightning 2 KnightsAndPawns 参加記録

問題文:

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17225&compid=66697

順位表:

http://community.topcoder.com/longcontest/?module=ViewStandings&rd=17225

 

大学のテスト・レポートとかぶっていてだいぶつらい

 

問題概要

H*Wのボードにいくつかのポーンが置かれている。ここにいくつかのナイトを置いていく。このとき、すべてのナイトについて、攻撃できる駒の数がちょうど2でなくてはならない。置くコマ数を最大化せよ。

解法

 とにかく時間がないので実装が簡単でパラメータ調整でゴリおせそうなものを目指しました(パラメータ調整は大学のレポートなどと並行してできるので)。

一般的な考察

・ナイトのattack数が2ということは、attackしているナイト同士を結ぶとパスができて、パスは閉路であるかポーンを端点としていると言えます。

・3つ以上のポーンを攻撃するマスはそもそも考慮に入れる必要がありません。

validと準valid

 validな状態とは、非負スコアが得られる状態、すなわちすべてのナイトのattack数が2である状態です。これに対しすべてのナイトのattack数が2以下である状態を準validと呼ぶことにします。

焼きなまし

僕の解法が全体としてやっていることは焼きなましです。以下に示す状態遷移を繰り返して準validな状態を得た後、validな状態に直すところまでを一遷移として、焼きなましをします。

状態遷移

 状態が準validであるとします。基本的な考え方は、「新たにナイトを置いていきたいが、準validな状態を保持したい」です。

 attack数が1であるナイトを一つ選び、その近傍にナイトを一つ置きます。選んだナイトをA、Aの近傍に置いたナイトをB、さらにBの近傍にあってAでないもの(ナイトorポーン)をCとします。AとBを設定すると、

  1. そもそもCが存在しない。
  2. Cとして考えられるものがちょうど1つ存在する。
  3. Cとして考えられるものが2つ以上存在する。

のどれかが成り立ちます。

 1の場合は簡単で、Aのattack数が2、Bのattack数が1、それ以外は影響なしなので準validな状態は保たれています。

 2の場合は、Aのattack数=2、Bのattack数=2、Cのattack数+=1、となります。Cのattack数が1増えるということは、attack数が3になる可能性があります。その場合、Cがナイトであれば準validでなくなってしまいます。そこでCの近傍であってBでないもの2つのうち一つを消します。もし両方ともポーンであるならば、Cを消してしまいます。

  3の場合は、そもそもBの候補として除外しておくことにします。 

 以上の挙動は、以下のように説明できます。

・ナイトが作るパスの端を伸ばしていって、ほかのパスにぶつかったらそのパスを切って切り口につなぐ。ほかのパスの端点とぶつかったら2つのパスをつないで一つのパスになる。

 この操作において、ナイトの数が減ることはありません。

 そもそもAの候補がない場合ですが、適当な空きマスを選んでナイトを置き、上述の2の場合と同様な処理を施すことで、状態を変化させることができます。

準validからvalidを得る

準validな状態からattack数が1以下のものを消していくと、最終的にvalidになります。これは不完全なパスをすべて消すことに対応し、得られたvalidな状態は、消す順番などに依らず準validな状態に対して一意に定まります。

焼きなましの一遷移

焼きなましの一遷移は、「準valid保持の状態遷移を20回程度繰り返したのち、上述した方法でvalid解を得る」です。遷移回数は100万回ほどになりました。

 

細かい工夫

大学レポートと並行しながらやっていた関係で、なんでうまくいくか考察できていない部分が工夫点のほとんどになってしまいました。すべて挙げるときりがないので一部だけ書きます。

・一定期間ベストを更新しないときロールバック処理を行いました。ロールバック直後、ランダムなナイトの消去操作を何回か行いました。また、ロールバック直後の状態遷移の回数をマスの大きさぐらいまで増やしました。

・状態遷移において、低確率でattack数1のナイトを消去するようにしました。

example test

Example scores:
0) 15.0
1) 1335.0
2) 3457.0
3) 1426.0
4) 2001.0
5) 173.0
6) 1389.0
7) 258.0
8) 230.0
9) 1528.0

seed2

f:id:ats5515:20180801005942j:plain

 

TCO18 MM R3 InvestmentAdvice 参加記録

問題文:

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17203&compid=65421

順位表:

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

 

最終日のみの参加になってしまった

 

問題内容

概要

N個のファンドがあり、それぞれ異なるexpertにより運用されている。毎round、各expertは次roundまでにリターン可能であると予測される利益の投資額に対する比を提示する。どれにいくら投資するかを決めて、利益を最大化せよ。

制約、条件

1roundで1つのexpertに投資できる額の上限は400000である。また、投資額の合計が所持金額を超えてはならない。これらの条件を満たせば、投資額は毎roundごと自由に決められる。投資したお金は必ず次のroundには清算される。利益は、各ファンドごとに投資額×真の利益比(小数点以下切り下げ)によって計算される。この値は次のroundにおいて知ることができる。

・最初から持ってるお金=1000000

・ファンド数 N=nextInt(10,50)

・全round数 R=nextInt(10,100)

・各ファンドの真の利益の比=平均0、標準偏差0.1の正規分布に従う。

・expertの提示する値:

確率Aで平均が真の利益、標準偏差Sの正規分布に従う。

確率1-Aで平均0、標準偏差0.1の正規分布に従う。

ここでA,Sはexpertごとに持つパラメータで、

A=nextDouble()

S=nextDouble()*0.2

として決定される。これはroundごとに変化しない。

やったこと

平均a、標準偏差s、の正規分布確率密度関数をf(x,a,s)と書くことにします。

基本方針

まず、毎roundの利益の期待値を最大化するには、各ファンドごとに利益率の期待値を求め、大きいところから順に、期待値が正である間、また所持金が残っている間、上限額(400000)ずつ投資していけばよいです。

もし全く投資しない場合、そのファンドの真の利益率についての情報が得られません。よって、情報を得るために期待値が低いところに投資することも考える必要があります。情報を得たいファンドについては一定の額を投資することとし、それ以外についてはそのroundの利益の期待値を最大化することを考えることにします。

期待値の計算

ベイズの定理とかで確率計算します。以降一つのファンドに注目して考えることにします。

あるroundにおいて、真の利益率がactual、提示された値がreportであったとします。

expertのパラメータの確率分布は、

p(A,S | actual,report) ∝ p(A,S)×p(report | actual,A,S)×p(actual | A,S)

です。p(report | actual,A,S)は、問題の制約において、真の値から提示する値を決定する部分がそのまま使えます。

p(actual | A,S)はそもそもA,Sに依らないので無くて良いです。したがって、

p(A,S | actual,report) ∝ p(A,S)×{A×f(report,actual,S)+(1-A)×f(report,0,0.1)}

投資したファンドについては前roundのactualの情報が分かるので、これを用いて確率計算します。投資しなかったファンドについては、

p(A,S | report) ∝ p(A,S)×p(report | A,S)

=p(A,S)×{A×f(report,0,sqrt(0.01 + S*S))+(1-A)×f(report,0,0.1)}と計算できると思いましたが、やるとスコアが悪くなるのでやってません。なんで

続いて、利益の期待値を計算します。さっきまでのactual,reportは直前roundの情報でしたが、これからは現roundのactual,reportです。actualに関しては予測値ですので、区別するためにXと書きます。

p(X | report) ∝ p(report | X)×p(X)

=∬p(report | X,A,S)×p(X,A,S) dAdS

=p(X)×∬p(report | X,A,S) dAdS

=f(X,0,0.1)×∬{A×f(report,X,S)+(1-A)×f(report,0,0.1)}dAdS

後は期待値ですが、

∫X×p(X | report)dXを計算すればよいです。

これらの計算は解析的にはできそうにありません。A,S,予測actualに関して標本化して計算しました。

情報を得るための投資

投資した回数が一定回数以下のexpertには、必ず40だけ投資するようにしました。この値は大きすぎるとそのroundに得られる利益の期待値が低くなる損が大きくなり、小さすぎると得られる情報の正確さが落ちます。

「一定回数」の決め方ですが、全ファンド数と全round数のみに依るものとして考えました。あらかじめいくつかの{全ファンド数、全round数}に対して「一定回数」として最善の値を求めておき、間の値は補完することでテストケースごとの「一定回数」を求めました。

この辺は改善の余地が大いにあると思うのですが、時間がなくてやってません。

 

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位目指して頑張りたい。