2015-08-10

■ [ICFPC]ICFP Programming Contest 2015 01:58 はてなブックマーク - ICFP Programming Contest 2015 - TopCoderの学習のお時間


例年のように会社の人と合宿して参加した。5人チーム。

やったこと


テトリスAIだったので、まあビームサーチかなということでまずは下に落とすだけのソルバを書いた。

2日目の午前中くらいには回転なし版がそれなりに動いて、あとはライトニングの提出に向けて回転を足して調整したり高速化したりで2日目終了。

3日目には他の人たちもソルバを拡張し始めていて、あまり他の人がコードをいじるようなつもりで書いていなかったのでアッアッ…という感じだったけど、そこで手を出してしまうと同じコードを同時に複数人で変更することになってカオスになるのでソルバの拡張は任せることにした。

公式の順位表が重くて見づらいことに嫌気がさして、ダウンロードしてきて適当にフォーマットして表示するようにした。

公式順位表のデータ部分はJavaScriptで生成されているようだったので、 Seleniumでブラウザ起動して取得→重すぎ casperjsでサイレント実行して取得→なぜかcronで実行するとうまく取れない とはまっていたけど、実は https://davar.icfpcontest.org/rankings.js をダウンロードしたら順位表データが全部入っていた…。時間をだいぶ無駄にしてしまった。

あとはビジュアライザのスクリーンショットを順位表と合わせて表示するようにした。どのような盤面はどのくらいのスコアが出ていて、ライン消すのかPowerをたくさん狙うのかどちらがよさそうかなどを判断する情報になってくれたかもしれない。

それと各チームのベスト記録を元にした潜伏なし版ランキングも作っていたので、Unagiチームの強さはだいぶ早いうちから知ることができていた。

最終日はソルバのコードもだいぶ読めない感じになってきていて、Power探しシステムが完成していたこともあり、Powerの文字列候補のネタ出しをしていた。

Wikipediaからクトゥルフ関連の単語を大量に取ってきて投げたけど、その後で 公式Twitterに「Wikipediaからコピペしてんじゃねーよ」みたいなことが書かれているのに気付いた…。

最長のPowerの長さが51文字ということで、ストーリーの文書からちょうど単語区切りが51文字になっている部分を全列挙して眺めてみて、「a new representation for ancient protection schemes （, called davar）」というとてもそれっぽい箇所があるのを発見するものの、「ep」と連なっているところが→,←の順での移動だから活用するのはほぼ無理だね、となって試さなかった（結局全然違っていた）。

時間の最後のあたりでソルバの重複盤面除去が甘いことに気付いて（自分が初期に入れたコード）直したりほかのデバッグの手伝いをしたりしていた。

例年と同じく最後はちょっと慌てたけれど提出完了。

反省


特によかったこと

  • 最初に問題内容の理解を全員で合わせる機会を持った
  • かなり早いうちにビジュアライザができていたので作ったコードの動きが見えてやる気が上がった
  • Power探索がシステム化されて候補を探すのが効率的だった
  • ホワイトボードを有効活用できた
    • 合宿先に4枚もあった
  • (個人的に)食事以外ではほとんど間食せず、それなりに睡眠も取って健康的だった。コードが書けたおかげで体調良くなった

そのほか

  • 早いうちにやっておくべき事に着手するのが遅めだった
    • Power探しは公式ジャッジサーバーに提出して結果が出るまで待たないといけないのでどうしても時間がかかる。2日目の夜はまだPowerの候補を出していなくて公式ジャッジのリソースが遊んでいたのがもったいなかった
    • 順位表データはとりあえず保存しておくだけでも先にやっておきたかった。各チーム、ライトニング終了時点ではその時点でのベストスコアを出しているはずだけど、だいたいその後Power探しになって順位表がぐちゃぐちゃになるので、実際各ケースで最大どれだけのスコアが取れるのかがわかりづらくなってしまった
  • 役割分担をそこまで厳格には決めなかった
    • 本当はAI書く人は最初からずっとそれだけやるのが良いんだろうけど、まあみんなコード書きたいだろうし
    • あんまりぎちぎちにしてしまうのはコンテスト参加の楽しみという点では辛いので
  • AIのパラメタ振り
    • 盤面の特徴がさまざまなので1つのAIプログラムで対処するのが難しくて、ソルバのいくつかのバリアントで実行してベストの物を使えるように…
    • という話はしていたが結局あんまりバリアント作れなかった（実際それで良くなるのかどうかはわからない）。
  • テスタは別途作っておくべきだった
    • 手元での評価用に、正確に実行することだけを考えて作成したシミュレータを用意しておくべきだったように思う
    • サーバーに回答（またはコード）を提出して結果を得る方式だと扱いづらいので。公式がバグってることもよくあるし…
  • 開始前に「プログラムに名前をつけよう」と言っていたのを達成できなかった。特に好きなキャラクターとかないのが難しい

