てきとーな日記

2010-10-21

[]TopCoder Open 2010 02:05

マラソンで奇跡が起きて優勝しちゃった!

f:id:wata_orz:20101021234624j:image

Marathon Final

今年から24hになったので大変だった・・・

問題概要

崩壊する洞窟からコインを回収するゲームのAIを作成せよ

通路は単位時間で1歩移動でき,壁を壊すのにはT時間かかる

通路上にはところどころにコインが落ちていてその上に移動すると回収できる

崩壊は毎時間一定の確率で起こり,崩壊が起こると周囲のDマスが一気に壁に変わる

コインが埋もれると消滅してしまう

運悪く,崩壊に巻き込まれた場合はゲームオーバー(0点)

最初はマップの左端にいて,左端か右端にある出口に到達すると脱出成功となり,回収したコインの個数に比例した点数が入る

マップの難易度により重み付けがされ,各マップに対するスコアの和で順位が決まる

自分の解法

基本的にはダイクストラして一番近いコインを見つけ,てきとーなタイミングで帰還するだけ

マップがそこそこ広いが,目的地に到着したときと,目的地までのパス上で崩壊が起こったときだけ計算すれば十分な上,一番近いコインは結構すぐ見つかるので,なんとかなる

あまり遠くに行ってしまうと帰れなくなるので,コインを取って帰還する間に埋もれて死んじゃう確率をてきとーに見積もって,取りに行ったほうがよさそうな位置にあるコインのうち,一番近いのを狙うようにした

どれも取りに行かない方がいいと判定されたら帰還する

帰還するのにかかる時間の計算は,一番近いコイン見つけるのより時間がかかるので,1000ターンに一回だけ計算しなおすことにした

ビジュアライザ眺めてたら,たったひとつ取り残したコインを回収しに行って,そのせいで脱出が遅れて死んでしまうことが時々あったので,コインの周りに他のコインがどのくらいあるかも考慮した(コインがいっぱいあるのでマンハッタン距離で代用したが,意外とBFSでも速かったらしい)

結果

システムテスト前は2位だったけど,中には1ケースで0.5くらい取れるのとかがあるため,そういうのでたまたま運悪く死んでたりする可能性があるからあんまりあてにならないなーと思っていたが,意外とシステムテストで他の人達が点数伸びなくて,なんと1位になってしまった!

Algorithm Semi Final

マラソン終了後3時間くらい睡眠をとってから挑んだ

250

やるだけな感じの問題

なんかバグるーと思ったら,スワップを

int[] tmp = crt; crt = next; next = crt;

とか書いてたorz (最後がcrt→tmpが正しい)

500

品物集合を二つに分けて,平均価格の和を最小化する問題

寝不足+オンサイト補正(オンサイトだし激ムズに違いない)により解けなかったorz

冷静に考えたら簡単だったし…もうだめぽorz

1000

サイズ制約がどう見ても二つに分けてくださいと言っていたので二つに分けてRangeTreeだー!と思って組んでたがどっかバグってサンプル通らずorz

てか冷静に考えてBITでいいし…なにやってんの俺orz

Challenge

ACRushの250開いたらなんか7重ループが見え,それぞれ最大50回る感じだったのでエェ…と思って撃墜しそうになったが,冷静になって考えたら全体で50C7で間に合ってることに気づいた

他のは怪しいのすらなかった

System Test

8位orz (7位までならWildCard進出)

オンサイトはあまり得意じゃないがさすがにこれはひどいorz

感想

マラソンは夕飯食べたくらい(10h経過くらい)で体力の限界を感じ,そこからは定期的に横になって休んでた

てか,普段のマラソンもコーディングとかあまりせずに,ベッドで転がって方針考えてるのでこういうスタイルで最初からやったほうがいい気がした

アルゴリズム敗退して自分の出るのが全部終わった後は,カジノに入れる年齢になった+超アクティブな社員(大学のクラスメイト)を連れていったため例年よりいっぱい観光して,すごいハードスケジュールだったけどその分面白かった

ラスベガス4泊のはずが2回しか寝てないし…

社員が英語ペラペラでカッコ良かったので自分もいい加減英語何とかしたいなぁと思ったがなんともならないorz

あと,来年はダブル優勝目指す!(無理ゲー)

2010-08-05

[]TCO10 Marathon Round 3 18:24

Subgraph Isomorphismする問題

暫定8位だけど、おそらくシステムテストで順位が超入れ替わると思われるので安心出来ない

通過できてるといいなぁ

戦略上重要なこと

スコアが絶対評価なので、点が稼げるところで一気に稼がないといけない

難しいケースは頑張っても20〜40点とかそれくらいの点数しかとれないのに対し、簡単なケースは300点以上取れる

forum情報だと1ケースで2600点とった人までいるとか…

このことに終盤で気づいたので、そっからは点数低いのをあげようとするのをやめて、点数高いやつをさらに高くするために頑張った

基本的な方針

基本的には全探索するだけ

