読者です 読者をやめる 読者になる 読者になる

simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

NYC Lightning Round 参戦記録

競技プログラミング

診断人さんのツイートで気づいて参戦しました

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16756&pm=14282


問題文

縦横長さが D のボードがあります、ボードの各ピクセルには色が割り当てられています。このゲームは2人対戦ゲームで、プレイヤー0の初期領地は左上(0,0)、プレイヤー1の初期マスは右下( D - 1, D - 1 )です。プレイヤーはなるべく多くの領地を取得することが目的です。各プレイヤーはターン毎に任意の色を指定することが出来ます。この時、現在の自分の領地の色または相手の領地の色は選択出来ません。色を指定すると以下の操作が行われます。

  • 自分の領地に隣接しており、かつ誰の領地でもなく、指定した色と同じ色のマスを自分の領地にする
  • 自分の領地の色を指定した色に塗り替える

この操作をプレイヤーが交互に行い、全てのマスがいずれかのプレイヤーの領地になるまでゲームを続けます。最終的なスコアは「自分が占領したマス / 全てのマス」となります。

戦略

最初は一直線にフィールドの中心を目指します。(むしろ中心から敵の初期位置寄り)、このゲームでは「相手の陣地は取れない」のでなるべく大きく自分の陣地を囲みに行きたいからです。そして、到達後は相手の伸びしろを消すためにボードの端っこを目指して不可侵領域を作りに行きます。最初は貪欲にマスを取っていましたが、最終的には不可侵領域を多く作るほうが効率が良かったです。

貪欲パターン

貪欲にマスを取ると領地が図のような感じで増えますが、同時に相手の領地も増えやすい形になってしまいます。

f:id:simanman:20160618003525p:plain

f:id:simanman:20160618003539p:plain

不可侵領域パターン

最初に相手に近づいて不可侵領域を作ります

f:id:simanman:20160618003815p:plain

f:id:simanman:20160618003824p:plain

この戦略が取れるのは今回の対戦するAIがランダムに色を選択するタイプだったので、比較的、敵の領地の広がり方が遅いのでこの戦略が使えました。

1日マラソン参加しましたけど集中力が全然持たないですね、もっとゆっくり参加したかったです。あと1日マラソンでtesterにバグ生えてるのは勘弁して下さい

Examples

Example scores:
0) 0.62
1) 0.7975
2) 0.7822222222222223
3) 0.9122
4) 0.8722601248366961