感想


毎回ICFPCは、いくらロジックだけ書けてもそれを人間とのインターフェース含めて有効に活用できる手段も持っていないと威力が半減するのだなあ、というのを思い知らされてたいへん学習モチベーションが上がる機会で。

そういったことを思う存分できた3日間が終わってしまったのが悲しくて、普段の中ではそこまで自由に色々できるわけではないけど、創意工夫を差し込める箇所を探して、できることを増やしていけるよう頑張ろう、

2015-03-17

■ [CodeChef]March Challenge 2015 20:34 はてなブックマーク - March Challenge 2015 - TopCoderの学習のお時間


http://www.codechef.com/MARCH15

使える時間が 週末×1 だけでは難問まで手が出せなくてつらい…

Chef and Notebooks(CNOTE)


やる

http://www.codechef.com/viewsolution/6418160

Sign Wave(SIGNWAVE)


実験すると規則性がわかる

2問目からやたら難易度上がって面食らった

http://www.codechef.com/viewsolution/6419514

Devu and his Class(DEVCLASS)


type=0はハミング距離数えるだけ

type=1は前から順に近いところへ移動させれば良い

type=2は1つずつ移動させることを考えたらtype=1と同じ

http://www.codechef.com/viewsolution/6421521

Count Substrings(STRSUB)


end[i] = i文字目から end[i] 文字目までに含まれる0の数と1の数がともにK以下であるような最大の整数

とする。これは尺取りっぽくやると O(N+K) で全体が求められる。また、endについて累積和を計算しておく。

end[mid] <= R かつ end[mid+1] > R となるmidを二分探索で求める。

[L,mid]の範囲の位置を左端とする文字列に関して数えるべきものの個数は、end[L]からend[mid]までの和からわかり、これは累積和を使って O(1)

[mid+1,R]に関しては、 1 + 2 + ... + R-mid なので O(1)

http://www.codechef.com/viewsolution/6418577

Sereja and Random Array(SEAPROAR)


線形合同法かどうかを判定する。

線形合同法の下位16bit目は2^17の周期でループし、かつXとしての周期は2^32なので、

下位16bit目の出現列としてあり得るものは全て、適当なseedから始めて得られた長さ2^17のビット列に含まれる

入力の先頭500文字がその中に出現するかを調べると良い（ローリングハッシュを使った）

http://www.codechef.com/viewsolution/6433305

Matrix(MTRWY)


逆からUnion-Find

http://www.codechef.com/viewsolution/6420460

Chef and Problems(QCHEF)


平方分割

http://www.codechef.com/viewsolution/6479333

Counting on a Tree(TREECNT2)


思いつかず

部分点だけならてきとーにやればできるんではと思ったが面倒になってしまった

Z≤10^6 なので各エッジは素因数を高々7個しか持たない、といったあたりがキーなのかな

Random Number Generator(RNG)


きたまさ法やって O(k^2 logN) で部分点

FFTとかで O(k logk logN) にできれば100点なんでしょう

http://www.codechef.com/viewsolution/6517890

Embedding(EMBED:タイブレーク)


時間なかったので着手せず

とりあえずハード制約だけ満たすものを作って、

Nが小さいものから焼きなましてく感じかな

評価基準は各ケースの絶対スコアの単純合計なので、点数を取れるケースでたくさん取るのがきっと重要

結果


  • 710pts/1000pts
  • 97位/5847人

