2015 TopCoder Open Marathon - Round 2

PathDefense.cpp

//  http://community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=48152&rd=16471

#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <cctype>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <ctime>
#include <set>
#ifndef TOPCODER_LOCAL
#include <sys/time.h>
#endif

using namespace std;

double time()
{
#ifdef TOPCODER_LOCAL
    return double(clock())/CLOCKS_PER_SEC;
#else
    static bool init = false;
    static timeval start;
    if (!init)
    {
        init = true;
        gettimeofday(&start, nullptr);
    }
    timeval t;
    gettimeofday(&t, nullptr);
    return (t.tv_sec*1000000+t.tv_usec
        - (start.tv_sec*1000000+start.tv_usec))*1e-6;   
#endif
}

class PathDefense
{
public:
    int init(vector<string> board, int money, int creepHealth, int creepMoney,
        vector<int> towerTypes);
    vector<int> placeTowers(vector<int> creep, int money,
        vector<int> baseHealth);

private:
    struct TowerType
    {
        int range;
        int attack;
        int cost;

        int used;
        TowerType() {}
        TowerType(int range, int attack, int cost)
            : range(range), attack(attack), cost(cost), used(0) {}
    };

    struct Creep
    {
        int id;
        int health;
        int x;
        int y;
        Creep() {}
        Creep(int id, int health, int x, int y)
            : id(id), health(health), x(x), y(y) {}
    };

    struct Tower
    {
        int x;
        int y;
        int type;
        Tower() {}
        Tower(int x, int y, int type): x(x), y(y), type(type) {}
    };

    class Random
    {
        unsigned long long x;
    public:
        Random(): x(88172645463325252ULL) {}
        int rand()
        {
            x ^= x<<13;
            x ^= x>>7;
            x ^= x<<17;
            return int(x&0x7fffffff);
        }
    };

    const static int dx[4];
    const static int dy[4];

    vector<string> board;
    int W;
    int H;
    int creepHealth;
    int creepMoney;
    vector<TowerType> towerType;
    vector<vector<int>> path;
    vector<int> edgeX;
    vector<int> edgeY;
    int step;
    vector<Tower> tower;
    double elapsedTime;
    set<int> creepId;
    vector<int> simCount;

    vector<Tower> placeTowers(vector<Creep> creep, int money,
        vector<int> baseHealth);
    void guessPath();
    int simulate(vector<Creep> creep, int money, vector<int> baseHealth,
        vector<Tower> tower);
    int dist(int x1, int y1, int x2, int y2);
};

int PathDefense::init(vector<string> board, int money, int creepHealth,
    int creepMoney, vector<int> towerTypes)
{
    double start = time();

    this->board = board;
    W = (int)board[0].size();
    H = (int)board.size();
    this->creepHealth = creepHealth;
    this->creepMoney = creepMoney;
    for (int i=0; i<(int)towerTypes.size(); i+=3)
        towerType.push_back(
            TowerType(towerTypes[i], towerTypes[i+1], towerTypes[i+2]));
    guessPath();
    step = 0;
    elapsedTime = time() - start;

#ifdef TOPCODER_LOCAL
    //cerr<<"creepHealth: "<<creepHealth<<endl;
    //cerr<<"creeMoney: "<<creepMoney<<endl;
    //cerr<<"Tower type: "<<towerType.size()<<endl;
    //for (TowerType &t: towerType)
    //  cerr<<"  "<<t.range<<" "<<t.attack<<" "<<t.cost<<endl;
    //cerr<<"board:"<<endl;
    //for (string b: board)
    //  cerr<<b<<endl;
    //cerr<<"path:"<<endl;
    //for (int y=0; y<H; y++)
    //{
    //  for (int x=0; x<W; x++)
    //      if (path[y][x]==0)
    //          cerr<<" ";
    //      else if (path[y][x]<=9)
    //          cerr<<char('0'+path[y][x]);
    //      else
    //          cerr<<char('a'+path[y][x]-10);
    //  cerr<<endl;
    //}
#endif

    return 0;
}

