JMK no matter what

어제 못푼 그문제.

어제 코딩하다가 너무 졸려서 잠들고, 아침에 침대에서 비몽사몽간에 일어나서 컴퓨터 앞으로 기어와 간신히 풀었음. N 이 작았으면 사용했을 O(2^N * N^2) 어프로치를 최적화해서 푸는 것이 포인트.. 였는데, 아레나에서 1.93초 나오네... 역시 인생은 아슬아슬한 게 맛이라능.. -_ -;; 가능한한 모든 것을 Precalc 했다. 가능한한 메인 루프에 들어가는 내용을 줄이는 것이 포인트. unsigned 를 써서 -1 과 INF 를 같이 쓰는 전법; 을 사용해 보았는데 생각보다 쉽게 되더라는.. 눈물의 소스 코드

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
const int INF = 987654321;

int mask2Id[1<<22];
int nextId[29000][22][5], nextX[29000][22][5];
unsigned cache[2][23][29000];

struct BrickPuzzle 
{
    int h, w;
    VI id2Mask, firstZero;
    vector<pair<int,int> >  blocks[5];
    void genMask(int curmask, int x)
    {
        if(x == w) id2Mask.pb(curmask);
        if(x + 2 <= w) genMask(curmask + (3<<x), x+2);
        if(x + 1 <= w) genMask(curmask, x+1);
    }
    bool hasBit(int a, int b) { return a & (1<<b); }
    inline int full(int width) { return (1 << width) - 1; }
    string bin(int mask)
    {
        string ret(w, '0');
        REP(i,w) if(mask&(1<<i)) ret[i] = '1';
        return ret;
    }
    void genAction()
    {
        REP(id,id2Mask.sz)
        {
            int mask = id2Mask[id];
            REP(x,w)
            {
                const int M = full(x+1);
                int topMask = mask & ~M;
                int botMask = mask & M;
                if(mask2Id[topMask] == -1 || mask2Id[botMask] == -1) continue; // nonsense..
                assert((topMask & (1<<x)) == 0);
                REP(act,5)
                {
                    int row[2] = { topMask, botMask };
                    bool ok = true;
                    REP(i,blocks[act].sz)
                    {
                        const int ny = blocks[act][i].first;
                        const int nx = x + blocks[act][i].second;
                        if(nx < 0 || nx >= w || hasBit(row[ny], nx)) { ok = false; break; }
                        row[ny] += (1<<nx);
                    }                    
                    if(!ok) continue;
                    int nX = x+1;
                    while(nX < w && hasBit(row[0], nX)) ++nX;
                    const int M2 = full(nX+1);
                    int nextState = (row[0] & ~M2) | (row[1] & M2);
                    assert(nX != w || row[1] == nextState);
                    assert(mask2Id[nextState] != -1);
                    nextId[id][x][act] = mask2Id[nextState];
                    nextX[id][x][act] = nX;
                }
            }
        }
    }

    inline void update(unsigned& a, unsigned b)
    {
        a = min(a, b);
    }

    int leastShapes(vector <string> board) 
    {
        CLEAR(mask2Id,-1);
        blocks[1].pb(make_pair(0,0)); blocks[1].pb(make_pair(0,1)); blocks[1].pb(make_pair(1,0)); blocks[1].pb(make_pair(1,1)); 
        blocks[2].pb(make_pair(0,0)); blocks[2].pb(make_pair(0,1)); blocks[2].pb(make_pair(1,-1)); blocks[2].pb(make_pair(1,0)); 
        blocks[3].pb(make_pair(0,0)); blocks[3].pb(make_pair(0,1)); blocks[3].pb(make_pair(1,1)); blocks[3].pb(make_pair(1,2)); 
        blocks[4].pb(make_pair(0,0)); blocks[4].pb(make_pair(0,1)); blocks[4].pb(make_pair(0,2)); blocks[4].pb(make_pair(0,3)); 
        h = board.sz; w = board[0].sz;
        bool cover[50][50];
        CLEAR(cover,0);
        REP(i,h) REP(j,w) if(board[i][j] == '.') cover[i][j] = true;
        genMask(0, 0);
        sort(all(id2Mask));
        firstZero.resize(id2Mask.sz);
        REP(i,id2Mask.sz) 
        {
            mask2Id[id2Mask[i]] = i;
            firstZero[i] = w;
            REP(j,w) if(!hasBit(id2Mask[i], j)) 
            {
                firstZero[i] = j;
                break;
            }
        }
        CLEAR(nextId,-1);
        genAction();
        CLEAR(cache,-1);
        cache[0][0][0] = 0;
        REP(y,h) 
        {
            REP(x,w) REP(id,id2Mask.sz) 
            {
                if(cache[y%2][x][id] == -1) continue;
                REP(a,5)
                {
                    if(cover[y][x] && a == 0) continue;
                    if(nextId[id][x][a] == -1) continue;
                    int nId = nextId[id][x][a];
                    int nX = nextX[id][x][a];
                    update(cache[y%2][nX][nId], cache[y%2][x][id] + (a ? 1 : 0));
                }
            }
            CLEAR(cache[(y+1)%2],-1);
            REP(id,id2Mask.sz)
                if(cache[y%2][w][id] != -1)
                {
                    int fz = firstZero[id];
                    const int M = full(fz + 1);
                    update(cache[(y+1)%2][fz][mask2Id[id2Mask[id] & ~M]], cache[y%2][w][id]);
                }
        }
        return int(cache[(h-1)%2][w][0]);
    }
};