2015-02-19

■ [CodeChef]Februray Challenge 2015 18:06 はてなブックマーク - Februray Challenge 2015 - TopCoderの学習のお時間


http://www.codechef.com/FEB15

これがchef longのガチ問か

Chef and Chain(CHEFCH)


010101... とxorをとってbitcount

http://www.codechef.com/viewsolution/6128122

Chef and Equality(CHEFEQ)


最頻値の個数を数える

http://www.codechef.com/viewsolution/6128251

Let us play with rank list(RANKLIST)


与えられた制約の下でのranklist中の値が取り得る最大値を二分探索

http://www.codechef.com/viewsolution/6128614

Chef and Strange Formula(STFM)


Σ_{i<=x}i･i! と xΣ_{i<=x}i に分けて考える。

後者は O(1) だし、

前者は、 i>=M の項は mod M で0だから考えなくて良いので前計算できる

http://www.codechef.com/viewsolution/6129545

Chef and Strings(STRQ)


memo[i][j][k] := i文字目までで文字jの後に文字kが出てくる組み合わせの個数

count[i][j] := i文字目までで文字jが出てくる個数

こいつらを最初にDPで求めておくと各クエリ O(1) で組み合わせ数を計算できる

http://www.codechef.com/viewsolution/6130140

Time to Study Graphs with Chef(CHEFGRPH)


追加のedgeが貼られる頂点があるlayerだけ特別に計算する

http://www.codechef.com/viewsolution/6132411

Xor Matrix(XRMTRX)


実験するとわかる

たくさん場合分けしてしまったけれどもっと綺麗な方法はありそう

http://www.codechef.com/viewsolution/6135507

Devu and Locks(DEVLOCK)


ふつうにDPすると O(P^2 M^3) になる。少し定数倍高速化して60点

FFTかも、というのは感じていたが、その方向だとどっちにしろ難しそう（FFT書いたことない）なので

埋め込みできないかなーとかそんなことを考えていた

http://www.codechef.com/viewsolution/6158495

Payton numbers(CUSTPRIM)


小さいケースで実験してみたり、

簡単に表せる形にならないか各要素を足し引きしてみたりしたが

まったくわからなかった

Jigsaw Puzzle Solving(CHPUZZLE:タイブレーク)


密度が高い順にピースを並べて、最初に見つかった置けるところに置いていくだけ

もっと取り組む時間があれば小さいケースでは評価関数定めてビームサーチしてたのだが

問題としてはかなりバランスの良いものだったと思う

66.2pts

http://www.codechef.com/viewsolution/6283013

結果


  • 826.155pts/1000pts
  • 26位/7008人

2015-01-12

■ [CodeChef]January Challenge 2015 21:24 はてなブックマーク - January Challenge 2015 - TopCoderの学習のお時間


http://www.codechef.com/JAN15

2年ぶりくらいに参加した。

このコンテスト形式、マイペースに取り組めて良いので今後も出ようと思う。

Chef and Stones(CHEFSTON)


やる

http://www.codechef.com/viewsolution/5713322

Gcd Queries(GCDQ)


配列を前から見ていった累積GCDと後ろから見ていった累積GCDを覚えておく

http://www.codechef.com/viewsolution/5713655

Sereja and Votes(SEAVOTE)


取り得る和の上限と下限を求める

http://www.codechef.com/viewsolution/5713840

One Dimensional Kingdoms(ONEKING)


よくあるGreedy

最初、区間の開始・終了をオブジェクトとしてソートしていたらTLEした

座標の範囲が狭かったので座標をキーにしてソート無しでやった

http://www.codechef.com/viewsolution/5714255

Chef and A Large Permutation(CLPERM)


実装も知識も無く考察のみで解ける愉快な問題

存在するカードを昇順に並べた配列をBとする。

B_1〜B_n のカードを使って S=ΣB_i(1<=i<=n) までの全ての整数を表せるとすると、B_n+1 を考えると次のようになる

  • B_n+1 <= S+1 の場合
    • B_1〜B_n+1 のカードを使って ΣB_i(1<=i<=n+1) までの全ての整数を表せる
  • B_n+1 > S+1 の場合
    • S+1が表せない