まず最初に、H(小さい方のグラフ)の頂点の順番を固定し、その順に探索を行う

固定せずに、候補数の少ない点からやったほうがよさそうな気がするが、候補数の計算に時間がかかる、ちょっと先の方に難しい場所があってもそっち方法に進むとは限らない、といった問題があってスコアが悪かったので最終的には固定順で行くことにした

Hの順番を決めたら、次はHの1点目に対応するG(大きい方のグラフ)の点を決めて(全頂点回す)、探索を行う

全探索だととても時間がかかってしまうので、まず最初に嘘探索を行った

ある頂点のマッチングに失敗したときに、普通の全探索だとひとつ前の頂点まで戻るところを、マッチングに失敗した原因となる頂点まで一気に全部戻る

あとで気づいたのだが、これをもうちょっと改良すると嘘でなくなるので全探索の改良もできた(終盤で一気に伸びたのはこれの影響が大きい)

また、うまく行くときはたいていすぐに解が見つかって、うまく行かないときはいつまでたっても終了しない感じだったので、いきなり全探索をするのではなくて探索木の分岐数を最初1に制限し(つまり、バックトラックしない)、それで見つからなければ2にし、それでもだめなら嘘探索→全探索を行った

固定順の計算

固定順の計算法は、まず最初に1点を決めて、すでに決めた頂点集合Uに次のような方法で頂点を追加していくことにより行った

  • Uの2点以上と接続している頂点があれば、その中でUとの接続次数がもっとも大きい物を加える
  • そのような頂点がなければ、Uから出発してUに戻ってくる最小無向閉路を探し、その閉路上の点を順番に追加する
  • そのような閉路がなければ、Uから出発して、どこにも進めなくなる最小のパスをさがし、そのパス上の点を順番に追加する

最初の一点の計算は、全ての点に対して、そこを1点目とした場合にその後5回閉路を辿るのに何頂点必要かを計算し、もっとも小さいのを採用した

こんな感じで序盤に難しい場所(基本的に辺の数が多いほど難しい)を探索すれば、できるだけ早い段階で解がないと判定できて実行時間が短くなるはず

探索の方法

f(v)=v2をv∈V(H)に対応する点がv2∈V(G)であることを意味するとする

探索はf(v)の値をv=0から順に決めていくことにより行う

最初の点は|V(G)|個の可能性があるので全通り回すことによって決めるとして、1番から先の点vに対しては次のように行う

  • vに隣接する点u(<v)を探してくる
  • f(u)に隣接する点v2を探してくる
  • f(v)=v2としたときに、v2の隣接関係が大丈夫かチェックする
  • 大丈夫ならf(v)=v2としてv+1のマッチングを行う
  • v+1のマッチングに失敗したらv2の他の候補を調べる

よく考えると、v+1のマッチングに失敗した原因がf(v)=v2とは無関係であった場合、v2を他の点に変えてもやはり失敗することが確定しているのでさらに前の頂点まで一気にもどることができる

そこで、マッチングに失敗した原因となる頂点のリストretを用意し、次のように改良した

  • vのマッチングにおける失敗の原因リストret_vを別に用意する
  • vに隣接する点u(<v)を探してきて、ret_vにuを追加(f(u)が変化すれば、f(v)の候補点が変化するので可能性が生じる)
  • f(u)に隣接する点v2を探してきて、f(v)=v2としたとき、v2の隣接関係が大丈夫かチェック。駄目だった場合にはその原因のうちで最も番号の小さいものをret_vに追加する(一番小さいの以外が変化しても、結局一番小さいやつのせいでf(v)=v2のマッチングは失敗する)
  • 大丈夫ならf(v)=v2としてv+1のマッチングを行う(この時点でretとret_vは別物のまま)
  • v+1のマッチングに失敗したとき、retにvが含まれているかを調べ、含まれていなければ他の候補を調べる必要はなく、そのままリターン(retもそのまま)
  • 含まれている場合は、v2を変化させればうまく行くかもしれないので他の候補を調べる
  • 全ての候補で駄目だった場合は、ret_vの要素を全部retに加えてリターン

この改良によりローカルでは1000点以上上がった(TC鯖上では500点くらいしか上がらなかった)

高速化

簡単なケースでは、ほとんど詰まることなく単に時間との勝負だったので、高速化が必要だった

Javaでも高速化を結構がんばっていたが、やはりC++にしたほうが良いのは明らか

でも、C++に移行するとアルゴリズム的な改良が出来ない自信があったので、終盤ギリギリまでJavaでやってからC++に移行してひたすら高速化祭りをした

結局C++移行によりローカルでは800点くらい上がった(TC鯖上では400点くらい)

反省点

ローカルテスターとビジュアライザの仕様上、インタラクティブにするのがめんどかったので、どうせ300点くらいまでしか取れないだろうと思って入力は300点分あらかじめファイルに吐いておき、リダイレクトで起動するということを行っていたが、終盤になって300点なんて軽ーく超えるという状況になってしまった