vector<int> PathDefense::placeTowers(vector<int> creep, int money,
    vector<int> baseHealth)
{
    double start = time();

    vector<Creep> c;
    for (int i=0; i<(int)creep.size(); i+=4)
        c.push_back(Creep(creep[i], creep[i+1], creep[i+2], creep[i+3]));

    vector<Tower> tower = placeTowers(c, money, baseHealth);

    vector<int> ret;
    for (int i=0; i<(int)tower.size(); i++)
        ret.push_back(tower[i].x),
        ret.push_back(tower[i].y),
        ret.push_back(tower[i].type);

    elapsedTime += time() - start;
    if (step == 2000)
    {
        //cerr<<"Total tower: "<<this->tower.size()<<endl;
        cerr<<"Elapsed Time: "<<elapsedTime<<endl;
    }

    return ret;
}

const int PathDefense::dx[4] = {0, -1, 0, 1};
const int PathDefense::dy[4] = {1, 0, -1, 0};

vector<PathDefense::Tower> PathDefense::placeTowers(vector<Creep> creep,
    int money, vector<int> baseHealth)
{
    for (Creep &c: creep)
        creepId.insert(c.id);

    vector<Tower> res;

    int maxCost = 0;
    for (TowerType &t: towerType)
        maxCost = max(maxCost, t.cost);

    if (money >= maxCost)
    {
        vector<pair<int,int> > P;
        for (int y=0; y<H; y++)
        for (int x=0; x<W; x++)
        if (board[y][x] == '#')
        {
            bool f = false;
            for (Creep &c: creep)
            {
                if (dist(c.x, c.y, x, y) <= 5*5)
                    f = true;
            }
            if (f)
                P.push_back(make_pair(x, y));
        }

        if (!P.empty())
        {
            random_shuffle(P.begin(), P.end());

            int count;

            if (step < 256)
            {
                count = min(256/int(towerType.size()), int(P.size()));
            }
            else
            {
                int total = accumulate(simCount.begin(), simCount.end(), 0);
                count = int((total*(15-elapsedTime)/elapsedTime)
                    / (simCount.size()*(2000-step)/(step+1)));
            }
        
            count = min(max(count, 1), int(P.size()));
            //cerr<<step<<" "<<elapsedTime<<" "<<count<<" "<<P.size()<<endl;

            simCount.push_back(count);

            int bestScore = simulate(creep, money, baseHealth, tower);
            Tower bestTower(0, 0, -1);

            for (int i=0; i<count; i++)
            {
                int p = rand()%int(P.size());
                int x = P[p].first;
                int y = P[p].second;
            
                for (int type=0; type<(int)towerType.size(); type++)
                if (int(tower.size())<100 || towerType[type].used > 0)
                {
                    tower.push_back(Tower(x, y, type));
                    int s = simulate(creep, money-towerType[type].cost,
                        baseHealth, tower);
                    tower.pop_back();

                    if (s > bestScore)
                    {
                        bestScore = s;
                        bestTower = Tower(x, y, type);
                    }
                }
            }

            if (bestTower.type >= 0)
            {
                board[bestTower.y][bestTower.x] = 'T';
                res.push_back(bestTower);
                tower.push_back(bestTower);
                money -= towerType[bestTower.type].cost;
                towerType[bestTower.type].used++;
            }
        }
    }

    step++;

    return res;
}

void PathDefense::guessPath()
{
    path = vector<vector<int>>(H, vector<int>(W));

    for (int sy=0; sy<H; sy++)
    for (int sx=0; sx<W; sx++)
    if ((sx==0 || sx==W-1 || sy==0 || sy==H-1) &&
        board[sy][sx]=='.')
    {
        edgeX.push_back(sx);
        edgeY.push_back(sy);

        for (int d=0; d<4; d++)
        {
            vector<vector<int>> memo(H, vector<int>(W, -1));
            function<bool (int, int)> BT = [&](int x, int y)
            {
                if (x<0 || W<=x || y<0 || H<=y ||
                    board[y][x]=='#' ||
                    memo[y][x]==0)
                    return false;
                if (isdigit(board[y][x]) ||
                    memo[y][x]>0)
                    return true;
                memo[y][x] = 0;
                if (BT(x+dx[d], y+dy[d]))
                    memo[y][x] |= 1<<d;
                if (BT(x+dx[-~d%4], y+dy[-~d%4]))
                    memo[y][x] |= 1<<-~d%4;
                return memo[y][x]>0;
            };
            BT(sx, sy);

            for (int y=0; y<H; y++)
            for (int x=0; x<W; x++)
                if (memo[y][x] >= 0)
                    path[y][x] |= memo[y][x];
        }
    }

    for (int y=0; y<H; y++)
    for (int x=0; x<W; x++)
    if (path[y][x]>0)
    {
        vector<int> v;
        for (int i=0; i<4; i++)
            if (path[y][x]>>i&1)
                v.push_back(i);
        int n = int(v.size());
        while(int(v.size())<12)
            v.push_back(v[v.size()-n]);
        random_shuffle(v.begin(), v.end());
        //cerr<<v<<endl;

        path[y][x] = 0;
        for (int i=0; i<12; i++)
            path[y][x] <<= 2,
            path[y][x] |= v[i];
    }
}