これをそのままやるとO(N-K)だが、カードの数が連続している範囲をまとめて処理するとO(K)になる

http://www.codechef.com/viewsolution/5717846

Queries on the String(QSET)


count[x][y] := (文字列先頭からx文字目まで見たときの数値 % 3 == y) ? 1 : 0

上記の値をSegmentTreeで管理する

この問題が今回の中で一番難しかった気がする

http://www.codechef.com/viewsolution/5716782

Xor Queries(XRQRS)


永続SegmentTree

xor最大化やk-th smallestのクエリに対しては、上から1bitずつ決めていく

http://www.codechef.com/viewsolution/5867272

Sereja and LCM(SEALCM)


D（なぜかコード中ではUという名前にしてしまった）を素因数の冪に分解して、包除原理で補集合の要素数を求める

http://www.codechef.com/viewsolution/5872152

Ranka(RANKA)


白を下から埋めていく→黒を1つ置いて白を全滅させる

を繰り返す

黒が最後まで行ったらいったん黒を全滅させ、盤面を90度回転させた形で同様のことをやる

http://www.codechef.com/viewsolution/5873615

Sereja and Number Division 2(SEAND2:タイブレーク)


焼きなましただけ

ΣB の値が大きいケースに長く時間をかけるようにした

http://www.codechef.com/viewsolution/5729963

CodeChefではJavaはC++の2倍時間を使えるけど、有利なのかどうかはよくわからない

結果

  • 10問中10問AC
  • 14位/7943人

2014-12-01

■ [部活][MM] MarathonMatchトレーニングのための過去問レビュー 01:01 はてなブックマーク - MarathonMatchトレーニングのための過去問レビュー - TopCoderの学習のお時間


これは Competitive Programming Advent Calendar 2014 1日目の記事です。

MarathonMatchで成績を上げていくには、他のスポーツと同じく実践が不可欠だと思います。

しかし、最近は通常の（=TCO予選みたいな組み合わせ最適化を問う）MarathonMatchの開催回数が少ないのでなかなかその機会が得られません。

信じられないかもしれませんが、2008年ごろは月1回以上のペースでMarathonMatchが開催されていたんです…。

ならば過去の問題ストックを使って自主練するしかない！

ということで、過去に自分が参加したMarathonMatchについて、問題をジャンルわけしてコメントを付け、オススメ度を☆で表しています。

ジャンルわけは便宜上という側面が大きく、この方針ではないとダメ！　というわけではないです。

あと、ネタバレありなので要注意。

リンク先はPracticeの問題文です。

Practiceが存在しないものがいくつかあって、それらにはリンクを張っていません。

なお、Practiceにないものも含めて過去のMarathonMatchの一覧を見るには、Match Winners のページがよさそうです。

焼きなまし


ざっくりいえば焼きなましをするんだけど、もちろん焼きなましただけではだめで、その適用形態は多彩です。

  • TCO14 Round3 CollageMaker [☆☆☆]
    • そもそも、焼きなまし（というか、逐次的改善）可能な形にできたかどうかが上位との分かれ目といった感じでした
    • 解の探索以外でちょっと面倒な要素が多いので、練習するなら他の問題の方が良いかなぁ
  • TCO13 Round3 CirclesSeparation [☆☆☆]
    • 良い近傍の取り方がとても難しい
    • 僕は本番でまともな方法を実装できずに撃沈しました
  • Marathon Match 78 FixTheFence [☆☆☆☆☆]
    • 良い近傍の取り方が難しい
    • 問題としてはシンプルなので練習によさそう
    • ところで本番1位の人の解法は焼きなましではなく他の人たちと全然違う方針でした。かっこいい
  • TCO10 Round2 CellularAutomaton [☆☆]
    • 完全に高速化ゲー。高速化の訓練としては良いかもしれませんが…
  • TCO10 Round1 Planarity [☆☆]
    • これもかなり高速化ゲーの印象（12時間しかやってないけど）
  • Marathon Match 56 EnclosingCircles [☆☆☆☆]
    • よくMarathonMatchの問題例として取り上げられる、理解しやすい問題
    • 本番の結果は意外とばらけていて、焼きなましの職人芸スキルで差がついた、という印象
  • Marathon Match 54 TilesPuzzle [☆☆☆]
    • 本番で自分が焼きなましでやったのでここに入れましたが、forumを見る限りは焼きなましてる人は少数派っぽい
    • いろいろなヒューリスティック探索ができそう

