2019/08/25から2019/09/2まで8日間TopCoderで開催されたコンテスト「PolyominoCovering」に参加しました。
provisional 10位/40位でした。システムテストでどうなるかはわかりません。
N行N列の盤面が与えられ、それぞれのマスに-9 ~ 9の数字が書かれている。この盤面を2 ~ 7マスpolyominoで塗り分け、それぞれのpolyominoが含むすべてのマスの数字の積の合計がスコアになる。polyominoの形は自由だが、各サイズのpolyominoはそれぞれ問題によって与えられた数までしか使えない。どのpolyominoにも属さないマスは、1マスにつき-1000点となる。
前提知識として、過去に日本橋ハーフマラソンのA問題として類題が出題されています。細部は違いますが、大筋はかなり似ています。RCOからの講評を読むと、ポリオミノ(当該問題ではオクトミノ)の形と場所を全列挙して上から貪欲という戦略で4位相当のスコアが取れると書かれています。日本橋ハーフマラソンは3時間で2問という超短期間のコンテストだったので、時間内にこの方針以上のことをした / できた人はほとんどいなかったという意味だと考えています。ただし、この方針だけでも実は結構強く、今回のマッチでも同じ方法で20位 / 40位くらいは取れたと思います（僕の2回目の提出はそれです（1回目は提出方法を間違えたのか採点してもらえませんでした））。
日本でマラソンマッチをやっている人の多くは上記の問題を知っていると思うので、今回の問題はどれだけ細部を詰めて高得点を目指せるかという勝負になりそうだな、というのが第一印象でした。
今回の問題では、マスを多くつなげるほど1マスの価値が大きくなっていきます。ここで、実際に全列挙して上から貪欲したもので1マスあたりの平均的なスコアを見てみると、7-ominoでは100000以上、6-ominoで5000程度、5-ominoでは数百くらいで、4-omino以下は10にも満たないことがわかります。空きマスは1マスあたり1000点のペナルティとなるので、5-omino以下で無理にスコアを稼ごうとして空きマスを作るくらいならスコアを度外視してでも空きを減らしに行ったほうが結果的に高得点になると考えて、スコアは[6, 7]-ominoで稼いで[2, 5]-ominoでペナルティを消しにいくという戦略を取ることにしました。
[6, 7]-ominoでスコアを稼ぐといいましたが、実際のところスコアに対する6-ominoと7-ominoの寄与は全く違っていて、6-ominoは7-ominoの5%にも満たないです。さらに、上から貪欲がかなり強いこともあって、6-ominoに計算時間を割いてスコアを上げようとするよりは、7-ominoに殆どの計算時間を使ったほうがよいと考えました。
コンテスト中に悩んでいた部分は殆どが7-ominoの並べ方でしたが、最終的にはビームサーチを採用しました。
前処理として7-ominoの形と位置をすべて列挙しておき、スコア順にソートしておきます。そのあと上から順にみて、各ピースを使うか使わないかを状態としてもつことでビームサーチを行いました。そもそも当該状態ですでに置いたピースと被っていれば使えないので、ひとつの状態で実際に置けるピースは数十個にひとつであることから、状態としては置いたピースの番号をもつことにして、頑張って高速化するとビーム幅3000、8000msくらいで上から2000 ~ 10000番目のピースくらいまでは列挙することができました（盤面の大きさによる）。
7-ominoのビームサーチが終わったあと、ビーム幅3000だとすると、ビームサーチで一番最後に見たピースまでの入れ方を列挙した状態が3000個残ります。これらの状態をスコアの高い順に見て、残った[6, 7]-ominoを上から貪欲に詰め込んでいき、時間内(1000ms程度)で発見した一番スコアの高い配置を[6, 7]-ominoの配置と決めました。
サイズが5以下のポリオミノは、（上から貪欲に詰めたときの）1マスあたりの平均的なスコアが1000よりも小さくなるので、スコア重視で詰めるよりも穴がないように詰めてペナルティを減らしたいという気持ちがありました。
[6, 7]-ominoを配置したあと空いた空間に[2, 5]-ominoを詰めようとするとき、1マスだけ残してその周囲をすべて埋めてしまうと、残ったマスを後から埋めることは不可能になってしまいます。そこで、事前にpolyominoを[6, 7]-ominoおよび壁に接している長さでソートしておく、孤立する空きマスができる場合は置くのをやめるなどすると比較的うまく埋めることができました。
コメント含めて522行です。最終提出時の状態から手を加えていないので、デバッグ用のコメントなども残っています。
// C++11
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
#include <set>
#include <string>
#include <tuple>
#include <cmath>
#include <queue>
#include <utility>
#include <bitset>
using namespace std;
struct Pos{
int x,y;
};
typedef vector<Pos> poly;
typedef vector<poly> polies;
typedef vector<vector<int>> board;
int dx[4]={0,-1,1,0},dy[4]={-1,0,0,1};
int n;
inline int randxor(){
static unsigned int x=123456789,y=987235098,z=957398509,w=879423879;
unsigned int t;
t=(x^(x<<11));
x=y,y=z,z=w;
w=(w^(w>>19))^(t^(t>>8));
return abs((int)w);
}
//時間を測定する関数
const double cycles_per_sec=2800000;
inline double getTime(){
uint32_t lo,hi;
asm volatile("rdtsc":"=a"(lo),"=d"(hi));
return (((uint64_t)hi<<32)|lo)/cycles_per_sec;
}
class Polyomino{ //polyominoの列挙
public:
int N=0;
int offset=0;
polies P;
void DFS(poly& p, board& B, int used, int maxi){
//polyominoが完成していたらPに入れて終了
if(p.size()==N){
P.push_back(p);
return;
}
//ボードを見て、usedより大きい数字があれば順に四角形を置く
board B_copy=B;
int maxi_copy=maxi;
for(int i=-(N);i<N;i++){
for(int j=-(N);j<N;j++){
if(B[i+offset][j+offset]<=used)
continue;
p.push_back(Pos{i,j});
int nextUsed=B[i+offset][j+offset];
//周囲に数字を置く
for(int k=0;k<4;k++){
if(B[i+dx[k]+offset][j+dy[k]+offset]==0){
maxi++;
B[i+dx[k]+offset][j+dy[k]+offset]=maxi;
}
}
DFS(p,B,nextUsed,maxi);
p.pop_back();
B=B_copy;
maxi=maxi_copy;
}
}
}
Polyomino(int n){
N=n;
offset=N;
board B(2*(N+1),vector<int>(2*(N+1)));
for(int i=-(N-1);i<0;i++)
B[i+offset][0+offset]=-1;
for(int i=-(N-1);i<=(N-1);i++)
for(int j=-(N-1);j<0;j++)
B[i+offset][j+offset]=-1;
poly p;
B[0+offset][0+offset]=1;
DFS(p,B,0,1);
}
};
int num(int x, int y){
return x*n+y;
}
bool isOut(int x,int y){
return (x<0 || n<=x || y<0 || n<=y);
}
class PolyominoCovering {
public:
vector<int> findSolution(int N, vector<int> grid, vector<int> tiles)
{
double startTime=getTime();
vector<int> remains(8); //残り使えるporyominoの数
for(int i=0;i<6;i++)
remains[i+2]=tiles[i];
n=N;
vector<int> ans(N*N);
for(int i=0;i<N*N;i++) //ansを-1で初期化
ans[i]=-1;
polies P[8]; //poryomino
for(int i=2;i<=7;i++){ //poryominoを全列挙する
Polyomino Po(i);
P[i]=Po.P;
}
//全部のporyominoを全部のマスを始点にして試して、スコアを記録する
vector<tuple<long long, int, int, int, int>> scores; //(スコア、サイズ、番号、x、y)
for(int i=2;i<=7;i++){
for(int j=0;j<P[i].size();j++){
poly p=P[i][j];
for(int x=0;x<N;x++){
for(int y=0;y<N;y++){
long long score=1;
bool avail=1;
for(Pos d:p){
int X=x+d.x,Y=y+d.y;
if(isOut(X,Y)){ //盤面からはみ出したら駄目
avail=0;
break;
}
int now=num(X,Y);
if(i>=5 && grid[now]==0){ //サイズが5以上のときは、0が含まれたら自動的に弾いてみる（高速化のため）
avail=0;
break;
}
score*=grid[now];
}
if(i>=5 && score<0) //サイズが5以上のときは、スコアが負なら自動的に弾いてみる（高速化のため）
avail=0;
if(avail)
scores.emplace_back(score, i, j, x, y);
}
}
}
}
sort(scores.begin(),scores.end(),greater<tuple<long long, int, int, int, int>>());
int bigSize=6; //このサイズまでは貪欲に置く
//上から貪欲に見ていく
long long scoreSum=0;
int polNum=1;
vector<int> ans_copy=ans;
vector<int> remains_copy=remains;
double nowTime=0., endTime=8500., endTime2=9700.;
vector<pair<long long, vector<int>>> checked={make_pair(0LL, vector<int>())}, nextChecked;
vector<char> ans_seven(N*N);
//最初に、サイズ7だけでビームサーチをする
for(int selectIdx=0;selectIdx<scores.size();selectIdx++){
nowTime=getTime()-startTime;
if(nowTime>=endTime){
break;
}
if(selectIdx>10 && checked.size()==1)
break;
if(get<1>(scores[selectIdx])<7) //size<7なら飛ばす
continue;
nextChecked.clear();
for(auto& ch:checked){ //すでに見た状態を回す
vector<int>& state=ch.second;
nextChecked.push_back(ch);
vector<char> ans_temp=ans_seven;
int remains_seven=remains_copy[7]-state.size();
if(remains_seven==0)
continue;
long long scoreSum_temp=ch.first;
for(int idx:state){ //state内のピースを入れていく
long long score;
int size, number, x, y;
tie(score, size, number, x, y)=scores[idx];
poly& p=P[size][number];
for(Pos& d:p)
ans_temp[num(x+d.x, y+d.y)]=1;
}
//selectIdxを入れられるか調べる
long long score;
int size, number, x, y;
tie(score, size, number, x, y)=scores[selectIdx];
poly& p=P[size][number];
bool avail=1;
for(Pos& d:p){
if(ans_temp[num(x+d.x, y+d.y)]){
avail=0;
break;
}
}
if(avail){ //置く
scoreSum_temp+=score;
for(Pos& d:p)
ans_temp[num(x+d.x, y+d.y)]=1;
//nextCheckedに入れる
state.push_back(selectIdx);
nextChecked.emplace_back(scoreSum_temp, state);
}
}
sort(nextChecked.begin(), nextChecked.end(), greater<pair<long long, vector<int>>>());
checked.clear();
for(int i=0;i<min(3000, int(nextChecked.size()));i++){
checked.push_back(nextChecked[i]);
}
}
//最後に残ったcheckedをすべて見て、6まで貪欲して最大を採用する
for(int chIdx=0;chIdx<checked.size();chIdx++){
auto& ch=checked[chIdx];
vector<int> state=ch.second;
vector<int> ans_temp=ans_copy;
vector<int> remains_temp=remains_copy;
long long scoreSum_temp=0;
int polNum_temp=1;
nowTime=getTime()-startTime;
if(nowTime>=endTime2){
break;
}
//これまで見た状態を入れる
scoreSum_temp=ch.first;
for(int idx:state){
long long score;
int size, number, x, y;
tie(score, size, number, x, y)=scores[idx];
poly& p=P[size][number];
for(Pos& d:p)
ans_temp[num(x+d.x, y+d.y)]=polNum_temp;
polNum_temp++;
remains_temp[size]--;
}
for(int idx=0;idx<scores.size();idx++){
long long score;
int size, number, x, y;
tie(score, size, number, x, y)=scores[idx];
if(size<bigSize)
continue;
if(remains_temp[6]==0 && remains_temp[7]==0) //bigSizeが両方切れてたら終了する（ここ埋め込み）
break;
if(remains_temp[size]==0) //すでにそのサイズのタイルを使い切っていればskip
continue;
//すでに置かれているものと被ってなければ置いていく
poly& p=P[size][number];
bool avail=1;
for(Pos& d:p){
if(ans_temp[num(x+d.x, y+d.y)]!=-1){
avail=0;
break;
}
}
if(avail){ //置く
scoreSum_temp+=score;
for(Pos& d:p)
ans_temp[num(x+d.x, y+d.y)]=polNum_temp;
polNum_temp++;
remains_temp[size]--;
}
}
if(scoreSum<scoreSum_temp){
scoreSum=scoreSum_temp;
ans=ans_temp;
remains=remains_temp;
polNum=polNum_temp;
}
}
//各マスからBFSをして、空きマスの集合のサイズが今使える最大のピース以下のものは貪欲に埋めてしまう
vector<int> visited(N*N);
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(ans[num(i,j)]!=-1 || visited[num(i,j)])
continue;
int groupSize=1; //空きマス集合のサイズ
queue<Pos> que;
que.push(Pos{i,j});
visited[num(i,j)]=1;
while(que.size()){
Pos nowPos=que.front();
que.pop();
int x=nowPos.x, y=nowPos.y;
int now=num(x,y);
for(int k=0;k<4;k++){ //周囲4マスを見る
int X=x+dx[k], Y=y+dy[k];
int next=num(X,Y);
if(isOut(X,Y) || visited[next] || ans[next]!=-1)
continue;
que.push(Pos{X,Y});
visited[next]=1;
groupSize++;
}
}
if(groupSize>=bigSize || remains[groupSize]==0)
continue;
remains[groupSize]--;
visited=vector<int>(N*N);
que.push(Pos{i,j});
visited[num(i,j)];
ans[num(i,j)]=polNum;
while(que.size()){
Pos nowPos=que.front();
que.pop();
int x=nowPos.x, y=nowPos.y;
int now=num(x,y);
for(int k=0;k<4;k++){ //周囲4マスを見る
int X=x+dx[k], Y=y+dy[k];
int next=num(X,Y);
if(isOut(X,Y) || visited[next] || ans[next]!=-1)
continue;
que.push(Pos{X,Y});
visited[next]=1;
ans[next]=polNum;
}
}
polNum++;
}
}
vector<tuple<int, int, long long, int, int, int>> smallPieces; //小さいサイズのピースの中で、置くことが可能なもの(size, score, number, x, y)
for(auto tup:scores){
long long score;
int size, number, x, y;
tie(score, size, number, x, y)=tup;
if(size>=bigSize)
continue;
//すでにそのサイズのタイルを使い切っていればskip
if(remains[size]==0)
continue;
//すでに置かれているものと被ってなければsmallPiecesに入れる
poly p=P[size][number];
bool avail=1;
for(Pos d:p){
int now=num(x+d.x, y+d.y);
if(ans[now]!=-1){
avail=0;
break;
}
}
if(!avail)
continue;
//隣接しているピースの数を数える
set<pair<int,int>> tes;
for(Pos d:p){
for(int k=0;k<4;k++){
if(isOut(x+d.x+dx[k], y+d.y+dy[k]) || ans[num(x+d.x+dx[k], y+d.y+dy[k])]!=-1)
tes.insert(make_pair(x+d.x+dx[k], y+d.y+dy[k]));
}
}
smallPieces.emplace_back(size, tes.size(), score, number, x, y);
}
sort(smallPieces.begin(), smallPieces.end(), greater<tuple<int, int, long long, int, int, int>>());
//貪欲に置く
for(auto tup:smallPieces){
long long score;
int size, np, number, x, y;
tie(size, np, score, number, x, y)=tup;
poly p=P[size][number];
if(remains[size]==0)
continue;
bool avail=1;
for(Pos d:p){ //置けるか調べる
int now=num(x+d.x, y+d.y);
if(ans[now]!=-1){
avail=0;
break;
}
}
if(!avail)
continue;
for(Pos d:p) //いったん埋めとく
ans[num(x+d.x,y+d.y)]=-2;
for(Pos d:p){ //隣接する空きマスが孤立しないかどうか調べる
for(int k=0;k<4;k++){ //隣接するマス
if(isOut(x+d.x+dx[k], y+d.y+dy[k]))
continue;
if(ans[num(x+d.x+dx[k], y+d.y+dy[k])]!=-1)
continue;
//隣接するマスが自分自身に含まれているなら無視
bool inc=0;
for(Pos e:p){
if(x+d.x+dx[k]==x+e.x && y+d.y+dy[k]==y+e.y)
inc=1;
}
if(inc)
continue;
int nei=0; //隣接している埋まっているマスの数
for(int l=0;l<4;l++){ //隣接するマスに隣接するマス
int X=x+d.x+dx[k]+dx[l], Y=y+d.y+dy[k]+dy[l];
int next=num(X,Y);
if(isOut(X,Y) || ans[next]!=-1)
nei++;
}
if(nei==4) //孤立するなら置かない
avail=0;
}
}
if(avail){ //置く
scoreSum+=score;
for(Pos d:p){
int now=num(x+d.x, y+d.y);
ans[now]=polNum;
}
polNum++;
remains[size]--;
}
else{
for(Pos d:p) //いったん埋めとく
ans[num(x+d.x,y+d.y)]=-1;
}
}
//孤立を無視してもう一回入れる
for(auto tup:smallPieces){
long long score;
int size, np, number, x, y;
tie(size, np, score, number, x, y)=tup;
poly p=P[size][number];
if(remains[size]==0)
continue;
bool avail=1;
for(Pos d:p){ //置けるか調べる
int now=num(x+d.x, y+d.y);
if(ans[now]!=-1){
avail=0;
break;
}
}
if(!avail)
continue;
if(avail){ //置く
scoreSum+=score;
for(Pos d:p){
int now=num(x+d.x, y+d.y);
ans[now]=polNum;
}
polNum++;
remains[size]--;
}
}
return ans;
}
};
// -------8<------- end of solution submitted to the website -------8<-------
template<class T> void getVector(vector<T>& v) {
for (int i = 0; i < v.size(); ++i)
cin >> v[i];
}
int main() {
PolyominoCovering pc;
int N;
cin >> N;
vector<int> grid(N*N);
getVector(grid);
vector<int> tiles(6);
getVector(tiles);
vector<int> ret = pc.findSolution(N, grid, tiles);
cout << ret.size() << endl;
for (int i = 0; i < (int)ret.size(); ++i)
cout << ret[i] << endl;
cout.flush();
}
おまけ
戻る