hirokazu1020さんのソースコード

//------------------------------------------------------------------------------
/// @file
/// @brief    HPCAnswer.hpp の実装 (解答記述用ファイル)
/// @author   ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright  Copyright (c) 2015 HAL Laboratory, Inc.
/// @attention  このファイルの利用は、同梱のREADMEにある
///             利用条件に従ってください
 
//------------------------------------------------------------------------------
 
#include "HPCAnswer.hpp"
#include "HPCMath.hpp"
#include "HPCParameter.hpp"
#include "HPCRandom.hpp"
#include<algorithm>
#include<vector>
#include<iostream>
#include<numeric>
#include<utility>
#include<array>
#include<stack>
#include<typeinfo>
#include<cassert>
#include<cstring>
#include<cstdio>
#include<climits>
#include<ctime>
 
 
/// プロコン問題環境を表します。
namespace hpc {
    typedef short T;
    const int TMAX = std::numeric_limits<T>::max() / 2;
    const int WeightLimit = Parameter::TruckWeight + Parameter::TruckWeightCapacity;
    int dist[Parameter::ItemCountMax][Parameter::ItemCountMax]; //配達先間の距離
    int dist_office[Parameter::ItemCountMax];   //営業所から配達先への距離
    T weights[1 << Parameter::ItemCountMax];    //荷物集合のトラックを含めた重量
    T tsp[1 << Parameter::ItemCountMax][Parameter::ItemCountMax];
    T mintsp[1 << Parameter::ItemCountMax];     //荷物集合の最小配達コスト
 
    std::vector<Action> actions; int actidx;
    std::array<int, Parameter::PeriodCount> assigned; //各時間帯に割り当てられた荷物集合
 
    int stageCount = -1;
 
    ItemCollection sorted_items;
    std::vector<int> ord; //sort前のindex
 
 
    int heuristics[Parameter::ItemCountMax]; //コスト下界 
 
 
 
    class stack {
        int n;
        Pos p[150];
    public:
        stack() :n(0) {}
        void push(const Pos &a) { p[n++] = a; }
        void pop() { n--; }
        Pos top() const { return p[n - 1]; }
        bool empty() const { return n == 0; };
        int size() const { return n; };
        void clear() { n = 0; };
    };
 
    bool wall[Parameter::FieldWidthMax][32];
    stack st[4]; //優先順位付きキュー(リングバッファ)
 
    //sからgの距離
    int distance(Pos s, Pos g) {
        for (int i = 0; i < 4; i++)st[i].clear();
        int d[Parameter::FieldWidthMax][32];
        std::fill_n((int*)d, sizeof(d) / sizeof(d[0][0]), TMAX);
 
        int cur = 0;
        d[s.x][s.y] = 0;
        //ref:HPCField.cpp  (odd,odd):=non-wall, (even,even):=wall
        // (odd,odd)の座標のみ優先順位付きキュー(リングバッファ)に突っ込む
        if ((s.x & 1) == 0) {
            if (!wall[s.x - 1][s.y]) { //壁判定いらない
                d[s.x - 1][s.y] = 1;
                st[(abs(s.x - 1 - g.x) - abs(s.x - g.x) + 1) >> 1].push(Pos(s.x - 1, s.y));
            }
            if (!wall[s.x + 1][s.y]) {
                d[s.x + 1][s.y] = 1;
                st[(abs(s.x + 1 - g.x) - abs(s.x - g.x) + 1) >> 1].push(Pos(s.x + 1, s.y));
            }
        }
        else if ((s.y & 1) == 0) {
            if (!wall[s.x][s.y - 1]) {
                d[s.x][s.y - 1] = 1;
                st[(abs(s.y - 1 - g.y) - abs(s.y - g.y) + 1) >> 1].push(Pos(s.x, s.y - 1));
            }
            if (!wall[s.x][s.y + 1]) {
                d[s.x][s.y + 1] = 1;
                st[(abs(s.y + 1 - g.y) - abs(s.y - g.y) + 1) >> 1].push(Pos(s.x, s.y + 1));
            }
        }
        else {
            st[0].push(s);
        }
        while (1) {
            while (st[cur].empty())cur = (cur + 1) & 3;
            Pos a;
            a = st[cur].top();
            if (a == g)return d[g.x][g.y];
            st[cur].pop();
            int da = d[a.x][a.y] + 2;
            int hx = abs(a.x - g.x) - 2;
            int hy = abs(a.y - g.y) - 2;
            if (hx + hy == -3) {
                return d[a.x][a.y] + 1;
            }
            a.x += 2;
            if (!wall[a.x - 1][a.y] && da < d[a.x][a.y]) {
                d[a.x][a.y] = da;
                st[(cur + ((abs(a.x - g.x) - hx) >> 1)) & 3].push(a);
            }
            a.x -= 4;
            if (!wall[a.x + 1][a.y] && da < d[a.x][a.y]) {
                d[a.x][a.y] = da;
                st[(cur + ((abs(a.x - g.x) - hx) >> 1)) & 3].push(a);
            }
            a.x += 2;
            a.y += 2;
            if (!wall[a.x][a.y - 1] && da < d[a.x][a.y]) {
                d[a.x][a.y] = da;
                st[(cur + ((abs(a.y - g.y) - hy) >> 1)) & 3].push(a);
            }
            a.y -= 4;
            if (!wall[a.x][a.y + 1] && da < d[a.x][a.y]) {
                d[a.x][a.y] = da;
                st[(cur + ((abs(a.y - g.y) - hy) >> 1)) & 3].push(a);
            }
        }
        return -1;
    }
 
