Marathon Match 65: Cutting Figures

TopCoder

今回はリアルタイムで書き置きしておくことにする。

問題の把握と方針決め

  • 問題文を読んでみる。今回決定するのは「acceptするかrejectするかの判定」、「どの位置を切り取るかの判定」の2種類。
  • 値段の幅が1~100となっているので、重要なのは明らかに前者の方。101~200とかなら話は別だけど。
  • MM64 StreetSalesと同じく相対評価なので、小さいケースで手を抜かずにハイスコアを狙う必要がある。
  • 細かい実装は後にして、accept or rejectの判定について考える。これが最重要なので安易にヒューリスティックに逃げてはいけない。

実装以前

  • 値段の分布が一様であることを確認。
  • 確率の問題。[0,100]の一様乱数をn個抽出したとき、大きい方m個の合計の期待値E(n,m)は？
  • 答えはE(n,m)=100*(n + (n-1) + (n-2) + … + (n-m+1))/(n+1)。
  • したがって、残りオーダー数n, 残り作れそうな個数mとして、E(n-1,m-1)+incomeとE(n-1,m)を比較してacceptするかrejectするか決めれば良い。
  • 本当はm-1とするのは不適当だけど、これを正確に出そうとすると計算時間が大変な事になる。
  • この評価の良いところは価格の低い依頼を定数時間でバッサリrejectできること。注文数が多いので半分以上の依頼を無視できるのは嬉しい。
  • どの位置を切り取るべきかは取りあえず全探索してみる。時間が足りなそうなら局所探索も考えよう。
  • 評価関数は隣接している使用済のセルの個数でいいだろう。重複してカウントしても何らかの重みは必要なので別に問題なさそう。
  • 合宿が終わった段階でstandingを見ると上位が団子状態。細かい部分の勝負になりそうな感じがしてちょっと怖い。

実装段階

  • 何はともあれpositive scoreを目指す。
  • 様々な補正項を無視したプログラムを書いて1st submit。70点位。こんな適当なのでそんなに取れるのか…。
  • できるだけ、「ぴったりはまった」ものを選ぶことにする。85点位。伸びるものだなぁ。
  • 毎ターン終了後に残り切り取り可能な枚数を再計算することにする。92点。
  • 期待値を求める関数に入っているバグ(整数の割り算)を取り除く。97.0点。おい…。
  • ぴったりはまっている候補を複数個選び、その中で最もvalidな升を無駄にしないものを選ぶ。
  • 例えばK=5のとき、そこに埋めたら面積4の池が発生するようなominoは評価が低い。これで98.5点。

微調整

  • 探索空間を広げる。98.6点。
  • 残り切り取り可能な枚数の計算をより正確にする。
  • 例えばK=5のとき、面積8の池はomino1つ分としか評価しないようにする。
  • Kが大きいときはぴったりはまる図形が出にくいことを考慮する。
  • 例えばK=10のとき、面積10や11の池の評価は少し低く見積もる。これで98.8点。
  • Kに応じて、「ぴったりはまっている係数」と「升が無駄になる係数」の重み付けを変える。98.92点。
  • この辺りでは2位で上位と0.1点差なので何とかなると思っていた。
  • 残り切り取り枚数の計算を毎回全升に対して行うのではなく、新しく切り取った箇所の周囲でのみ行うようにする。点数ガタ落ち(97点前半)。
  • 実行時間が結構厳しいので高速化を図る。bfsをdfsに書き換えたりsetをpriority_queueに変えたり残り切り取り枚数の計算で枝刈りしたりで実行時間を75%位に縮められた。
  • スクリプトを書いてパラメータ(重み、探索回数の上限)の探索を多少楽にする。大部分は手動だけど。
  • 上以外のパラメータはいじっても中々良くならなかった。
  • 探索の末点数が上がる。98.94点。相対評価でトップ陣の点数が上がっているので前回の98点より価値がある。
  • パラメータの改善は時間もかかって面倒で、上がり幅も小さいけど下がることが少ないので精神的には楽。
  • 実装重いくせに得点が上がるかどうか分からないのは少し気分が沈む。
  • 実装重いのは消すのが勿体なくて得点下がってもちょっと執着してしまう。
  • visualizerで眺めると、小さいケースで無駄が多いけどそれは仕方ないことなのかもしれない。相対評価でスコアの絶対値が小さいので正確にできたら大きな武器になるはず。