ビームサーチ


最近ビームサーチばかりやってる気がするけど、挙げてみたら思っていたより少なかった。

  • TCO14 Round1 SquareRemover [☆☆☆]
    • 高速化寄り
    • アルゴリズムにやらせると、人力で遊んだ場合より遙かに良い点数を出すのが面白かった（どうでもいい）
  • TCO13 Round2 FragileMirrors [☆☆☆☆]
    • 良い評価関数を作ることがもちろん大切なんだけど、もっと重要な要素がひとつあって、それを見つけられないと勝負にならない感じだった
    • 問題の性質をよく考える訓練になって良い
  • TCO12 Round1 BlackAndWhiteGame [☆☆]
    • 探索が可能な形をつくるのが全く自明ではなくて大変
    • 正のスコアを出すまでちょっと遠いので練習としてやるにはつらいかもしれない

マルチエージェント系


複数のユニットを動かして、協調して何かやらせる問題。

実装が難しくなることが多いです。

  • TCO13 Final GatheringResources [☆☆☆]
    • 実装ゲーに近かったと思う
    • とはいえ12時間しかやっていないのでもっと時間かけたときにどうなるかは未知数かな
  • Marathon Match 55 CoalMining [☆☆☆]
    • あまり印象に残っていない…。オーソドックスな問題だったと思います

パターン決め系


良い解では全体がどのような形になるかを見出すことが最重要になる問題たち。

後はそのパターンの中で細かく探索をしたりする。

他人の解をビジュアライザで見ると面白いことが多い。

  • TCO14 Round2 RectanglesAndHoles [☆☆☆]
    • パターンを想定するまではできても、それを実装するのが難しい問題だったと思います
  • Marathon Match 74 AntiTravelingSalesperson [☆☆☆☆]
    • 格子点にしか置けないという制約がある中でうまいパターンを作るには、適当にやってもダメでよーく考えないといけない
    • これも1位の人は違った方針でやっていてかっこよかった
  • TCO09 Round2 Gearing [☆☆☆☆]
    • 逐次的な改善が可能な形でパターン決めてあげないと良いスコアにはならない
    • 本番に自分が参加したときは、greedy的な方針で決めうちしてしまってイマイチな結果でした
  • Marathon Match 49 MegaParty [☆☆☆☆☆]
    • 問題の性質をよく考えて、全体の形を作る事が最重要。教育的です
    • 本番に自分が参加したときは、何も考えず単純に焼きなましただけだったのでイマイチな結果でした

不完全情報・確率評価系


初めに情報が全部は与えられないタイプの問題。結果の期待値を評価しながら次の一手を選んでいくプログラムになる。

個人的にはこの形式はけっこう好き。

  • TCO12 Final PolygonEstimation [☆☆☆]
    • 本番で方針が大きく2つに分かれて結果も拮抗していたのが面白かった
    • なかなか実装Hardです
  • TCO11 Round1 ImageScanner [☆☆☆]
    • colunさんがガチ確率評価をやって圧勝したことで有名（？）な回
    • 問題テーマとしては、情報科学的な観点でもとても面白いものではある
    • 外部のデータファイルを処理しないといけないので少し取っつきづらいかな？
  • TCO10 Final CollapsingMaze [☆☆]
    • 確率的に即0点になってしまうという大味な問題。どこまで攻めるかの調整が肝
    • Practiceではテストケース数が限られるから運ゲー要素が強くなってしまいそう
  • Marathon Match 65 CuttingFigures [☆☆☆☆☆]
    • ある手を指したときの期待値をしっかり評価することが求められる
    • ルールもシンプルだし、良い練習になりそうな問題です
  • Marathon Match 53 TilesMatching [☆☆☆☆]
    • とにかく良い評価関数を作れるか勝負
    • これもう一回やりたいのだけどなんでPracticeにないんだ…
  • TCO09 Round1 ReliefMap [☆☆☆☆]
    • 取れる選択肢の自由度が非常に高くて、次に何をするかをどうやって決めたら良いか難しい
    • 実装も大変で、Round1（当時ルール）にしておくにはもったいない良問でした