    //actの末尾にsからgへの最小移動経路を連結
    void concat_route(Pos s, Pos g, std::vector<Action> &act) {
        for (int i = 0; i < 4; i++)st[i].clear();
        int d[Parameter::FieldWidthMax][32];
        std::fill_n((int*)d, sizeof(d) / sizeof(d[0][0]), TMAX);
        if (s == g)return;
        int cur = 0;
        d[g.x][g.y] = 0;
        if ((g.x & 1) == 0) {
            if (!wall[g.x - 1][g.y]) {
                d[g.x - 1][g.y] = 1;
                st[(abs(g.x - 1 - s.x) - abs(g.x - s.x) + 1) >> 1].push(Pos(g.x - 1, g.y));
            }
            if (!wall[g.x + 1][g.y]) {
                d[g.x + 1][g.y] = 1;
                st[(abs(g.x + 1 - s.x) - abs(g.x - s.x) + 1) >> 1].push(Pos(g.x + 1, g.y));
            }
        }
        else if ((g.y & 1) == 0) {
            if (!wall[g.x][g.y - 1]) {
                d[g.x][g.y - 1] = 1;
                st[(abs(g.y - 1 - s.y) - abs(g.y - s.y) + 1) >> 1].push(Pos(g.x, g.y - 1));
            }
            if (!wall[g.x][g.y + 1]) {
                d[g.x][g.y + 1] = 1;
                st[(abs(g.y + 1 - s.y) - abs(g.y - s.y) + 1) >> 1].push(Pos(g.x, g.y + 1));
            }
        }
        else {
            st[0].push(g);
        }
        while (1) {
            while (st[cur].empty())cur = (cur + 1) & 3;
            Pos a;
            a = st[cur].top();
            if (a == s)break;
            st[cur].pop();
            int da = d[a.x][a.y] + 2;
            int hx = abs(a.x - s.x) - 2;
            int hy = abs(a.y - s.y) - 2;
            if (hx + hy == -3) {
                d[s.x][s.y] = d[a.x][a.y] + 1;
                break;
            }
            a.x += 2;
            if (!wall[a.x - 1][a.y] && da < d[a.x][a.y]) {
                d[a.x - 1][a.y] = da - 1;
                d[a.x][a.y] = da;
                st[(cur + ((abs(a.x - s.x) - hx) >> 1)) & 3].push(a);
            }
            a.x -= 4;
            if (!wall[a.x + 1][a.y] && da < d[a.x][a.y]) {
                d[a.x + 1][a.y] = da - 1;
                d[a.x][a.y] = da;
                st[(cur + ((abs(a.x - s.x) - hx) >> 1)) & 3].push(a);
            }
            a.x += 2;
            a.y += 2;
            if (!wall[a.x][a.y - 1] && da < d[a.x][a.y]) {
                d[a.x][a.y - 1] = da - 1;
                d[a.x][a.y] = da;
                st[(cur + ((abs(a.y - s.y) - hy) >> 1)) & 3].push(a);
            }
            a.y -= 4;
            if (!wall[a.x][a.y + 1] && da < d[a.x][a.y]) {
                d[a.x][a.y + 1] = da - 1;
                d[a.x][a.y] = da;
                st[(cur + ((abs(a.y - s.y) - hy) >> 1)) & 3].push(a);
            }
        }
	//経路復元
        while (s != g) {
            for (int i = 0; i < 4; i++) {
                Pos b = s.move((Action)i);
                if (d[b.x][b.y] + 1 == d[s.x][s.y]) {
                    act.push_back((Action)i);
                    s = b;
                    break;
                }
            }
        }
    }
 