実はこいつらの中には1000点近く取れてるのがいたみたいで、そうなるとおそらく探索だけでなく固定順の計算とかもボトルネックになっていると思われ、そこら辺もちゃんと最適化すべきだったorz

あと、ほぼ全部解けるのなら、Gに含まれるクリークの位置をあらかじめ調べておくっていうのも有効だったかもしれない

Gにクリークが少ししかない(多くのケースで3クリークは大量に含まれているが、簡単なケースだと4クリークが一桁個ということがある)場合に一気に候補が絞れるのだが、Gに少ししかないということはHに含まれている可能性も少ししかなくて役に立たないだろうと思っていた

しかし、簡単な問題ではかなり大きいグラフまで解けることを考えると、Hにも結構含まれていそうだった

おまけ

デバッグなどの目的でグラフビジュアライザを作成した

大量の頂点を平面に描画すると辺が重なってワケが分からなくなるので、三次元で配置して、くるくる回せるようにした

頂点数が多くなっても全体の構造も細かい部分の接続関係もちゃんとわかっていい感じ

f:id:wata_orz:20100805160446p:image

せっかくなので公開

http://ow.ly/2ll3X

ぱすわーどはてきと

使い方

ダブルクリックで起動

始点 終点 (辺のラベル)

を一行に1辺ずつ入力

まともな配置になるまでShowボタンを連打

ドラッグで回転

頂点を右クリックでその点に接続する辺のみを表示

2010-05-04

[]Marathon Match 59 00:59

TCOのシードを得るために一年ぶりに参戦

結果は11位orz

まぁ、久しぶり過ぎた上に時間がなさすぎたのでしょうがない…

方針はまず、何段にするかと、それぞれの段の高さを決めるために、次のように制約をきつくした問題を考え、それを解くことにした。

  • i段目に入っている本はi+1段目に入っているどの本よりも高さが低い

こういう制約を付けると次のような二段階のDPにより最適解を求めることができる。

  • まず、本を高さでソートする
  • dp1[i][j] := [i,j]から幅Wで選ぶときの最大価値
  • dp1[i][j]の計算はiを固定しておいて、ナップサックするだけ
  • サイズが大きいと計算量がやばいので、ナップサックDPは諦めて貪欲法を使用
  • dp2[h][i] := i番目までで高さがhとなるときの最大スコア
  • dp2[h][i]=max{dp2[h-book[j].height-10]+dp1[j][i]}みたいな感じ
  • こっちも計算量がやばいので、嘘DPを使用

何段にするかと、高さが決まったら、次は高さの低い段から貪欲的にナップサックDPを行って本を入れる

これだけだと、空きスペースができてもったいなかったので、本を別の段に移動させることにより、新たに別の本が入れれるようになるっていうのを探して頑張って詰め込む

時間が余るので、高さをランダムにちょっとだけ変更して繰り返しー

2010-03-17

[]SRM 464 23:27

hos先生のセット

250

全通り調べるだけ

n=1の場合を忘れて再提出orz

しかも、再提出ミスって再々提出orzorz

147.68

550

見た瞬間、二分探索+2SAT

492.89

1000

現在位置*安全だと分かっている色の集合*危険だと分かっている色で状態数が50^2*2^7*8

これをDPしていけばいいが、そのままだとDAGでないので、安全だと分かっている色の集合が変化しない部分についてUnionFindとかでマージすればよい

時間内に組み終わらずorz

Challenge

250でn=1の場合を忘れている人いっぱいいるだろーと思ったのに全然いなかった

1成功1ミス

+25.00


合計665.57の9位

28482902

2010-03-03

[]SRM 463 17:48

またしてもりんごさんのセット…

250

ソートして、Π(a_i-i)計算するだけ

すぐに気づけなくて時間かかったorz

239.85

500

よくわかんなかったのでとりあえず小さいの二つ取り出して足すのと掛けるので大きい方にして、一つになるまで繰り返すーをやってみたらサンプルが通らなかったorz

ちょっと考えたら、1.5〜3.0のやつらを二つずつのペアにして足して、あとは全部掛けるでいいことが分かったが、どういうペアにすればいいのか分からない…

小さいから順にペアにするとサンプルが通らないので小さいのと大きいのでペアかなーとか思って組んでみたらサンプルは通ったけどなんか怪しい…

全探索も組んでランダムであってるか調べたら落ちたorz

ここらで諦めて1000開いてわかんなくて戻ってきて、どこまで足し算するかの部分を全部試せばいいんじゃねということにようやく気づき、やってみたら小さいサイズでは正しい解が出てそうだったので提出

231.39

1000

さっぱり分からなかったorz

Challenge

500が撃墜祭りになりそうだったので、パッと見で怪しかったら先越されないように即撃墜

5回成功3回ミス

+175.00

ルーム内で11/16が落ちてたので、全員に対してブラインド撃墜してれば50*11-25*4で450点も稼げた計算に…

今度からはPetrが再提出してたらブラインド撃墜してみよう


合計646.24の32位

28412848