JMK no matter what

간단 기하 + 트리 250 에 (포함관계는 트리 모델링의 아주 좋은 사례) 어려운 상태공간 탐색 600, 그리고 matrix exponentiation 1000. 600 을 bidirectional search 로 풀었다가 TLE 나는거 확인하고 그냥 1000 으로 넘어감. 1k 는 알고리즘은 맞았는데, implementation level detail 때문에 TLE 나주심. 이거 최적화하려고 졸랭 삽질했는데... ㅠㅠ 답은 둘 중 하나인 듯:

• matrix exponentiation 할 때 각 단계들을 미리 캐싱해 둔다.
• sum of powers 패턴을 쓰지 말고, powers includes accumulation (이거 풀어 쓰자면 너무 어려워서 대충 -_-) 전략을 쓴다.

여튼 첫번째로 바꿔서 냈는데, 시스테스트는 여전히 TLE. 근데 웃긴게, 하나씩 돌려보면 다 1초 안에 나온다. 뭔가 잘못됐나. -_-

250 CirclesCountry

원들의 포함관계를 트리로 모델링하면 트리에서의 LCA 문제가 된다.

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;

struct CirclesCountry
{
    int n;
    VI x, y, r, p;
    int sqr(int x) { return x*x; }
    bool encloses(int a, int b)
    {
        return r[a] > r[b] && sqr(x[a]-x[b]) + sqr(y[a]-y[b]) < sqr(r[a]-r[b]);
    }
    bool included(int a, int y_, int x_)
    {
        return sqr(y[a] - y_) + sqr(x[a] - x_) < sqr(r[a]);
    }
    void build(int here)
    {
        vector<int> included;
        REP(i,n) if(p[i] == -1 && encloses(here, i)) included.pb(i);
        vector<bool> nextLevel(included.sz, true);
        REP(i,included.sz) REP(j,included.sz) if(encloses(included[i], included[j])) nextLevel[j] = false;
        REP(i,included.sz) if(nextLevel[i]) p[included[i]] = here;
        REP(i,included.sz) if(nextLevel[i]) build(included[i]);
    }
    int find(int here, int y, int x)
    {
        REP(i,n) if(p[i] == here && included(i, y, x)) return find(i, y, x);
        return here;
    }
    int leastBorders( vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2 )
    {
        x = X; y = Y; r = R;
        x.pb(0); y.pb(0); r.pb(20000);
        n = x.sz;
        p.assign(n, -1);
        build(n-1);
        REP(i,p.sz) printf("%d: x %d y %d r %d, p %d\n", i, x[i], y[i], r[i], p[i]);
        int a = find(n-1, y1, x1);
        VI c(n, -1);
        int dist = 0;
        while(a != -1)
        {
            c[a] = dist++;
            a = p[a];
        }
        int b = find(n-1, y2, x2);
        dist = 0;
        while(c[b] == -1)
        {
            ++dist;
            b = p[b];
        }
        return c[b] + dist;
    }
};

600 BinaryFlips /hard/again/analytic

실제로는 좀더 analytic 한 접근이 필요하다. Fenwick Tree 쓴 사람도 있다고 함.

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;


struct BinaryFlips
{
    VI c;
    int sgn(int x) { if(x > 0) return 1; if(x < 0) return -1; assert(0); return 0; }
    int minimalMoves( int A, int B, int K )
    {
        if(A == 0) return 0;

        int T = A+B;
        c.assign(T+1, 0);
        c[A] = 1;
        c[0] = -1;
        queue<int> q;
        q.push(A);
        q.push(0);
        while(!q.empty())
        {
            int zeros = q.front(); q.pop();
//            printf("popped %d\n", zeros);
            for(int zto = max(0, K+zeros-T); zto <= min(K, zeros); ++zto)
            {
                int otz = K - zto;
                int next = zeros - zto + otz;
                if(c[next] != 0)
                {
                    if(sgn(c[next]) != sgn(c[zeros]))
                        return abs(c[next]) + abs(c[zeros]) + 1 - 2;
                    continue;
                }
                c[next] = c[zeros] + sgn(c[zeros]);
//                printf("\totz = %d, c[%d] = %d\n", otz, next, c[next]);
                q.push(next);
            }
        }
        return -1; // oops
    }
};

1000 ShuffledPlaylist

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 int ll;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll M = 600921647;

VVI operator + (const VVI& a, const VVI& b)
{
    int n = a.sz;
    VVI ret(n, VI(n, 0));
    REP(i,n) REP(j,n) ret[i][j] = (a[i][j] + b[i][j]) % M;
    return ret;
}
VVI operator * (const VVI& a, const VVI& b)
{
    int n = a.sz;
    VVI ret(n, VI(n, 0));
    REP(i,n) REP(j,n) REP(k,n) (ret[i][j] += ((a[i][k] * (long long)b[k][j]) % M)) %= M;
    return ret;
}

VVI cache[30];
VVI pow(int N)
{
    const int n = cache[0].sz;
    VVI ret(n, VI(n, 0));
    REP(i,n) ret[i][i] = 1;
    REP(i,30) if(N & (1<<i)) ret = ret * cache[i];
    return ret;
}

// unit + unit**2 + .. + unit**N
VVI powsum(int N)
{
    assert(N);
    if(N == 1) return cache[0];
    if(N % 2) return pow(N) + powsum(N-1);
    VVI half = powsum(N/2);
    return half + (half * pow(N/2));
}

VVI powsum(int A, int B)
{
    int N = B - A + 1;
    VVI a = powsum(N);
    return a * pow(A-1);
}

struct ShuffledPlaylist
{
    int genres;
    ll calc(const VVI& arr)
    {
        ll ret = 0;
        for(int eg = 0; eg < genres; ++eg)
            (ret += arr[eg*9][(genres-1)*9]) %= M;
        return ret;
    }
    int count( vector <string> songs, vector <string> tran, int minLength, int maxLength )
    {
        REP(i,tran.sz) tran[i] += 'N';
        tran.pb(string(tran.sz, 'Y') + 'N');
        REP(i,tran.sz) printf("%s\n", tran[i].c_str());
        genres = tran.sz;
        string s = accumulate(all(songs), string());
        replace(all(s), ',', ' ');
        VVI cnt(genres, VI(10, 0));
        int a, b;
        istringstream inp(s);
        while(inp >> a >> b) { cnt[a][b]++; }
        int N = 9*genres;
        VVI unit(N, VI(N));
        REP(igenre,genres)
            REP(imins,9)
            {
                int i = igenre * 9 + imins;
                // finished before imins minutes ago
                if(imins > 0)
                {
                    unit[i][i-1] = 1;
                    //printf("WAIT: genre %d, mins %d += %d * genre %d, mins %d\n", igenre, imins, 1, igenre, imins-1);
                }
                else
                {
                    // play a song
                    REP(jgenre,genres) if(tran[jgenre][igenre] == 'Y')
                        FOR(len,1,10)
                        {
                            if(cnt[igenre][len])
                            {
                                unit[i][jgenre*9+len-1] += cnt[igenre][len];
                                //printf("PLAY: genre %d, mins %d += %Ld * genre %d, mins %d\n", igenre, imins, cnt[igenre][len], jgenre, len-1);
                            }
                        }
                }
            }
        cache[0] = unit;
        FOR(i,1,30) cache[i] = cache[i-1] * cache[i-1];
        if(minLength == 1)
            return calc(powsum(maxLength));
        return calc(powsum(minLength, maxLength));
    }
};