終戦

  • 色々あってこの後は何も手を加えることなく終戦を迎えた。
  • 評価関数とか適当だったしいじりようはあったと思うけど、あらゆることに対してモチベーションを失っていた時期がありまして。
  • Visualizerのソース見て入力データの解析しようと思っていた時期はあった。
  • コンテストの最終4日目位から赤い人が参加して上位を争っていた。
  • 暫定順位は6/161。上下の人とは結構得点が離れているのでこのままの位置で終わりそう。終わってくれたらいいなあ。
  • ソースに実験中だった色々なのがついていて汚い。

反省(10/3追記)

  • 最終的な順位は一つ下がって7位/161。レーティングも1900台に乗っかった。
  • detailを見たところ、小さいケースで弱かったのは確かだけど意外と大きなケースでもそんなに稼げていなかった。
  • 一番力を入れたはずの評価関数が実は甘かった？
  • 10以下のominoは高々4桁しかないから埋め込みを考えてみるべきだったかもしれない。
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std;

#define MaxPrice 100

#define DBG 0
#define PROCESS 0
#define INFO 0
#define ANALYZE 1


class CuttingFigures{
public:
vector<bool> plate, plateBackUp;
vector<int> plateTmp;
int resOrder, resCut, acceptCnt;
int plateWidth, plateHeight, plateCells;
int figureWidth, figureHeight;
int retValue;
int rotate, reflect;
int K;
int freeCell, squareCnt, removeSquare;
vector<int> figureIndex, figureIndexBase;
int dx[4], dy[4];
int totalEarn;
vector<int> ToDel;
int revise;
double weight;
bool checkFill, toCheck;
int memorySize;

int init(vector<string> plateIn, int Kin, int orderCntIn){
    resOrder = orderCntIn + 1;
    acceptCnt = totalEarn = 0;
    K = Kin;
    dy[0] = dy[1] = dx[2] = dx[3] = 0;
    dy[2] = dx[0] = 1;
    dy[3] = dx[1] = -1;
    freeCell = 0;
    figureIndex = vector<int>(K);
    figureIndexBase = vector<int>(K);
    plateHeight = plateIn.size();
    plateWidth  = plateIn[0].size();
    plateCells = plateWidth*plateHeight;
    plate = vector<bool>(plateCells);
    plateTmp = vector<int>(plateCells);
    checkFill = true;
    weight = decideWeight();
    decideMemorySize();
    for(int i=0; i<plateHeight; i++)
        for(int j=0; j<plateWidth; j++){
            plate[i*plateWidth+j] = plateIn[i][j]=='.';
        }
    markMiniSquare();
    freeCell = countFreeCell();
    resCut = freeCell / K;

if(INFO){ cerr << "plateCells: " << plateCells << endl; cerr << "ominoNum: " << K << endl;
    cerr << "orderCnt: " << orderCntIn + 1 << endl;
    cerr << "resCut: " << resCut << endl;
    cerr << "expect: " << calcExp(orderCntIn, resCut) << endl;
    cerr << "memory: " << memorySize << endl;
}
    return 0;
}

inline double decideWeight(){
    if(K==3){
        return 5.0;
    }
    else if(K==4){
        return 4.0;
    }
    else if(K==5){
        return 3.0;
    }
    else if(K==6){
        return 2.3;
    }
    else if(K==7){
        return 1.7;
    }
    else if(K==8){
        return 1.3;
    }
    else if(K==9){
        return 1.05;
    }
    else if(K==10){
        return 0.62;
    }
    return 1.0;
}

inline void decideMemorySize(){
    if(plateCells < 500)  memorySize = 1500;
    if(plateCells < 1000) memorySize = 1000;
    else if(plateCells < 1500) memorySize = 1000;
    else if(plateCells < 2000) memorySize = 400;
    else if(plateCells < 2500) memorySize = 200;
    else if(plateCells < 3000) memorySize = 150;
    else if(plateCells < 3500) memorySize = 100;
    else if(plateCells < 4000) memorySize = 50;
    else if(plateCells < 4500) memorySize = (K<=4)?35:40;
    else if(plateCells < 5000) memorySize = (K<=4)?20:25;
    else if(plateCells < 5500) memorySize = (K<=4)?15:20;
    else if(plateCells < 6000) memorySize = (K<=4)?10:15;
    else if(plateCells < 7000) memorySize = (K<=4)?7:10;
    else if(plateCells < 7500) memorySize = (K<=4)?4:8;
    else if(plateCells < 8000) memorySize = (K<=4)?3:6;
    else memorySize = (K<=4)?2:4;
}

inline int canMakeFigure(){
    int cnt = 0, ret = 0, filledSquare = 0;
    for(int i=0; i<K; i++){
        if(!plate[figureIndex[i]]) return -1;
        cnt = 0;
        int y = figureIndex[i]/plateWidth,
            x = figureIndex[i]%plateWidth;
        for(int k = 0; k<4; k++){
            int ny = y + dy[k],
                nx = x + dx[k];
            if(0<=ny && ny<plateHeight && 0<=nx && nx<plateWidth){
                if(!plate[ny*plateWidth+nx])
                    cnt++;
            }
            else {
                cnt++;
            }
        }
        ret += cnt;
    }
    return ret;
}

inline void bfs(int y, int x, int to){
    plateTmp[y*plateWidth+x] = to;
    queue<int> Q;
    Q.push(y*plateWidth+x);
    while(!Q.empty()){
        y = Q.front()/plateWidth;
        x = Q.front()%plateWidth;
        Q.pop();
        for(int k=0; k<4; k++){
            int ny = y + dy[k],
                nx = x + dx[k];
            if(0<=ny && ny<plateHeight && 0<=nx && nx<plateWidth && plateTmp[ny*plateWidth+nx] == 1){
                squareCnt++;
                plateTmp[ny*plateWidth+nx] = to;
                Q.push(ny*plateWidth + nx);
            }
        }
    }
    return ;
}

inline void dfs2(int y, int x, int to){
    plateTmp[y*plateWidth+x] = to;
    for(int k=0; k<4; k++){
        int ny = y + dy[k],
            nx = x + dx[k];
        if(0<=ny && ny<plateHeight && 0<=nx && nx<plateWidth && plateTmp[ny*plateWidth+nx] == 1){
            squareCnt++;
            dfs2(ny,nx,to);
        }
    }
    return ;
}

inline void dfs(int y, int x){
    plate[y*plateWidth+x] = false;
    for(int k=0; k<4; k++){
        int ny = y + dy[k],
            nx = x + dx[k];
        if(0<=ny && ny<plateHeight && 0<=nx && nx<plateWidth && plate[ny*plateWidth+nx]){
            dfs(ny, nx);
        }
    }
    return ;
}

inline void markMiniSquare(){
    int cnt = 2;
    for(int p=0; p<plateCells; p++){
        plateTmp[p] = plate[p]?1:0;
    }
    removeSquare = 0;
    for(int i=0; i<plateHeight; i++){
        for(int j=0; j<plateWidth; j++){
            if(plateTmp[i*plateWidth+j] == 1){
                squareCnt = 1;
                dfs2(i,j,cnt);
                if(squareCnt < K){
                    dfs(i,j);
                }
                cnt++;
            }
        }
    }
}

inline void markMiniSquareSub(){
    int cnt = 2;
    int lowerY=1<<20, upperY=0, lowerX=1<<20, upperX=0, width = 2*K + 2;
    for(int i=0; i<K; i++){
        int y = figureIndex[i]/plateWidth,
            x = figureIndex[i]%plateWidth;
        lowerX = min(lowerX, x);
        lowerY = min(lowerY, y);
        upperX = max(upperX, x);
        upperY = max(upperY, y);
    }
    lowerX = max(0, lowerX-width);
    lowerY = max(0, lowerY-width);
    upperX = min(plateWidth, upperX+width);
    upperY = min(plateHeight, upperY+width);
    for(int i=lowerY; i<upperY; i++){
        for(int j=lowerX; j<upperX; j++){
                plateTmp[i*plateWidth+j] = plate[i*plateWidth+j]?1:0;
        }
    }
    if(lowerX > 0)
    for(int i=max(lowerY-1,0); i<min(plateHeight,upperY+1); i++){
        plateTmp[i*plateWidth+lowerX-1] = 0;
    }
    if(upperX < plateWidth-1)
    for(int i=max(lowerY-1,0); i<min(plateHeight,upperY+1); i++){
        plateTmp[i*plateWidth+upperX+1] = 0;
    }
    if(lowerY > 0)
    for(int j=max(lowerX-1,0); j<min(plateWidth,upperX+1); j++){
        plateTmp[(lowerY-1)*plateWidth+j] = 0;
    }
    if(upperY < plateHeight-1)
    for(int j=max(lowerX-1,0); j<min(plateWidth,upperX+1); j++){
        plateTmp[(upperY+1)*plateWidth+j] = 0;
    }

    removeSquare = 0;
    for(int i=0; i<K; i++){
        int y = figureIndex[i]/plateWidth,
            x = figureIndex[i]%plateWidth;
        for(int k=0; k<4; k++){
            int ny = y + dy[k],
                nx = x + dx[k];
            if(0<=ny && ny < plateHeight && 0<=nx && nx<plateWidth && plateTmp[ny*plateWidth+nx] == 1){
                squareCnt = 1;
                dfs2(ny,nx,cnt);
                if(squareCnt < K){
                    removeSquare += squareCnt;
                    dfs(ny,nx);
                }
                else if(squareCnt < 2*K){
                    if(K>8 && squareCnt - K <= 2){
                        removeSquare++;
                    }
                    else if(K>6 && squareCnt - K <= 1){
                        removeSquare++;
                    }
                    removeSquare += (squareCnt - K)/(K-2);
                }
                else if(0 && K<=4 && squareCnt < 3*K){
                    if(squareCnt - 2*K > 0){
                        removeSquare++;
                    }
                }
                cnt++;
            }
        }
    }
}


inline int countFreeCell(){
    int ret = 0, col = 2;
    for(int p=0; p<plateCells; p++) plateTmp[p] = plate[p]?1:0;
    for(int p=0; p<plateWidth*plateHeight; p++){
        if(plateTmp[p]==1){
            squareCnt = 1;
            dfs2(p/plateWidth, p%plateWidth, col);
            col++;
            ret += squareCnt/K;
        }
    }
    return ret*K;
}

inline void cutFigure(){
    for(int i=0; i<K; i++){
        plate[figureIndex[i]] = false;
    }
}

inline double calcExp(int n, int m){
    return (double)(m*((2*n-m+1)*0.5))/(double)(n+1)*MaxPrice;
}

inline int encode(int pos, int rot, int ref){
    return (pos << 10) + (rot << 5) + ref;
}

inline int decode(int enc, int p){
    return (enc >> (5*p)) & ((1<<(p==2?20:5))-1);
}

inline int getRevise(){
    return 0;
    if(K<=4) return 0;
    if(K==5 && resCut < 10) return 1;
    if(K==6 && resCut < 15) return 1;
    if(K==7){
        if(resCut < 10) return 2;
        if(resCut < 25) return 1;
    }
    else if(K==8){
        if(resCut < 15) return 2;
        if(resCut < 30) return 1;
    }
    else if(K==9){
        if(resCut < 10) return 3;
        if(resCut < 20) return 2;
        if(resCut < 35) return 1;
    }
    else if(K==10){
        if(resCut < 15) return 4;
        if(resCut < 25) return 3;
        if(resCut < 35) return 2;
        if(resCut < 45) return 1;
    }

    return 0;
}

vector<int> processOrderSub(vector<string> figure, int income){
    resOrder--;
if(INFO && resOrder == 1){
    cerr << "resCut: " << resCut << endl;
    cerr << "accept: " << acceptCnt << endl;
    cerr << "average: " << totalEarn/acceptCnt << endl;
}

if(PROCESS && resOrder%50==0)cerr<< "resOrder: " << resOrder << ", resCut: " << resCut << ", price: " << calcExp(resOrder-1, resCut) - calcExp(resOrder-1, resCut-1) << endl;
    if(resOrder > resCut + K && calcExp(resOrder-1, resCut) - calcExp(resOrder-1, resCut-1) >= income ){
        return vector<int>();
    }
    figureWidth  = (int)figure[0].size();
    figureHeight = (int)figure.size();
    int pos=0;
    vector<int> figureIndexTmp;
    for(int i=0; i<figureHeight; i++){
        for(int j=0; j<figureWidth; j++)if(figure[i][j]=='X'){
            figureIndexBase[pos++] = i*plateWidth + j;
        }
    }
    int adjBest = -(1<<20);
    for(int rot = 0; rot < 4; rot++){
        for(int ref = 0; ref < 2; ref++){
            for(int i=0; i<plateHeight - figureHeight + 1; i++){
                for(int j=0; j<plateWidth - figureWidth + 1; j++){
                    for(int k=0; k<K; k++){
                        figureIndex[k] = i*plateWidth + j + figureIndexBase[k];
                    }
                    int adj = canMakeFigure();
                    if(adj > adjBest){
                        adjBest = adj;
                        figureIndexTmp = figureIndex;
                        rotate = rot;
                        reflect = ref;
                    }
                }
            }
            for(int i=0; i<K; i++){
                int x = figureIndexBase[i]%plateWidth,
                    y = figureIndexBase[i]/plateWidth;
                figureIndexBase[i] = y*plateWidth + (figureWidth - x - 1);
            }
        }
        for(int i=0; i<K; i++){
            int x = figureIndexBase[i]%plateWidth,
                y = figureIndexBase[i]/plateWidth,
                t = y;
            y = x;
            x = figureHeight - t - 1;
            figureIndexBase[i] = y*plateWidth + x;
        }
        swap(figureWidth, figureHeight);
    }
    if(adjBest >= 0){
        figureIndex = figureIndexTmp;
        cutFigure();
        markMiniSquare();
        freeCell = countFreeCell();
        resCut = freeCell/K;

        vector<int> ret;
        ret.push_back(rotate);
        ret.push_back(0);
        ret.push_back(reflect);
        int ma = 1<<20;
        for(int a=0;a<K;a++)ma = min(figureIndex[a]/plateWidth, ma);
        ret.push_back(ma);
        ma = 1<<20;
        for(int a=0;a<K;a++)ma = min(figureIndex[a]%plateWidth, ma);
        ret.push_back(ma);
        acceptCnt++;
        totalEarn += income;
        return ret;
    }

    return vector<int>();
}

vector<int> processOrder(vector<string> figure, int income){
    if(memorySize == 1) return processOrderSub(figure, income);
    resOrder--;
if(INFO && resOrder == 1){
    cerr << "resCut: " << resCut << endl;
    cerr << "accept: " << acceptCnt << endl;
    cerr << "average: " << totalEarn/acceptCnt << endl;
}

if(PROCESS && resOrder%50==0)cerr<< "resOrder: " << resOrder << ", resCut: " << resCut << ", price: " << calcExp(resOrder-1, resCut) - calcExp(resOrder-1, resCut-1) << endl;
    if(resOrder > resCut + K&& calcExp(resOrder-1, resCut) - calcExp(resOrder-1, resCut-1) >= income + getRevise()){
        return vector<int>();
    }
    figureWidth  = (int)figure[0].size();
    figureHeight = (int)figure.size();
    int pos=0;
    vector<int> figureIndexTmp;
    for(int i=0; i<figureHeight; i++){
        for(int j=0; j<figureWidth; j++)if(figure[i][j]=='X'){
            figureIndexBase[pos++] = i*plateWidth + j;
        }
    }
    vector<int> figureIndexBaseBackUp = figureIndexBase;
    priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > bestPos;
    for(int rot = 0; rot < 4; rot++){
        for(int ref = 0; ref < 2; ref++){
            for(int i=0; i<plateHeight - figureHeight + 1; i++){
                for(int j=0; j<plateWidth - figureWidth + 1; j++){
                    for(int k=0; k<K; k++){
                        figureIndex[k] = i*plateWidth + j + figureIndexBase[k];
                    }
                    int adj = canMakeFigure();
                    if(adj >= 0 && (bestPos.size() < memorySize || adj > bestPos.top().first)){
                        if(bestPos.size() == memorySize) bestPos.pop();
                        bestPos.push(make_pair(adj, encode(i*plateWidth+j, rot, ref)));
                    }
                }
            }
            for(int i=0; i<K; i++){
                int x = figureIndexBase[i]%plateWidth,
                    y = figureIndexBase[i]/plateWidth;
                figureIndexBase[i] = y*plateWidth + (figureWidth - x - 1);
            }
        }
        for(int i=0; i<K; i++){
            int x = figureIndexBase[i]%plateWidth,
                y = figureIndexBase[i]/plateWidth,
                t = y;
            y = x;
            x = figureHeight - t - 1;
            figureIndexBase[i] = y*plateWidth + x;
        }
        swap(figureWidth, figureHeight);
    }
    if(!bestPos.empty()){
        plateBackUp = plate;
        double minRem = -(1<<20);
        while(!bestPos.empty()){
            pair<int,int> tp = bestPos.top(); bestPos.pop();
            plate = plateBackUp;
            figureIndexBase = figureIndexBaseBackUp;
            int enc = tp.second, rot = decode(enc,1), ref=decode(enc,0), p = decode(enc,2);
            for(int r=0; r<rot; r++){
                for(int i=0; i<K; i++){
                    int x = figureIndexBase[i]%plateWidth,
                        y = figureIndexBase[i]/plateWidth,
                        t = y;
                    y = x;
                    x = figureHeight - t - 1;
                    figureIndexBase[i] = y*plateWidth + x;
                }
                swap(figureWidth, figureHeight);
            }
            if(ref){
                for(int i=0; i<K; i++){
                    int x = figureIndexBase[i]%plateWidth,
                        y = figureIndexBase[i]/plateWidth;
                    figureIndexBase[i] = y*plateWidth + (figureWidth - x - 1);
                }
            }
            if(rot&1) swap(figureWidth, figureHeight);
            for(int k=0; k<K; k++){
                figureIndex[k] = p + figureIndexBase[k];
            }
            cutFigure();
            markMiniSquareSub();
            double eval = (tp.first) - weight*removeSquare;
            if(eval > minRem){
                minRem = eval;
                figureIndexTmp = figureIndex;
                rotate = rot;
                reflect = ref;
            }
        }
        plate = plateBackUp;
        figureIndex = figureIndexTmp;
        cutFigure();
        markMiniSquare();
        freeCell = countFreeCell();
        resCut = freeCell/K;
        vector<int> ret;
        ret.push_back(rotate);
        ret.push_back(0);
        ret.push_back(reflect);
        int ma = 1<<20;
        for(int a=0;a<K;a++)ma = min(figureIndex[a]/plateWidth, ma);
        ret.push_back(ma);
        ma = 1<<20;
        for(int a=0;a<K;a++)ma = min(figureIndex[a]%plateWidth, ma);
        ret.push_back(ma);
        acceptCnt++;
        totalEarn += income;
        return ret;
    }

    return vector<int>();
}

};