int PathDefense::simulate(vector<Creep> creep, int money,
    vector<int> baseHealth, vector<Tower> tower)
{
    Random random;

    int total = int(creepId.size())*2000/(step+1);
    total = max(min(total, 2000), 500);
    int remain = total - int(creepId.size());

    int maxStep = min(step+100, 2000);

    vector<int> creepBorn[2000];
    for (int i=0; i<remain; i++)
    {
        if (step < 1999)
        {
            int s = random.rand()%(1999-step)+step+1;
            if (s < maxStep)
                creepBorn[s].push_back(random.rand()%int(edgeX.size()));
        }
    }

    for (int s=step; s<maxStep; s++)
    {
        for (Creep &c: creep)
        {
            int d = path[c.y][c.x]>>(step%12*2)&3;
            c.x += dx[d];
            c.y += dy[d];
            
            if (isdigit(board[c.y][c.x]))
            {
                int b = board[c.y][c.x] - '0';
                baseHealth[b] = max(baseHealth[b]-c.health, 0);
                c.health = 0;
            }
        }

        for (int c: creepBorn[s])
            creep.push_back(Creep(0, creepHealth<<(s/500), edgeX[c], edgeY[c]));

        for (Tower &t: tower)
        {
            TowerType &type = towerType[t.type];
            Creep *tc = nullptr;
            int td = 99999999;

            for (Creep &c: creep)
            if (c.health>0)
            {
                int d = dist(c.x, c.y, t.x, t.y);
                if (d <= type.range*type.range &&
                    (tc==nullptr || d<td))
                {
                    tc = &c;
                    td = d;
                }
            }

            if (tc!=nullptr)
            {
                tc->health -= type.attack;
                if (tc->health<=0)
                    money += creepMoney;
            }
        }

        vector<Creep> tmp;
        for (Creep &c: creep)
            if (c.health>0)
                tmp.push_back(c);
        creep = tmp;
    }

    return money + accumulate(baseHealth.begin(), baseHealth.end(), 0);
}

int PathDefense::dist(int x1, int y1, int x2, int y2)
{
    return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}

#ifdef TOPCODER_LOCAL

int main()
{
    PathDefense pathDefence;

    int N;
    cin>>N;
    int money;
    cin>>money;
    vector<string> board(N);
    for (string &s: board)
        cin>>s;
    int creepHealth;
    cin>>creepHealth;
    int creepMoney;
    cin>>creepMoney;
    int NT;
    cin>>NT;
    vector<int> towerType(NT);
    for (int &t: towerType)
        cin>>t;
    pathDefence.init(board, money, creepHealth, creepMoney, towerType);

    for (int t=0; t<2000; t++)
    {
        int money;
        cin>>money;
        int NC;
        cin>>NC;
        vector<int> creep(NC);
        for (int &c: creep)
            cin>>c;
        int B;
        cin>>B;
        vector<int> baseHealth(B);
        for (int &b: baseHealth)
            cin>>b;
        vector<int> ret = pathDefence.placeTowers(creep, money, baseHealth);
        cout<<ret.size()<<endl;
        for (int r: ret)
            cout<<r<<endl;
    }
}

#endif

/*
20
371
#.###.####.##.######
#.##..####....######
#.##.######..#######
#.....#####..#######
####..#####..#######
####.........#######
####.######..#######
####.######..#######
####.######..#######
####.######...######
####.######...######
#............1###...
#.##.######..####.##
..##.######..####.##
####.######..#....##
####0######23.....##
##############..#...
###############.####
###############..###
################.###
4
1
48
2 2 25 1 4 30 2 2 24 5 3 6 5 3 7 5 2 16 4 5 28 2 5 25 4 2 30 2 2 29 3 2 32 5 4 35 5 4 17 5 1 28 2 4 13 2 1 26
371
0
4
1000 1000 1000 1000
*/