JMK no matter what

일루옹이 타겟이 된 전설의 매치. 과거로 쭉 거슬러 올라가면서 연습하기로 맘먹고 돌아보았다. 간단한 250, 꽤나 복잡한 DP 500, 그리고 안드로메다 1000 의 구성. 1000 은 이렇게 저렇게 짜 봤는데 잘 안나온다. -_ - 모든 valid 한 비트마스크의 수가 피보나치 수열이라는 점을 이용하면 O(fib(w)wh) 에 동적 계획법을 할 수 있다는 요지인데.. 구현 디테일을 잘 모르겠음. ;;; 250 500 둘다 헤맸고, 500 에서는 이분검색에서 boundary 값 잘못 지정하는 거랑 함수 입력 정의 boundary 값 헷갈려서 틀림.

250 MagicalSource

시뮬레이션하려고 한참 폼잡고 있다가 그냥 풀은.. OTL

lang:cpp
struct MagicalSource {
    long long calculate( long long x ) {
        long long t = 1;
        while(t*10+1 <= x) t = t*10+1;
        while(x%t) t /= 10;
        return x/t;
    }
};

500 BaronsAndCoins

캡 복잡하게 짰다. -.-;; O(nn10000) 과 O(n*n) 의 두 가지 어프로치가 있는 것 같은데, 나는 후자로 짰음.

lang:cpp
const int INF = 987654321;
struct BaronsAndCoins {
    vector<pair<int,int> > coin;
    int cache[100][100];
    int sigma(int a, int b)
    {
        return b*(b+1)/2 - a*(a-1)/2;
    }
    int go(int last, int taken)
    {
        int& ret = cache[last][taken];
        if(ret != -1) return ret;
        ret = INF;
        if(taken == 1) return ret; // oops
        int track = -1;
        REP(before,last)
        {
            int ydiff = coin[last].first - coin[before].first;
            int xdiff = coin[last].second - coin[before].second;
            int minMoveSize = go(before, taken-1);
            if(minMoveSize == INF) continue;
            ++minMoveSize;
//            if(ydiff > 0 && xdiff >= minMove(minMoveSize, ydiff))
            if(ydiff > 0 && xdiff >= sigma(minMoveSize, minMoveSize + ydiff - 1))
            {
                // it's impossible to end at lo, possible to end at hi
                int lo = 0;
                int hi = xdiff;
                while(lo+1 < hi)
                {
                    int mid = (lo + hi) / 2;
                    if(xdiff <= sigma(mid - ydiff + 1, mid))
                        hi = mid;
                    else
                        lo = mid;
                }
                if(ret > hi) track = before;
                ret = min(ret, hi);
            }
        }
        //if(ret != INF)
        //printf("arrive at %d, catching %d => min move is %d from %d\n", last, taken, ret, track);

        return ret;
    }
    int getMaximum( vector <int> x, vector <int> y ) {
        CLEAR(cache,-1);
        coin.pb(make_pair(0, 0));
        REP(i,x.sz) coin.pb(make_pair(y[i], x[i]));
        cache[0][1] = 0;
        sort(all(coin));
        for(int amt = coin.sz; amt >= 1; --amt)
            REP(end,coin.sz) 
                if(go(end, amt) < INF) 
                    return amt-1;
        // oops
        return -1;
    }
};

1000 BrickPuzzle

모든 블럭이 두줄이라던가 이런 트리비얼한 것은 쉬운데.. 구현에서 약한 건가 ;ㅁ;