2019/01/24から2019/01/31まで7日間TopCoderで開催されたコンテスト「PointsOnGrid」に参加しました。
32位/106人でした。自分より上位の多くが黄色以上なので、良い順位だと思います。レートは1540で黃になりました。
H行W列の盤面が与えられ、それぞれのマスに0 ~ 9の数字が書かれている。いくつかのマスを塗って、塗られたマスに書かれている数字の合計がスコアになる。ただし、盤面のなかからどのようなh*wマスの領域をとってきても、そのなかで塗られているマスの数がKmin個以上Kmax個以下となるような塗り方でなくてはならない。
ページトップの画像は$H=8, W=8, h=3, w=4, Kmin=0, Kmax=5$の場合の塗り方の一例である。$8\times8$の盤面からどのような$3\times4$の領域を取ってきても、その中で塗られているマスの数が0以上5以下であることがわかる。
上図は、先程の盤面に追加で1マス(黄で表されているマス)を塗ったものである。赤で囲まれた$3\times4$の領域について、塗られているマスの数が6になっている。これはKmaxよりも大きいので、この塗り方は問題の条件を満たさない。
前回と同じく典型的な焼きなまし系の問題に見えたので、焼きなましをしました。焼きなましをするにあたって、近傍をどのように取るかということをはじめに考えました。以下に述べます。
以下、「$i$行$j$列目のマスを左上とするような$h\times w$マスの領域に含まれる、塗られたマスの数」を$p_{ij}$と呼ぶことにします。たとえば上にあげた2枚の図では、マス$(0,0)$を左上とした$3\times4$の領域の中に塗られたマスは5つあるので、$p_{ij}=5$となります。
今回の問題では、「どのような$h\times w$の領域を取ってきても、そのなかで塗られているマスの数が必ずKmin以上Kmax以下であるように塗らなくてはならない」という制約が非常に強いものとなっています。よって、焼きなましの遷移についてはスコアの変化よりも「変化する$p_{ij}$の数」が小さいものをより小さい遷移と考えることにしました。
マスをランダムに選んで、そのマスが塗られていなければ塗り、塗られていれば消します。焼きなましの最中に塗られたマスの数を変える遷移は明らかに必要であると考えられます。ただし、マスを1つ塗ったり消したりする遷移は自然な発想ではありますが、それほど小さい遷移ではありません。今回の問題設定においてはそれぞれのマスはh*w個の領域に属しているため、1つのマスを変更するとh*w個の領域に影響があることになるためです。スコア計算はO(h),遷移はO(H*W)です。
すでに塗られているマスをランダムに選んで、上下にずらします。つまり、選んだマスを塗られていない状態に変えて、その上下にある塗られていないマスを塗ります。この遷移では2マスが変更されていますが、実際にはFlipよりも小さい遷移です。
上図において、$i$行$j$列目が緑になっていることは$p_{ij}$が$+1$されていることを、$i$行$j$列目が赤になっていることは$p_{ij}$が$-1$されていることを表しています。1マス塗る操作と1マス消す操作を同時に行うとそれぞれの効果が打ち消し合って、片方だけを行うよりも全体的な影響範囲が小さくなっていることがわかります。Slideのスコア計算はO(1),遷移はO(W)です。
すでに塗られているマスと塗られていないマスをランダムに選んで、入れ替えます。Swapで選ぶマスが上下に隣り合っているときSlideと同値になります。今回焼きなましのスコアにはKmaxを超えた/Kminを下回った$p_{ij}$の数のほかに塗ったマスに書かれている数字の大きさも含めているため、後半温度が下がってくると上下を0や1など小さい数に挟まれたマスが全く遷移しなくなることを防ぐためにランダムな入れ替えも採用しました。実装時間の関係でスコア計算、遷移ともにO(H*W)です。
遷移は以上です。遷移100回につきFlipが1回、Swapが5回、Slideが94回の配分になっています。これは最も小さい遷移であるSlideをメインで使うという戦略であると同時に、計算量の大きい遷移を少なくすることで平均的な計算量を落とそうという試みでもあります。
KmaxとKminの差が非常に小さいときなど、焼きなましを行っても時間内に有効な解を作れないことは非常に怖いです。そのような場合のために、validな解を最初にひとつ用意しておくことにしました。$h\times w$の領域の中にKmaxこのマスを塗り、それを繰り返したパターンは必ずすべての$h\times w$領域がKmax個の塗られたマスを含みます。このような塗り方について、最も得点の高くなるようなものは貪欲法で求めることができて、時間内にこの解よりもよいものが得られなかった場合はこれを出力しました。下図は、そのような状況が起きてしまった例です。
焼きなましの最中に最高スコアを更新したとき、その状態を記録しておくことにしました。実際のところ、焼きなまし終了時の状態は最高スコアとほぼ変わらないものが出ていましたが、今回のランキングは自分のスコア/参加者全員の最高スコアで得点が決まっていたため、理論値が数百点であるようなケースにおいては数点の違いで結構順位が変わったりしていて、そこを安定させるために導入しました。Flipの遷移がもともとO(H*W)なので、そこで同時に行いました。
焼きなましの最中に一度温度を戻すことを試みました。スコアは少し伸びましたが、誤差かもしれません……。
コメント含めて613行です。最終提出時の状態から手を加えていないので、デバッグ用のコメントなども残っています。
// C++11
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <sstream>
#include <vector>
#include <set>
#include <string>
#include <cmath>
#include <tuple>
using namespace std;
struct Pos{ //座標(対応関係i→x, j→yで統一)
int x,y;
};
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 get_time(){
uint32_t lo,hi;
asm volatile("rdtsc":"=a"(lo),"=d"(hi));
return (((uint64_t)hi<<32)|lo)/cycles_per_sec;
}
inline bool isInBoard(int x,int y,int H,int W){ //座標が盤面の中であればtrue
return !(x<0 || H<=x || y<0 || W<=y);
}
bool isPainted[55][55]={}; //マス(i,j)が塗られているか
int numPainted[55][55]={}; //マス(i,j)を左上としたサブグリッドの中で塗られているマスの数
int shortSum[55][55]={},longSum[55][55]={}; //Kmin未満の分とKmax超過分の累積和
int justMin[55][55]={},justMax[55][55]={}; //Kmin,Kmaxちょうどのサブグリッドの累積和
int dx[2]={-1,1}; //↑↓
int iteration=0;
int maxScore=0,maxItr=0; //highestスコアと、最後にhighestスコアが出たときのiteration
vector<string> maxAns; //最大スコアの解
void rollBack(vector<string>& maxAns,int H,int W,int h,int w,int Kmax,int Kmin){ //maxAnsまで巻き戻す
//isPaintedを更新する
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(maxAns[i][j]=='x')
isPainted[i][j]=1;
else
isPainted[i][j]=0;
}
}
//numPaintedを更新する
for(int i=0;i<=H;i++){
for(int j=0;j<=W;j++){
numPainted[i][j]=0;
for(int a=i;a<min(i+h,H);a++){
for(int b=j;b<min(j+w,W);b++){
numPainted[i][j]+=isPainted[a][b];
}
}
}
}
//各行の累積和をとる
for(int i=1;i<=H-h+1;i++){
for(int j=1;j<=W-w+1;j++){
shortSum[i][j]=shortSum[i][j-1]+max(0,Kmin-numPainted[i-1][j-1]);
longSum[i][j]=longSum[i][j-1]+max(0,numPainted[i-1][j-1]-Kmax);
}
for(int j=W-w+2;j<=W;j++){
shortSum[i][j]=shortSum[i][j-1];
longSum[i][j]=longSum[i][j-1];
}
}
//JustKminとJustKmaxも更新する
for(int i=1;i<=H-h+1;i++){
for(int j=1;j<=W-w+1;j++){
justMin[i][j]=justMin[i][j-1]+(numPainted[i-1][j-1]==Kmin);
justMax[i][j]=justMax[i][j-1]+(numPainted[i-1][j-1]==Kmax);
}
for(int j=W-w+2;j<=W;j++){
justMin[i][j]=justMin[i][j-1];
justMax[i][j]=justMax[i][j-1];
}
}
}
int calcSlideDifScore(Pos change,int dir,int penalty,int H,int W,int h,int w,int Kmax,int Kmin){ //移動でのスコア計算
int ret=0;
int x=change.x+1,y=change.y+1; //1-indexed
if(dir){ //↑移動
if(0<=change.x-h+1)
ret-=shortSum[x-h+1][y]-shortSum[x-h+1][max(0,y-w)];
if(change.x+1<H)
ret+=shortSum[x+1][y]-shortSum[x+1][max(0,y-w)];
if(0<=change.x-h+1)
ret+=longSum[x-h+1][y]-longSum[x-h+1][max(0,y-w)];
if(change.x+1<H)
ret-=longSum[x+1][y]-longSum[x+1][max(0,y-w)];
//↑過少、超過
//↓ちょうど
if(0<=change.x-h+1)
ret-=justMin[x-h+1][y]-justMin[x-h+1][max(0,y-w)];
if(change.x+1<H)
ret-=justMax[x+1][y]-justMax[x+1][max(0,y-w)];
}
else{
ret-=shortSum[x][y]-shortSum[x][max(0,y-w)];
if(0<=change.x-h)
ret+=shortSum[x-h][y]-shortSum[x-h][max(0,y-w)];
ret+=longSum[x][y]-longSum[x][max(0,y-w)];
if(0<=change.x-h)
ret-=longSum[x-h][y]-longSum[x-h][max(0,y-w)];
//↑過少、超過
//↓ちょうど
ret-=justMin[x][y]-justMin[x][max(0,y-w)];
if(0<=change.x-h)
ret-=justMax[x-h][y]-justMax[x-h][max(0,y-w)];
}
ret*=penalty;
return ret;
}
void slidePaint(Pos change,int dir,int H,int W,int h,int w,int Kmax,int Kmin){
int x=change.x+1,y=change.y+1; //1-indexedにする
swap(isPainted[change.x][change.y],isPainted[change.x+dx[dir]][change.y]); //isPaintedを更新する
if(dir){ //↓移動
for(int i=max(0,change.y-w+1);i<=min(change.y,W-w);i++){ //numPaintedを更新する
if(change.x+1<=H-h)
numPainted[change.x+1][i]++;
if(0<=change.x-h+1 && change.x-h+1<=H-h)
numPainted[change.x-h+1][i]--;
}
for(int i=1;i<=W-w+1;i++){
if(change.x+1<=H-h){
shortSum[x+1][i]=shortSum[x+1][i-1]+max(0,Kmin-numPainted[change.x+1][i-1]);
longSum[x+1][i]=longSum[x+1][i-1]+max(0,numPainted[change.x+1][i-1]-Kmax);
}
if(0<=change.x-h+1 && change.x-h+1<=H-h){
shortSum[x-h+1][i]=shortSum[x-h+1][i-1]+max(0,Kmin-numPainted[change.x-h+1][i-1]);
longSum[x-h+1][i]=longSum[x-h+1][i-1]+max(0,numPainted[change.x-h+1][i-1]-Kmax);
}
}
for(int i=W-w+2;i<=W;i++){
if(change.x+1<=H-h){
shortSum[x+1][i]=shortSum[x+1][i-1];
longSum[x+1][i]=longSum[x+1][i-1];
}
if(0<=change.x-h+1 && change.x-h+1<=H-h){
shortSum[x-h+1][i]=shortSum[x-h+1][i-1];
longSum[x-h+1][i]=longSum[x-h+1][i-1];
}
}
//justMin,Maxも更新する
for(int i=1;i<=W-w+1;i++){
if(change.x+1<=H-h){
justMin[x+1][i]=justMin[x+1][i-1]+(numPainted[change.x+1][i-1]==Kmin);
justMax[x+1][i]=justMax[x+1][i-1]+(numPainted[change.x+1][i-1]==Kmax);
}
if(0<=change.x-h+1 && change.x-h+1<=H-h){
justMin[x-h+1][i]=justMin[x-h+1][i-1]+(numPainted[change.x-h+1][i-1]==Kmin);
justMax[x-h+1][i]=justMax[x-h+1][i-1]+(numPainted[change.x-h+1][i-1]==Kmax);
}
}
for(int i=W-w+2;i<=W;i++){
if(change.x+1<=H-h){
justMin[x+1][i]=justMin[x+1][i-1];
justMax[x+1][i]=justMax[x+1][i-1];
}
if(0<=change.x-h+1 && change.x-h+1<=H-h){
justMin[x-h+1][i]=justMin[x-h+1][i-1];
justMax[x-h+1][i]=justMax[x-h+1][i-1];
}
}
}
else{ //↑移動
for(int i=max(0,change.y-w+1);i<=min(change.y,W-w);i++){ //numPaintedを更新する
if(0<=change.x-h && change.x-h<=H-h)
numPainted[change.x-h][i]++;
if(change.x<=H-h)
numPainted[change.x][i]--;
}
for(int i=1;i<=W-w+1;i++){
if(0<=change.x-h && change.x-h<=H-h){
shortSum[x-h][i]=shortSum[x-h][i-1]+max(0,Kmin-numPainted[change.x-h][i-1]);
longSum[x-h][i]=longSum[x-h][i]+max(0,numPainted[change.x-h][i-1]-Kmax);
}
if(change.x<=H-h){
shortSum[x][i]=shortSum[x][i-1]+max(0,Kmin-numPainted[change.x][i-1]);
longSum[x][i]=longSum[x][i-1]+max(0,numPainted[change.x][i-1]-Kmax);
}
}
for(int i=W-w+2;i<=W;i++){
if(0<=change.x-h && change.x-h<=H-h){
shortSum[x-h][i]=shortSum[x-h][i-1];
longSum[x-h][i]=longSum[x-h][i];
}
if(change.x<=H-h){
shortSum[x][i]=shortSum[x][i-1];
longSum[x][i]=longSum[x][i-1];
}
}
//justMin,justMaxも更新する
for(int i=1;i<=W-w+1;i++){
if(0<=change.x-h && change.x-h<=H-h){
justMin[x-h][i]=justMin[x-h][i-1]+(numPainted[change.x-h][i-1]==Kmin);
justMax[x-h][i]=justMax[x-h][i-1]+(numPainted[change.x-h][i-1]==Kmax);
}
if(change.x<=H-h){
justMin[x][i]=justMin[x][i-1]+(numPainted[change.x][i-1]==Kmin);
justMax[x][i]=justMax[x][i-1]+(numPainted[change.x][i-1]==Kmax);
}
}
for(int i=W-w+2;i<=W;i++){
if(0<=change.x-h && change.x-h<=H-h){
justMin[x-h][i]=justMin[x-h][i-1];
justMax[x-h][i]=justMax[x-h][i-1];
}
if(change.x<=H-h){
justMin[x][i]=justMin[x][i-1];
justMax[x][i]=justMax[x][i-1];
}
}
}
}
int calcFlipDifScore(Pos change,int penalty,int H,int W,int h,int w){ //生成・消滅のスコア差を計算する
int ret=0;
int x=change.x+1,y=change.y+1; //1-indexed
if(isPainted[change.x][change.y]){ //消滅
for(int i=max(0,x-h+1);i<=x;i++){
ret-=shortSum[i][y]-shortSum[i][max(0,y-w)];
ret+=longSum[i][y]-longSum[i][max(0,y-w)];
}
for(int i=max(0,x-h+1);i<=x;i++){
ret-=justMin[i][y]-justMin[i][max(0,y-w)];
}
}
else{ //生成
for(int i=max(0,x-h+1);i<=x;i++){
ret+=shortSum[i][y]-shortSum[i][max(0,y-w)];
ret-=longSum[i][y]-longSum[i][max(0,y-w)];
}
for(int i=max(0,x-h+1);i<=x;i++){
ret-=justMax[i][y]-justMax[i][max(0,y-w)];
}
}
ret*=penalty;
return ret;
}
void flipPaint(Pos change,int H,int W,int h,int w,int Kmax,int Kmin,vector<string>& board){ //生成・消滅
int x=change.x+1,y=change.y+1; //1-indexed;
if(isPainted[change.x][change.y]){ //消滅
for(int i=max(0,change.x-h+1);i<=min(change.x,H);i++){
for(int j=max(0,change.y-w+1);j<=min(change.y,W);j++){
numPainted[i][j]--;
}
}
}
else{ //生成
for(int i=max(0,change.x-h+1);i<=min(change.x,H);i++){
for(int j=max(0,change.y-w+1);j<=min(change.y,W);j++){
numPainted[i][j]++;
}
}
}
isPainted[change.x][change.y]=!isPainted[change.x][change.y]; //反転
//各行の累積和をとる
for(int i=1;i<=H-h+1;i++){
for(int j=1;j<=W-w+1;j++){
shortSum[i][j]=shortSum[i][j-1]+max(0,Kmin-numPainted[i-1][j-1]);
longSum[i][j]=longSum[i][j-1]+max(0,numPainted[i-1][j-1]-Kmax);
}
for(int j=W-w+2;j<=W;j++){
shortSum[i][j]=shortSum[i][j-1];
longSum[i][j]=longSum[i][j-1];
}
}
//JustKminとJustKmaxも更新する
for(int i=1;i<=H-h+1;i++){
for(int j=1;j<=W-w+1;j++){
justMin[i][j]=justMin[i][j-1]+(numPainted[i-1][j-1]==Kmin);
justMax[i][j]=justMax[i][j-1]+(numPainted[i-1][j-1]==Kmax);
}
for(int j=W-w+2;j<=W;j++){
justMin[i][j]=justMin[i][j-1];
justMax[i][j]=justMax[i][j-1];
}
}
//解がvalidかどうか確認する
for(int i=0;i<H-h+1;i++){
for(int j=0;j<W-w+1;j++){
if(numPainted[i][j]<Kmin || Kmax<numPainted[i][j])
return;
}
}
//スコア計算
int score=0;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(isPainted[i][j])
score+=board[i][j]-'0';
}
}
if(maxScore<score){
maxScore=score;
maxItr=iteration;
//最大スコアが出たらmaxAnsを更新する
maxAns.clear();
for(int i=0;i<H;i++){
string S;
for(int j=0;j<W;j++){
S+=(isPainted[i][j]?'x':'.');
}
maxAns.push_back(S);
}
}
if(maxItr+1000000<iteration){ //最後に更新されたのが一定以上前ならロールバックする
rollBack(maxAns,H,W,h,w,Kmax,Kmin);
maxItr=iteration;
//cerr<<"rollback"<<endl;
}
//cerr<<iteration<<" "<<score<<" "<<maxScore<<endl;
}
int calcSwapDifScore(Pos A,Pos B,int penalty,int H,int W,int h,int w,int Kmax,int Kmin,vector<string>& board){
int ret=0;
//Aはpainted, Bは!painted
ret+=calcFlipDifScore(A,penalty,H,W,h,w);
flipPaint(A,H,W,h,w,Kmax,Kmin,board);
ret+=calcFlipDifScore(B,penalty,H,W,h,w);
ret*=penalty;
return ret;
}
vector<string> validPattern(int H,int W,int h,int w,int Kmin,int Kmax,vector<string>& board){ //絶対にvalidな解を作る
vector<string> subGrid;
int subScores[55][55]={};
for(int i=0;i<H;i++){
for(int j=0;j<W;j++)
subScores[i%h][j%w]+=board[i][j]-'0';
}
vector<tuple<int,int,int>> vec;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++)
vec.push_back(make_tuple(subScores[i][j],i,j));
}
sort(vec.begin(),vec.end(),greater<tuple<int,int,int>>());
//Kmax個のpaintedをふくむサブグリッドを作る
for(int i=0;i<h;i++){
string S;
for(int j=0;j<w;j++)
S+='.';
subGrid.push_back(S);
}
for(int i=0;i<Kmax;i++){
int s,x,y;
tie(s,x,y)=vec[i];
subGrid[x][y]='x';
}
vector<string> ret;
//投影する
for(int i=0;i<H;i++){
string S;
for(int j=0;j<W;j++)
S+=subGrid[i%h][j%w];
ret.push_back(S);
}
return ret;
}
class PointsOnGrid {
public:
vector<string> findSolution(int H, int W, int h, int w, int Kmin, int Kmax, vector<string> board) {
vector<string> validAns=validPattern(H,W,h,w,Kmin,Kmax,board);
//変数群
const double startTime=get_time();
double nowTime=0.;
double endTime=9800.; //焼きなます時間
double startTemp=50.,endTemp=1.; //最初の温度、最後の温度
int penalty=50; //ペナルティ
//最初にいくつか撒く
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
isPainted[i][j]=(validAns[i][j]=='x');
}
}
for(int i=0;i<=H;i++){ //numPaintedを入れる
for(int j=0;j<=W;j++){
for(int a=i;a<min(i+h,H);a++){
for(int b=j;b<min(j+w,W);b++){
numPainted[i][j]+=isPainted[a][b];
}
}
}
}
//各行の累積和をとる
for(int i=1;i<=H-h+1;i++){
for(int j=1;j<=W-w+1;j++){
shortSum[i][j]=shortSum[i][j-1]+max(0,Kmin-numPainted[i-1][j-1]);
longSum[i][j]=longSum[i][j-1]+max(0,numPainted[i-1][j-1]-Kmax);
}
for(int j=W-w+2;j<=W;j++){
shortSum[i][j]=shortSum[i][j-1];
longSum[i][j]=longSum[i][j-1];
}
}
//JustKminとJustKmaxも更新する
for(int i=1;i<=H-h+1;i++){
for(int j=1;j<=W-w+1;j++){
justMin[i][j]=justMin[i][j-1]+(numPainted[i-1][j-1]==Kmin);
justMax[i][j]=justMax[i][j-1]+(numPainted[i-1][j-1]==Kmax);
}
for(int j=W-w+2;j<=W;j++){
justMin[i][j]=justMin[i][j-1];
justMax[i][j]=justMax[i][j-1];
}
}
int itr=0;
//焼きなまし
while(nowTime<endTime){
int halfTime=endTime/2;
if(nowTime<halfTime)
penalty=max(5,(int)(1000*((exp(nowTime/halfTime)-1)/exp(1))));
else
penalty=max(5,(int)(1000*((exp((nowTime-halfTime)/(endTime-halfTime))-1)/exp(1))));
iteration++;
nowTime=get_time()-startTime; //時間の更新
Pos change{randxor()%H,randxor()%W}; //変更する場所を決める
if(iteration%100==0){ //生成・消滅
itr++;
int difScore=0,numScore=0;
if(isPainted[change.x][change.y])
numScore-=board[change.x][change.y]-'0';
else
numScore+=board[change.x][change.y]-'0';
difScore=calcFlipDifScore(change,penalty,H,W,h,w);
difScore+=numScore*50;
double temp=startTemp+(endTemp-startTemp)*nowTime/endTime; //温度
double probability=exp(difScore/temp),randVal=(double)(randxor()%10000)/10000; //遷移確率
//cerr<<temp<<" "<<probability<<" "<<randVal<<endl;
if(difScore<0 && nowTime>endTime-1000)
continue;
if(difScore>0 || probability>randVal){ //遷移するとき
flipPaint(change,H,W,h,w,Kmax,Kmin,board);
}
}
else if(iteration%100>95){ //swap
int difScore=0,numScore=0;
Pos toSwap{randxor()%H,randxor()%W}; //swap先を決める
if(isPainted[change.x][change.y]==isPainted[toSwap.x][toSwap.y])
continue;
if(!isPainted[change.x][change.y])
swap(change,toSwap); //changeだけがpainted
numScore+=board[toSwap.x][toSwap.y]-board[change.x][change.y];
difScore=calcSwapDifScore(change,toSwap,penalty,H,W,h,w,Kmax,Kmin,board);
difScore+=numScore*70;
double temp=startTemp+(endTemp-startTemp)*nowTime/endTime; //温度
double probability=exp(difScore/temp),randVal=(double)(randxor()%10000)/10000; //遷移確率
if(difScore<0 && nowTime>endTime-1000){
flipPaint(change,H,W,h,w,Kmax,Kmin,board);
continue;
}
if(difScore>0 || probability>randVal){ //遷移するとき
flipPaint(toSwap,H,W,h,w,Kmax,Kmin,board);
}
else{
flipPaint(change,H,W,h,w,Kmax,Kmin,board);
}
}
else{ //スライド
int dir=randxor()%2;
if(isPainted[change.x][change.y]==isPainted[change.x+dx[dir]][change.y])
continue;
if(!isInBoard(change.x+dx[dir],change.y,H,W))
continue;
int difScore=0,numScore=0;
if(isPainted[change.x][change.y])
difScore=calcSlideDifScore(change,dir,penalty*10,H,W,h,w,Kmax,Kmin);
else
difScore=calcSlideDifScore(Pos{change.x+dx[dir],change.y},!dir,penalty*10,H,W,h,w,Kmax,Kmin);
if(isPainted[change.x][change.y])
numScore+=(board[change.x+dx[dir]][change.y]-'0')-(board[change.x][change.y]-'0');
else
numScore-=(board[change.x+dx[dir]][change.y]-'0')-(board[change.x][change.y]-'0');
difScore+=numScore*70;
double temp=startTemp+(endTemp-startTemp)*nowTime/endTime; //温度
double probability=exp(difScore/temp),randVal=(double)(randxor()%10000)/10000; //遷移確率
if(difScore<0 && nowTime>endTime-1000)
continue;
if(difScore>0){ //遷移するとき
if(isPainted[change.x][change.y])
slidePaint(change,dir,H,W,h,w,Kmax,Kmin);
else{
slidePaint(Pos{change.x+dx[dir],change.y},!dir,H,W,h,w,Kmax,Kmin);
}
}
}
}
//入れられるものがあったら貪欲に入れる
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(!isPainted[i][j] && calcFlipDifScore(Pos{i,j},penalty,H,W,h,w)>0 && board[i][j]-'0'>0)
flipPaint(Pos{i,j},H,W,h,w,Kmax,Kmin,board);
}
}
//retを作る
vector<string> ret;
for(int i=0;i<H;i++){
string S;
for(int j=0;j<W;j++){
S+=(isPainted[i][j]?'x':'.');
}
ret.push_back(S);
}
// for(int i=0;i<H;i++){
// for(int j=0;j<W;j++)
// cerr<<ret[i][j]<<" ";
// cerr<<endl;
// }
// cerr<<endl;
// for(int i=0;i<H-h;i++){
// for(int j=0;j<W-w;j++)
// cerr<<numPainted[i][j]<<" ";
// cerr<<endl;
// }
// cerr<<endl;
// for(int i=1;i<=H;i++){
// for(int j=1;j<=W;j++){
// cerr<<longSum[i][j]<<" ";
// }
// cerr<<endl;
// }
// cerr<<endl;
// for(int i=1;i<=H;i++){
// for(int j=1;j<=W;j++){
// cerr<<justMax[i][j]<<" ";
// }
// cerr<<endl;
// }
// cerr<<endl;
// for(int i=0;i<H;i++){
// for(int j=0;j<W;j++)
// cerr<<calcFlipDifScore(Pos{i,j},penalty,H,W,h,w)<<" ";
// cerr<<endl;
// }
// for(int i=0;i<H;i++){
// for(int j=0;j<W;j++)
// cerr<<calcSlideDifScore(Pos{i,j},0,penalty,H,W,h,w,Kmax,Kmin)<<" ";
// cerr<<endl;
// }
cerr<<iteration<<endl;
//validAnsとスコアを比べて、大きい方を出力
int myScore=0,validScore=0;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(isPainted[i][j])
myScore+=board[i][j]-'0';
if(validAns[i][j]=='x')
validScore+=board[i][j]-'0';
}
}
//解がvalidかどうか確認する
for(int i=0;i<H-h+1;i++){
for(int j=0;j<W-w+1;j++){
if(numPainted[i][j]<Kmin || Kmax<numPainted[i][j]){
if(validScore>maxScore)
return validAns;
else
return maxAns;
}
}
}
cerr<<myScore<<" "<<validScore<<" "<<maxScore<<endl;
if(myScore<maxScore){
myScore=maxScore;
ret=maxAns;
}
if(myScore<validScore)
return validAns;
cerr<<"!"<<endl;
return ret;
}
};
// -------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() {
PointsOnGrid pog;
int H;
int W;
int h;
int w;
int Kmin;
int Kmax;
int size;
cin >> H;
cin >> W;
cin >> h;
cin >> w;
cin >> Kmin;
cin >> Kmax;
cin >> size;
vector<string> grid(size);
getVector(grid);
vector<string> ret = pog.findSolution(H,W,h,w,Kmin,Kmax,grid);
cout << ret.size() << endl;
for (int i = 0; i < (int)ret.size(); ++i)
cout << ret[i] << endl;
cout.flush();
}
戻る