    //荷物のbit集合に対する最適配達経路
    std::vector<Action> route(Pos office, int bits) {
        int p = -1; //今いる配達先
        for (int i = 0; i < sorted_items.count(); i++) {
            if ((bits >> i & 1) && tsp[bits][i] + weights[bits] * dist_office[i] == mintsp[bits]) {
                p = i;
                break;
            }
        }
 
        std::vector<Action> act;
        act.reserve(400);
        if (bits == 0)return std::move(act);
	//TSPの経路復元
        concat_route(office, sorted_items[p].destination(), act);
        while (bits&(bits - 1)) {
            int nxt = -1; //一つ先の配達先
            for (int i = 0; i < sorted_items.count(); i++) {
                if (p != i && (bits >> i & 1) && tsp[bits&~(1 << p)][i] + weights[bits&~(1 << p)] * dist[i][p] == tsp[bits][p]) {
                    nxt = i;
                    break;
                }
            }
            concat_route(sorted_items[p].destination(), sorted_items[nxt].destination(), act);
            bits &= ~(1 << p);
            p = nxt;
        }
        concat_route(sorted_items[p].destination(), office, act);
        return std::move(act);
    }
 
    //mintspを遅延評価
    int calc_cost(int bits) {
        if (mintsp[bits] != TMAX)return mintsp[bits];
        if (weights[bits] > WeightLimit)return TMAX;
 
        int z[Parameter::ItemCountMax], nz;
        nz = 0;
        for (int j = 0; j < sorted_items.count(); j++) {
            if ((bits >> j & 1) == 1) {
                z[nz++] = j;
                calc_cost(bits & ~(1 << j));
            }
        }
        for (int j = 0; j < nz; j++) {
            const int a = z[j];
            int x = TMAX;
            const int w = weights[bits & ~(1 << a)];
            for (int k = 0; k < j; k++) {
                int b = z[k];
                x = std::min<int>(x, tsp[bits & ~(1 << a)][b] + w * dist[a][b]);
            }
            for (int k = j + 1; k < nz; k++) {
                int b = z[k];
                x = std::min<int>(x, tsp[bits & ~(1 << a)][b] + w * dist[a][b]);
            }
            tsp[bits][a] = x;
        }
 
        int x = TMAX;
        int w = weights[bits];
        for (int j = 0; j < nz; j++) {
            const int a = z[j];
            x = std::min<int>(x, tsp[bits][a] + w * dist_office[a]);
        }
        return mintsp[bits] = x;
    }
 
    //分枝限定法
    std::pair<int, std::array<int, Parameter::PeriodCount>> search(int idx, int mincost) {
        if (idx == -1) {
            return std::make_pair(mintsp[assigned[0]] + mintsp[assigned[1]] + mintsp[assigned[2]] + mintsp[assigned[3]], assigned);
        }
 
        std::pair<int, std::array<int, Parameter::PeriodCount>> res, tmp;
        res.first = mincost;
        if (mintsp[assigned[0]] + mintsp[assigned[1]] + mintsp[assigned[2]] + mintsp[assigned[3]] + heuristics[idx] >= mincost)
            return std::move(res);
 
 
        std::pair<int, int> a[Parameter::PeriodCount];
        for (int i = 0; i < Parameter::PeriodCount; i++) {
            a[i] = std::make_pair(calc_cost(assigned[i] | 1 << idx) - mintsp[assigned[i]], i);
        }
	//増加コストでソート
        std::sort(a, a + Parameter::PeriodCount, [](const std::pair<int, int> &x, const std::pair<int, int> &y) {return x.first < y.first; });
 
        int c = 0;
        for (int i = 0; i < Parameter::PeriodCount; i++) {
            if (assigned[a[i].second] == 0 && ++c >= 2)continue;
            assigned[a[i].second] ^= 1 << idx;
            tmp = search(idx - 1, res.first);
            if (res.first > tmp.first)res = tmp;
            assigned[a[i].second] ^= 1 << idx;
        }
        return std::move(res);
    }
 