その他・ノンジャンル・総合力


  • TCO11 Round2 QualityPolygons [☆☆☆☆☆]
    • いろいろな方針が考えられて、まさに総合力といった感じ
    • がっつり練習したかったら、ここに挙げた中で一番オススメです
  • TCO10 Round3 SubgraphIsomorphism [☆☆☆☆]
  • TCO09 Round3 BounceOff [☆☆☆☆]
    • まず、ある程度まともに動作する解を作れるかどうかが難しくて、Round3（当時ルール）に進んだ人たちでもかなり苦労していた
    • この問題は特に、SRM的な発想では全く方針決められない気がします。その意味では良い例題
    • ビジュアライザが楽しいです
  • Marathon Match 48 WatermarkSequence [☆☆☆☆]
    • Marathon史上最良問との呼び声もある問題。僕が初めてMarathonに参加した回でもある
    • めちゃめちゃ面白いけどだいぶ難しいので、練習にやってみるなら覚悟して

特殊・非推奨


ちょっと特殊なところがあってあまりお勧めできない問題たち。


やったことないやつら


問題文を読んだだけでコードを書いたことがない回もたくさん残っていました。それらの中で面白そうなのを列挙します。

自分が練習会をするとしたら、この中から選ぶことになります。

（この記事の公開と同時に練習会を始めようかとも思っていましたが、CodeVSやKaggleが出てきたのでまたいずれ）

2014-06-15

■ [TCO][MM] TCO14 Marathon Round2 18:45 はてなブックマーク - TCO14 Marathon Round2 - TopCoderの学習のお時間

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15982&pm=13189

問題


ランダムな大きさの長方形がN個与えられる。長方形の各辺の長さは[1,1000]、Nの範囲は[100,1000]の一様分布。

こいつらを平面内に配置して穴を作る。

(穴の個数)^2 * (穴の面積合計) を最大化せよ。

やったこと


大きな穴を1つ作る+小さな穴をたくさん作る が最適になるのはまあ直感的にわかる。

colunさんに倣ってBigHoleとManyHolesと呼ぶ。

ManyHolesに何個の長方形を回すかは、実験してみたらN*0.54くらいが良さそうだった。

ManyHolesを作るときは、BigHoleで使われている長方形も利用した方がManyHolesに寄与する長方形の数を稼げる（その結果穴の数が増える）ので、BigHoleにくっつけて作る。

ManyHolesの領域はできるだけ表面積を小さくした方が良い（N個の長方形から作れる穴の数の最大値はNが大きいとほぼN個なんだけど、領域の外側に出ている長方形の個数分その限界から遠ざかっていく）ので、ManyHolesの部分は丸い感じになるようにする。

そのため、BigHoleの作り方を工夫して一部を外側に張り出すようにした。それでできた空間に小さい長方形を詰めていく。

小さい穴をたくさん作る方法なんだけど、賢い配置を考えて決めるのは泥沼っぽい気がして探索することにした。

長方形を小さい順に取って、既存の長方形の右側か左側に接するところを試す。他の長方形に接する一番端の箇所を見つけて、隙間ができていたらそれを穴ができたと見なす。

      |               |   |
      |               |   |
      |               +---+
 -+   |                 +---+
  |   +----             |   |
  |+----+      や     -+|   |
  ||    |              |+---+
  ||    |              |
  |+----+              |
  |                    |
 -+                   -+

こんな感じだと良い配置。

時間制限いっぱいまで、使う長方形の順序をちょっと変えながらこれを繰り返す。本当はビームサーチしたほうが良いのだと思うけど、実装時間が足りなくて断念してしまった。

あと、BigHoleの内側にManyHolesを作るのではなく外側に作ったら、面積が2%くらい増えるなーと思ってたけど、どうやっても穴の個数が減ってしまってうまくいかなかった。

画像


seed=1の例。

全体：

f:id:tomerun:20140615183106p:image

