JMK no matter what

안드로.txt

250 을 쉽게 푼건 좋았는데, 500 에서 사상 최대의 삽질 시나리오.

• string 출력이라, 답의 범위는 long long 이지만 bigint 인 줄 알았다.
• 존내 고생해서 bigint 로 O(lgT * n^2) 솔루션을 짬.
• 문제 잘못 읽음. matrix 고쳐서 walkaround 만듬.
• 너무 느리다.
• 존내 최적화.
• long long 인걸 커피가 가르쳐줌 => long long 으로 변경
• 틀림.
• 1에서 1로 가는 사이클 길이가 음수일 때도 그냥 끝내는 게 나을 수 있다는 점을 신경 못썼음.

.. 뭐 이런 시나리오. 1k 는 일단 어떻게 푸는지 감도 안오고.. 소스코드가 맘에 안들어서 다시 매크로를 쓰지 말까 하는 생각을 하고 있음.

250 CubeWalking

알고 보면 Cube 는 존재하지 않는다 (?)

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 dx[4] = { 0, 1, 0, -1 };
const int dy[4] = { 1, 0, -1, 0 };

struct CubeWalking 
{
    string finalPosition( string movement ) 
    {
        int y = 3001, x = 3001, d = 0;
        REP(i,movement.sz)
        {
            if(movement[i] == 'L') d = (d+1)%4;
            if(movement[i] == 'R') d = (d+3)%4;
            if(movement[i] == 'W') { y += dy[d]; x += dx[d]; }
        }
        if(y % 3 == 1 && x % 3 == 1) return "GREEN";
        if(fabs(y % 3 - x % 3) == 1) return "BLUE";
        return "RED";
    }
};

500 AntOnGraph; /matrix/divideandconquer

다시 짠 버전.

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 long long ll;
typedef vector<ll> Row;
typedef vector<Row> Matrix;

struct AntOnGraph 
{
    int n;
    Matrix graph;
    Matrix mix(const Matrix& a, const Matrix& b)
    {
        Matrix c(n, Row(n, -1));
        REP(k,n) 
            REP(i,n) 
                if(a[i][k] != -1)
                    REP(j,n)
                        if(b[k][j] != -1)
                            c[i][j] = max(c[i][j], a[i][k] + b[k][j]);

        return c;
    }
    Matrix pow(const Matrix& unit, int t)
    {
        if(t == 1) return unit;
        if(t % 2) return mix(pow(unit, t-1), unit);
        Matrix half = pow(unit, t/2);
        return mix(half, half);
    }
    string maximumBonus( vector <string> p0, vector <string> p1, vector <string> p2, int stepsPerSecond, int timeLimit ) 
    {
        n = p0.sz;
        graph.assign(n, Row(n, -1));
        REP(i,n) REP(j,n)
        {
            string s;
            s += p0[i][j];
            s += p1[i][j];
            s += p2[i][j];

            int w = atoi(s.c_str());
            if(w > 0) graph[i][j] = w;
        }

        Matrix perSecond = pow(graph, stepsPerSecond);
        perSecond[1][1] = max<ll>(perSecond[1][1], 500LL * stepsPerSecond);

        Matrix allTime = pow(perSecond, timeLimit);
        printf("allTime %Ld\n", allTime[0][1]);
        if(allTime[0][1] < 0) return "IMPOSSIBLE";

        ll res = allTime[0][1] - stepsPerSecond * 500LL * timeLimit;
        char buf[128];
        sprintf(buf, "%Ld", res);
        return buf;
    }
};

처음에 짠.... ㅠㅠ

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;
typedef vector<ll> VL;
typedef vector<VL> VVL;

struct AntOnGraph 
{
    int n;
    VVI edges;
    VVL u;

    void add(const VVL& a, const VVL& b, VVL& ret)
    {
        ret.assign(n, VL(n, -1));
        REP(k,n) REP(i,n) if(a[i][k] != -1) REP(j,n) if(b[k][j] != -1)
            ret[i][j] = max(ret[i][j], a[i][k] + b[k][j]);
    }
    void go(int t, VVL& ret)
    {
        printf("call %d\n", t);
        fflush(stdout);
        if(t == 1) ret = u;
        else if(t % 2) 
        {
            VVL tmp;
            go(t-1, tmp);
            add(tmp, u, ret);
        }
        else
        {
            VVL half;
            go(t/2, half);
            add(half, half, ret);
        }
        printf("returning t %d\n", t);
        fflush(stdout);
//        printf("t = %d\n", t);        REP(i,n) { REP(j,n) printf("%10s", ret[i][j].c_str()); printf("\n"); }
    }

    string maximumBonus( vector <string> p0, vector <string> p1, vector <string> p2, int stepsPerSecond, int timeLimit ) 
    {
        n = p0.sz;
        edges.assign(n, VI(n, 0));
        REP(i,n) REP(j,n)
        {
            string s;
            s += p0[i][j];
            s += p1[i][j];
            s += p2[i][j];
            edges[i][j] = atoi(s.c_str());
        }
        //edges[1][1] = 500; // there is a zero-length edge from 1 to 1
        VVL unit(n, VL(n, -1));
        REP(i,n) unit[i][i] = 0;
        REP(i,stepsPerSecond)
        {
            VVL next(n, VL(n, -1));
            REP(a,n) REP(b,n) 
                if(unit[a][b] != -1)
                    REP(c,n)
                        if(edges[b][c] != 0)
                        {
                            int cand = unit[a][b] + edges[b][c];
                            if(next[a][c] == -1 || next[a][c] < cand)
                                next[a][c] = cand;
                        }
            unit = next;
        }

        u = unit;
        u[1][1] = max<ll>(u[1][1], 500 * stepsPerSecond);
//        if(u[1][1] == -1) u[1][1] = 500 * stepsPerSecond;
        REP(i,n) { REP(j,n) printf("[%10Ld]", u[i][j]); printf("\n"); }
        printf("wow\n");
        fflush(stdout);
        VVL ret;
        go(timeLimit, ret);
        ll sol = ret[0][1];
        if(sol == -1) return "IMPOSSIBLE";
        sol -= ll(timeLimit) * ll(stepsPerSecond) * 500;
        char buf[128];
        sprintf(buf, "%Ld", sol);
        return buf;
    }
};

이건 뭐 코드도 아니고