    //------------------------------------------------------------------------------
    /// 各ステージ開始時に呼び出されます。
    ///
    /// ここで、各ステージに対して初期処理を行うことができます。
    ///
    /// @param[in] aStage 現在のステージ。
    void Answer::Init(const Stage& aStage)
    {
        //clock_t ct = clock();
        stageCount++;
        //printf("%d:\n",stageCount);
        const Field &field = aStage.field();
        const ItemCollection &items = aStage.items();
 
 	//荷物をソート
        sorted_items = items;
        ord.clear();
        //period -1を先頭に
        for (int i = -1; i < Parameter::PeriodCount; i++) {
            for (int j = 0; j < items.count(); j++) {
                if (items[j].period() == i) {
                    sorted_items[ord.size()] = items[j];
                    ord.push_back(j);
                }
            }
            if (i == -1) {
                Pos a = field.officePos();
                for (int j = 0; j < (int)ord.size(); j++) {
                    for (int k = ord.size() - 1; k > j; k--) {
                        Pos b = sorted_items[k - 1].destination();
                        Pos c = sorted_items[k].destination();
                        //if (abs(b.x - a.x) + abs(b.y - a.y) > abs(c.x - a.x) + abs(c.y - a.y)) {
                        if ((abs(b.x - a.x) + abs(b.y - a.y))*(sorted_items[k - 1].weight() + 1) > (abs(c.x - a.x) + abs(c.y - a.y))*(sorted_items[k].weight() + 1)) {
                            std::swap(sorted_items[k - 1], sorted_items[k]);
                            std::swap(ord[k - 1], ord[k]);
                        }
                    }
                }
            }
        }
 
	//距離計算
        memset(dist, -1, sizeof(dist));
        for (int y = 0; y < field.height(); y++)
            for (int x = 0; x < field.width(); x++)wall[x][y] = field.isWall(Pos(x, y));
        for (int i = 0; i < sorted_items.count(); i++) {
            Pos a = sorted_items[i].destination();
            int pa = sorted_items[i].period();
            for (int j = 0; j < i; j++) {
                Pos b = sorted_items[j].destination();
                int pb = sorted_items[j].period();
                if (pa == -1 || pb == -1 || pa == pb)
                    dist[i][j] = dist[j][i] = distance(a, b);
            }
            dist[i][i] = 0;
            dist_office[i] = distance(field.officePos(), a);
        }
 
 
        weights[0] = Parameter::TruckWeight;
        for (int i = 0; i < sorted_items.count(); i++) weights[1 << i] = sorted_items[i].weight() + Parameter::TruckWeight;
        for (int i = 1; i < (1 << sorted_items.count()); i++) {
            weights[i] = weights[i&(i - 1)] + weights[i&-i] - Parameter::TruckWeight;
        }
 
        //初期化いらない
        /*if (typeid(T) == typeid(short))
            std::fill_n((int*)tsp, (1 << sorted_items.count())*Parameter::ItemCountMax / 2, (int)TMAX << 16 | TMAX);
        else
            std::fill_n((T*)tsp, (1 << sorted_items.count())*Parameter::ItemCountMax, TMAX);
        */
        std::fill_n(mintsp, 1 << sorted_items.count(), TMAX);
        mintsp[0] = 0;
        for (int i = 0; i < sorted_items.count(); i++) {
            tsp[1 << i][i] = weights[0] * dist_office[i];
            mintsp[1 << i] = tsp[1 << i][i] + weights[1 << i] * dist_office[i];
        }
 
 	//時間指定荷物を割り当て
        int num_unassigned = 0;
        std::fill(assigned.begin(), assigned.end(), 0);
        for (int i = 0; i < sorted_items.count(); i++) {
            if (sorted_items[i].period() == -1)num_unassigned++;
            else assigned[sorted_items[i].period()] |= 1 << i;
        }
 
	//下界の計算
        for (int i = 0; i < num_unassigned; i++) {
            int wi = sorted_items[i].weight();
            int h = 2 * dist_office[i] * Parameter::TruckWeight + wi *  dist_office[i];
            for (int j = i + 1; j < sorted_items.count(); j++) {
                for (int k = i + 1; k < sorted_items.count(); k++) {
                    if (k == j)continue;
                    //j -> i -> k
                    if (dist[j][k] != -1)h = std::min(h, (dist[i][j] + dist[i][k] - dist[j][k])*(Parameter::TruckWeight + sorted_items[k].weight()) + wi * (dist_office[j] + dist[j][i]));
                }
                //office -> i -> j
                h = std::min(h, (dist_office[i] + dist[i][j] - dist_office[j])*(Parameter::TruckWeight + sorted_items[j].weight()) + wi *  dist_office[i]);
                //j -> i -> office
                h = std::min(h, (dist_office[i] + dist[i][j] - dist_office[j])*Parameter::TruckWeight + wi * (dist_office[j] + dist[i][j]));
            }
            heuristics[i] = h;
        }
        for (int i = 1; i < num_unassigned; i++) heuristics[i] += heuristics[i - 1];
 
 
        for (int i = 0; i < Parameter::PeriodCount; i++)
            calc_cost(assigned[i]);
        assigned = search(num_unassigned - 1, TMAX).second;
 
        //printf("%d : %d %d %.3f\n",stageCount,items.count(),num_unassigned,(clock()-ct)/(double)CLOCKS_PER_SEC);
 
    }
 