上部：

f:id:tomerun:20140615183105p:image

ビジュアライザには次の変更を加えた。

  • 穴になった部分が赤く塗られていたけど気持ち悪かったので消した
  • スクロールやズームを可能にした
  • 縮尺を表示するようにした
  • ビジュアライズ部分をテスタと分離して別プログラムにして、テスタ実行時に表示するのではなくスタンドアローンで起動できるようにした
    • テスタではログに出力しておいて、ビジュアライザにはそれを読み込ませる

結果

  • provisional score : 954551.54（各ケースで1位を100万点とした相対スコアの平均）
  • provisional rank : 9 / 170
  • final score : 954969.99
  • final rank : 10 / 170
  • レーティング : 2188->2250

意味のあるスコアを出すまでの実装が大変なのでやっぱり参加者少なかったですね。

2014-05-04

■ [TCO][MM] TCO14 Marathon Round1 21:23 はてなブックマーク - TCO14 Marathon Round1 - TopCoderの学習のお時間

http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15938&pm=13132

問題


yowaさんのスライドを参照。

http://topcoder.g.hatena.ne.jp/yowa/20140424

やったこと


問題読む→はい、いつものビームサーチのパターンですね

2次元グリッド上でなんかゲームやって、1手ごとならビームサーチ、全体を構成するのなら焼きなまし、というパターン最近多すぎて飽きてきた…

ターン数が10000と多くて、評価関数で色々やろうとするとビーム幅小さくなってどうやってもスコア下がってしまうので、評価関数はごく簡単にしてひたすら高速化を頑張った

探索空間


C=4の場合は1手で消せるところ、C=5,6の場合は1手か2手で消せるところを全探索

始めは高速化のため、前回動かしたところの周辺だけ探す、ということをやっていたけれど意味なかった

ビーム幅は、時間をいっぱいまで使えるよう実行中に残り時間を見ながら動的に変える

評価関数の要素


  • 累計の得点
    • 連鎖を全部シミュレートしてしまうのはあまり意味がなく、得点が0か1か2以上か、だけ判定した
  • 2×2のブロック中に3つ同色がそろった箇所・2つ同色がそろった箇所が、盤面内に何個あるか

データ構造と探索方法


struct Board{
    uint64_t f[20];   // 各セルがどの色か。最高6色、番兵として使う無効分も入れて7色なので1セル3bitで収まる。周囲2マスずつ番兵にするので20*20分確保
    uint64_t v[15];   // 各2×2の領域がどのような状態か。15×15個分確保。
                      // 3つ同色のパターン:4個、2つ同色*2のパターン:3個、2つ同色*1のパターン:6個、同色無しのパターン:1個 で合計14個なので1つ4bit
    uint64_t v2[15];  // 高速化用。基本的にはvと同じだけど、一度探索してみた結果1手や2手では消せないとわかった箇所は、
                      // 0（無効を意味する）で上書きして再度調べないようにする
};

探索するときは、たとえばv2が「3箇所そろっていて右下だけ違う色」を示しているときは、次のような状態になっている。

 AA
 AB

下の図のXの箇所を調べ、そこの色がAだった場合、それをBの箇所に持ってくる動きを候補として採用する。

 AA_
 ABX
 _X_

C=5,6でXの箇所が候補にならなかった場合は、次に、2手で揃えられる箇所として、下の図のYの位置も調べる。

 __Y__
 _AAY_
 YABXY
 _YXY_
 __Y__

v2が「2箇所そろっている」の場合も、同じように2手で揃えられるパターンを全列挙してそこに揃えたい色が入っているかを調べる。

反省


  • 同一盤面の除去をやらなかった
  • 評価関数のパラメタ調整をやらなかった

同一盤面の除去を軽く入れてみたら2%くらい上がったので、もっとこの辺をちゃんとやっていたら通過ラインくらいまで行けていた可能性もある。

詰めが甘いです

結果

  • provisional score : 950346.80（各ケースで1位を100万点とした相対スコアの平均）
  • provisional rank : 10 / 333
  • final score : 952155.96
  • final rank : 10 / 333
  • レーティング : 2334->2371 highest更新