NYC Lightning Round 参戦記録

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

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

topcoder１日マラソン開催されるのであれば、すぐ寝る。されないのであれば、プログラミングして寝る。
— nico_shindannin (@nico_shindannin) 2016年6月16日

あ、いまやってたｗ https://t.co/xtlNnrnb1b
— nico_shindannin (@nico_shindannin) 2016年6月16日

問題文

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

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

自分の領地の色を指定した色に塗り替える

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

戦略

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