    //------------------------------------------------------------------------------
    /// 各配達時間帯開始時に呼び出されます。
    ///
    /// ここで、この時間帯に配達する荷物をトラックに積み込みます。
    /// どの荷物をトラックに積み込むかを決めて、引数の aItemGroup に対して
    /// setItem で荷物番号を指定して積み込んでください。
    ///
    /// @param[in] aStage 現在のステージ。
    /// @param[in] aItemGroup 荷物グループ。
    void Answer::InitPeriod(const Stage& aStage, ItemGroup& aItemGroup)
    {
        actions = route(aStage.field().officePos(), assigned[aStage.period()]);
        actidx = 0;
        for (int i = 0; i < aStage.items().count(); ++i) {
            if (assigned[aStage.period()] >> i & 1) aItemGroup.addItem(ord[i]);
        }
    }
 
    //------------------------------------------------------------------------------
    /// 各ターンでの動作を返します。
    ///
    /// @param[in] aStage 現在ステージの情報。
    ///
    /// @return これから行う動作を表す Action クラス。
    Action Answer::GetNextAction(const Stage& aStage)
    {
        return actions[actidx++];
    }
 
    //------------------------------------------------------------------------------
    /// 各配達時間帯終了時に呼び出されます。
    ///
    /// ここで、この時間帯の終了処理を行うことができます。
    ///
    /// @param[in] aStage 現在のステージ。
    /// @param[in] aStageState 結果。Playingならこの時間帯の配達完了で、それ以外なら、何らかのエラーが発生した。
    /// @param[in] aCost この時間帯に消費した燃料。エラーなら0。
    void Answer::FinalizePeriod(const Stage& aStage, StageState aStageState, int aCost)
    {
        if (aStageState == StageState_Failed) {
            // 失敗したかどうかは、ここで検知できます。
        }
    }
 
    //------------------------------------------------------------------------------
    /// 各ステージ終了時に呼び出されます。
    ///
    /// ここで、各ステージに対して終了処理を行うことができます。
    ///
    /// @param[in] aStage 現在のステージ。
    /// @param[in] aStageState 結果。Completeなら配達完了で、それ以外なら、何らかのエラーが発生した。
    /// @param[in] aScore このステージで獲得したスコア。エラーなら0。
    void Answer::Finalize(const Stage& aStage, StageState aStageState, int aScore)
    {
        //std::cout << aStage.lastTurnResult().totalCost << std::endl;
        if (aStageState == StageState_Failed) {
            // 失敗したかどうかは、ここで検知できます。
        }
        else if (aStageState == StageState_TurnLimit) {
            // ターン数オーバーしたかどうかは、ここで検知できます。
        }
    }
}
 
//------------------------------------------------------------------------------
// EOF