o0p1qさんのソースコード

//------------------------------------------------------------------------------
/// @file
/// @brief    HPCAnswer.hpp の実装 (解答記述用ファイル)
/// @author   ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright  Copyright (c) 2015 HAL Laboratory, Inc.
/// @attention  このファイルの利用は、同梱のREADMEにある
///             利用条件に従ってください

//------------------------------------------------------------------------------

#include "HPCAnswer.hpp"
#include "HPCMath.hpp"

/* **** include ***** */
#include <algorithm>
#include <functional>

/* **** global variable **** */
static int stageCount;

/* 定数 */
static const int inf = 1000000007;
static const int periodMax = 4;
static const int truckWeight = 3;
static const int weightMax = 15;
static const int itemMax = 16;
static const int widthMax = 31;
static const int heightMax = 31;
static const int turnMax = 1000;

/* 最善の巡回路を求めるbitDPで使用 */
static int g_dp[1 << itemMax][itemMax];
static int g_next[1 << itemMax][itemMax];
static int g_weight[1 << itemMax];
static int g_memo[1 << itemMax];
static int g_from[1 << itemMax][itemMax];
static int g_to[1 << itemMax][itemMax];

/* 荷物の情報 */
static int g_itemsPeriod[itemMax];
static int g_itemsWeight[itemMax];

/* 最短距離 */
static int g_dist[itemMax + 1][itemMax + 1];

/* 壁の有無 */
static bool g_wall[heightMax][widthMax];

/* 4方向の壁の有無の組み合わせに対した移動の有効な方向を格納 */
static int g_direction[1 << hpc::Action_TERM][hpc::Action_TERM + 1];
/* 各座標ごとの移動が有効な方向 */
static int g_directionIdx[heightMax * widthMax];

/* left right down up */
static const int dy[] {0, 0, -1, 1};
static const int dx[] {-1, 1, 0, 0};

/* bfsで使用するQueue */
static int g_queue[widthMax * heightMax];

/* bfsで使用する各座標へのコスト */
static int g_cost[heightMax * widthMax];
/* 経路復元用 */
static int g_recd[itemMax][heightMax][widthMax];

/* 荷物・オフィスの座標 */
static int g_posY[itemMax + 1];
static int g_posX[itemMax + 1];

/* period毎の積む荷物 */
static int g_eachItemIndices[periodMax][itemMax];
static int g_eachItemIndices_size[periodMax];
static int g_tmp_eachItemIndices[periodMax][itemMax];
static int g_tmp_eachItemIndices_size[periodMax];

/* period毎の巡回路 */
static int g_eachRoute[periodMax][itemMax + 2]; // 始点と終点のオフィス分の+2
static int g_eachRoute_size[periodMax];

/* 時間帯の決まっていない荷物 */
static int g_anytime[itemMax];
static int g_anytime_size;
/* 時間帯の決まっていない荷物を配達するために最低限必要なコスト */
static int g_needCost[itemMax];

/* period毎の積載量 */
static int g_eachWeight[periodMax];
static int g_tmp_eachWeight[periodMax];
/* period毎の積む荷物のmask */
static int g_eachMask[periodMax];
static int g_tmp_eachMask[periodMax];
/* period毎の消費燃料 */
static int g_eachFuel[periodMax];
static int g_tmp_eachFuel[periodMax];

/* tmp */
static int g_tmp[itemMax];
static int g_tmp_size;

/* action */
static hpc::Action g_action[turnMax];
static int g_action_size;

/* ステージ毎に解法を作成するクラス */
class Solve {

    const hpc::ItemCollection &items;
    const hpc::Field &field;

    const int width;
    const int height;

    /* 使用する変数(配列)でのオフィスの情報のインデックス (== items.count()) */
    const int officeIndex;

    /* 最善の荷物の配達時間帯を導出する関数間で用いる */
    int a_idx;
    int a_minCost;
    int a_currCost;
    int a_itemIndicesMask;
    int a_bestItemIndicesMask;

public:

    Solve(const hpc::Stage& aStage)
        : items(aStage.items())
        , field(aStage.field())
        , width(aStage.field().width())
        , height(aStage.field().height())
        , officeIndex(aStage.items().count())
    {
        /* プログラム中1回だけ行う処理 */
        if (!stageCount) {
            /* bitDPで使用する、bitに対して移動元として有効なインデックス(g_from)と移動先として有効なインデックス(g_to)を求める */
/* 1つの時間帯で積める荷物の最大数は10 */
#define ITEM_MAX 10
            for (int bit = 1; bit < (1 << ITEM_MAX); ++bit) {
                /* 移動元はbitが立っている場所 */
                int gfidx = 0;
                for (int from = 0; (1 << from) <= bit; ++from) {
                    if (~bit & (1 << from))
                        continue;
                    g_from[bit][gfidx++] = from;
                }
                g_from[bit][gfidx] = -1;
                /* 移動先はbitが立っていない場所 */
                int gtidx = 0;
                for (int to = 0; to < ITEM_MAX; ++to) {
                    if (bit & (1 << to))
                        continue;
                    g_to[bit][gtidx++] = to;
                }
                g_to[bit][gtidx] = inf;
            }
#undef ITEM_MAX

            /* bfsで使用する各座標への移動コストをinfで初期化 */
            for (int i = 0; i < widthMax * heightMax; ++i) {
                g_cost[i] = inf;
            }

            /* 4方向の壁に対して移動の有効な方向を全ての壁の組み合わせに対して列挙 */
            for (int bit = 0; bit < (1 << hpc::Action_TERM); ++bit) {
                int idx = 0;
                for (int i = 0; i < hpc::Action_TERM; ++i) {
                    if (~bit & (1 << i)) {
                        g_direction[bit][idx++] = i;
                    }
                }
                g_direction[bit][idx] = hpc::Action_TERM;
            }
        }

        ++stageCount;
        for (int i = 0; i < officeIndex; ++i) {
            g_itemsWeight[i] = items[i].weight();
            g_itemsPeriod[i] = items[i].period();
        }
        for (int i = 0; i < (1 << officeIndex); ++i) {
            g_memo[i] = -1;
        }

        initWall();
        initPosition();
        initDistance();
        g_action_size = 0;
        initDistribution();
        g_action_size = 0;
    }

private:

    void initWall()
    {
        /* 壁を生やす */
        for (int y = 1; y < height - 1; ++y) {
            for (int x = 1; x < width - 1; ++x) {
                g_wall[y][x] = field.isWall(x, y);
            }
            g_wall[y][0] = g_wall[y][width - 1] = true;
        }
        for (int x = 1; x < width - 1; ++x) {
            g_wall[0][x] = g_wall[height - 1][x] = true;
        }

        /* 座標ごとに移動の有効な方向を決定 */
        for (int y = 1; y < height - 1; ++y) {
            for (int x = 1; x < width - 1; ++x) {
                g_directionIdx[y * width + x] =
                    (g_wall[y + dy[0]][x + dx[0]]) |
                    (g_wall[y + dy[1]][x + dx[1]] << 1) |
                    (g_wall[y + dy[2]][x + dx[2]] << 2) |
                    (g_wall[y + dy[3]][x + dx[3]] << 3) ;
            }
        }
    }

    void initPosition()
    {
        for (int i = 0; i < officeIndex; ++i) {
            const hpc::Pos &p = items[i].destination();
            g_posY[i] = p.y;
            g_posX[i] = p.x;
        }
        const hpc::Pos &p = field.officePos();
        g_posY[officeIndex] = p.y;
        g_posX[officeIndex] = p.x;
    }

    void initDistance()
    {
        for (int i = 0; i < officeIndex; ++i) {
            bfs(i);
        }
    }

    void initDistribution()
    {
        for (int i = 0; i < periodMax; ++i) {
            g_eachItemIndices_size[i] = 0;
        }

        /* itemIndicesにperiod毎に配る荷物を登録する */
        distributeItems();

        for (int i = 0; i < periodMax; ++i) {
            if (!g_eachItemIndices_size[i])
                continue;
            g_eachRoute_size[i] = 0;
            leadRoute(i);
            for (int j = 1; j < g_eachRoute_size[i]; ++j) {
                restoreRoute(g_eachRoute[i][j - 1], g_eachRoute[i][j]);
            }
        }
    }

    /* 最短経路を導出 */
    inline void bfs(const int startIndex)
    {
        /* 距離を測る必要のある荷物の座標に目印を付ける */
        int cnt = 0;
        if (g_itemsPeriod[startIndex] == -1) {
            for (int i = startIndex + 1; i <= officeIndex; ++i) {
                g_cost[g_posY[i] * width + g_posX[i]] += i;
                cnt++;
            }
        } else {
            for (int i = startIndex + 1; i < officeIndex; ++i) {
                /* 求める必要のない組みを弾く */
                if ((g_itemsPeriod[i] != -1) && (g_itemsPeriod[startIndex] != g_itemsPeriod[i])) {
                    continue;
                }
                g_cost[g_posY[i] * width + g_posX[i]] += i;
                ++cnt;
            }
            g_cost[g_posY[officeIndex] * width + g_posX[officeIndex]] += officeIndex;
            ++cnt;
        }

        int q_top = 0;
        int q_tail = 0;

        g_queue[q_tail++] = g_posY[startIndex] * width + g_posX[startIndex];
        g_cost[g_queue[q_top]] = 0;

        while (cnt) {
            const int &p = g_queue[q_top++];
            const int y = p / width;
            const int x = p % width;

            const int *const direction = g_direction[g_directionIdx[p]];
            for (int d = 0; direction[d] != hpc::Action_TERM; ++d) {
                const int &i = direction[d];
                const int ny = y + dy[i];
                const int nx = x + dx[i];
                const int np = ny * width + nx;

                if (g_cost[p] + 1 < g_cost[np]) {
                    if (inf < g_cost[np]) {
                        const int idx = g_cost[np] % inf;
                        g_dist[startIndex][idx] = g_dist[idx][startIndex] = g_cost[p] + 1;
                        --cnt;
                    }

                    g_cost[np] = g_cost[p] + 1;
                    g_queue[q_tail++] = np;

                    g_recd[startIndex][ny][nx] = i;
                }
            }
        }

        /* 使用した座標のコストをinfで上書き */
        for (int i = 0; i < q_tail; ++i) {
            g_cost[g_queue[i]] = inf;
        }
    }

    /* 経路復元 */
    inline void restoreRoute(int srcIdx, int dstIdx)
    {
        if (srcIdx < dstIdx) {
            const int &srcY = g_posY[srcIdx];
            const int &srcX = g_posX[srcIdx];
            int dstY = g_posY[dstIdx];
            int dstX = g_posX[dstIdx];

            /* src -> dst の経路復元 */
            g_action_size += g_dist[srcIdx][dstIdx];
            int idx = g_action_size - 1;
            while (srcY != dstY || srcX != dstX) {
                g_action[idx--] = static_cast<hpc::Action>(g_recd[srcIdx][dstY][dstX]);
                hpc::Action a = static_cast<hpc::Action>(((1 - g_recd[srcIdx][dstY][dstX]) + hpc::Action_TERM) % hpc::Action_TERM);
                dstY += dy[a];
                dstX += dx[a];
            }

        } else {
            std::swap(srcIdx, dstIdx);

            const int &srcY = g_posY[srcIdx];
            const int &srcX = g_posX[srcIdx];
            int dstY = g_posY[dstIdx];
            int dstX = g_posX[dstIdx];

            /* dst -> src の経路復元 */
            while (srcY != dstY || srcX != dstX) {
                hpc::Action a = static_cast<hpc::Action>(((1 - g_recd[srcIdx][dstY][dstX]) + hpc::Action_TERM) % hpc::Action_TERM);
                g_action[g_action_size++] = a;
                dstY += dy[a];
                dstX += dx[a];
            }
        }
    }

    /* 消費燃料が最小となるように荷物を分ける */
    void distributeItems()
    {
        /* period毎の重さ */
        for (int i = 0; i < periodMax; ++i) {
            g_eachWeight[i] = 0;
        }

        g_anytime_size = 0;

        for (int i = 0; i < officeIndex; ++i) {
            /* 時間帯が決定している荷物の処理 */
            if (g_itemsPeriod[i] != -1) {
                g_eachItemIndices[g_itemsPeriod[i]][g_eachItemIndices_size[g_itemsPeriod[i]]++] = i;
                g_eachWeight[g_itemsPeriod[i]] += g_itemsWeight[i];
            /* 時間帯が決定していない荷物の処理 */
            } else {
                g_anytime[g_anytime_size++] = i;
            }
        }

        /* 時間帯が決定していない荷物がある */
        if (g_anytime_size) {
            /* 時間指定なしの荷物を、オフィスからの消費燃料の多い順にソート */
            if (1 < g_anytime_size) {
                for (int i = 0; i < g_anytime_size; ++i) {
                    g_anytime[i] += ((g_itemsWeight[g_anytime[i]]) * g_dist[officeIndex][g_anytime[i]]) * itemMax;
                }
                if (g_anytime_size == officeIndex) {
                    std::sort(g_anytime, g_anytime + g_anytime_size);
                } else {
                    std::sort(g_anytime, g_anytime + g_anytime_size, std::greater<int>());
                }
                for (int i = 0; i < g_anytime_size; ++i) {
                    g_anytime[i] %= itemMax;
                }
            }

            /* 何も登録されていなかったときは、1つはどこにどの荷物を登録してもよい */
            if (g_anytime_size == officeIndex) {
                g_eachItemIndices[0][g_eachItemIndices_size[0]++] = g_anytime[g_anytime_size - 1];
                g_eachWeight[0] += g_itemsWeight[g_anytime[g_anytime_size - 1]];
                g_itemsPeriod[g_anytime[g_anytime_size - 1]] = 0;
                --g_anytime_size;
                std::reverse(g_anytime, g_anytime + g_anytime_size);
            }

            if (g_anytime_size) {
                int sumFuel = 0;
                for (int i = 0; i < periodMax; ++i) {
                    /* 現状のそれぞれのperiod毎のmask */
                    g_eachMask[i] = 0;
                    for (int j = 0; j < g_eachItemIndices_size[i]; ++j) {
                        g_eachMask[i] |= 1 << g_eachItemIndices[i][j];
                    }
                    /* 現状のそれぞれのperiod毎の消費燃料 */
                    if (!g_eachItemIndices_size[i]) {
                        g_eachFuel[i] = 0;
                    } else {
                        g_eachFuel[i] = leadRouteCost(g_eachItemIndices[i], g_eachItemIndices_size[i], g_eachMask[i]);
                        sumFuel += g_eachFuel[i];
                    }
                }

                /* 枝刈り値を求めるためのコピー */
                for (int i = 0; i < periodMax; ++i) {
                    for (int j = 0; j < g_eachItemIndices_size[i]; ++j) {
                        g_tmp_eachItemIndices[i][j] = g_eachItemIndices[i][j];
                    }
                    g_tmp_eachItemIndices_size[i] = g_eachItemIndices_size[i];
                    g_tmp_eachWeight[i] = g_eachWeight[i];
                    g_tmp_eachMask[i] = g_eachMask[i];
                    g_tmp_eachFuel[i] = g_eachFuel[i];
                }
                /* 枝刈り値を求める */
                a_itemIndicesMask = 0;
                a_minCost = greedy();
                a_bestItemIndicesMask = a_itemIndicesMask;

                if (1 < g_anytime_size) {
                    /* 次の処理用 */
                    g_tmp_size = 0;
                    for (int t = 0; t < officeIndex; ++t) {
                        if (g_itemsPeriod[t] != -1) {
                            g_tmp[g_tmp_size++] = t;
                        }
                    }
                    for (int t = 0; t < g_anytime_size; ++t) {
                        g_tmp[g_tmp_size++] = g_anytime[t];
                    }

                    /* それぞれの荷物の配達に最低限必要な燃料 */
                    int needCostSum = 0;
                    for (int i = 0; i < g_anytime_size; ++i) {
                        const int &idx = g_anytime[i];

                        /* 対象の荷物配達以前にかかる最小コスト */
                        g_needCost[i] = g_itemsWeight[idx] * g_dist[officeIndex][idx];

                        /* 対象の荷物配達以降にかかる最小コスト */
                        int minCost = truckWeight * g_dist[idx][officeIndex];
                        for (int tmpJ = 0; g_tmp[tmpJ] != idx; ++tmpJ) {
                            const int &j = g_tmp[tmpJ];
                            for (int tmpK = tmpJ + 1;; ++tmpK) {
                                const int &k = (idx == g_tmp[tmpK] ? officeIndex : g_tmp[tmpK]);
                                /* 求める必要のない組みを弾く */
                                if ((g_itemsPeriod[j] != -1) && (k != officeIndex)) {
                                    if ((g_itemsPeriod[k] != -1) && (g_itemsPeriod[j] != g_itemsPeriod[k])) {
                                        continue;
                                    }
                                }
                                const int weight = ((k == officeIndex) ? (0) : (std::min(g_itemsWeight[j], g_itemsWeight[k])));
                                const int cost = (truckWeight + weight) * ((g_dist[j][idx] + g_dist[idx][k]) - g_dist[j][k]);
                                if (cost < minCost) {
                                    minCost = cost;
                                    if (minCost == 0)
                                        goto end;
                                }
                                if (k == officeIndex)
                                    break;
                            }
                        }
                        g_needCost[i] += minCost;
end:

                        needCostSum += g_needCost[i];
                    }

                    a_itemIndicesMask = 0;
                    a_idx = 0;
                    a_currCost = sumFuel + needCostSum;
                    dfs();
                }

                /* period毎に積む荷物の復元 */
                for (int i = 0; i < g_anytime_size; ++i) {
                    const int period = (a_bestItemIndicesMask >> (i * 2)) & 3;
                    g_eachItemIndices[period][g_eachItemIndices_size[period]++] = g_anytime[i];
                }
            }
        }
    }

    /* 下限値枝刈り法 */
    inline void dfs()
    {
        const int &idx = g_anytime[a_idx];

        a_currCost -= g_needCost[a_idx];

        bool f = false; // 荷物がない時間帯に登録するのは1回でよい
        for (int i = 0; i < periodMax; ++i) {
            if (f && !g_eachItemIndices_size[i])
                continue;
            f |= !g_eachItemIndices_size[i];

            if (weightMax < g_eachWeight[i] + g_itemsWeight[idx])
                continue;
            g_eachItemIndices[i][g_eachItemIndices_size[i]++] = idx;
            g_eachWeight[i] += g_itemsWeight[idx];
            g_eachMask[i] |= 1 << idx;
            a_itemIndicesMask |= i << (a_idx * 2);
            const int fuel = leadRouteCost(g_eachItemIndices[i], g_eachItemIndices_size[i], g_eachMask[i], a_minCost - (a_currCost - g_eachFuel[i])) - g_eachFuel[i];
            g_eachFuel[i] += fuel;
            a_currCost += fuel;
            ++a_idx;
            if (a_currCost < a_minCost) {
                if (a_idx == g_anytime_size) {
                    a_minCost = a_currCost;
                    a_bestItemIndicesMask = a_itemIndicesMask;
                } else {
                    dfs();
                }
            }
            --a_idx;
            a_currCost -= fuel;
            g_eachFuel[i] -= fuel;
            a_itemIndicesMask ^= i << (a_idx * 2);
            g_eachMask[i] ^= 1 << idx;
            g_eachWeight[i] -= g_itemsWeight[idx];
            --g_eachItemIndices_size[i];
        }

        a_currCost += g_needCost[a_idx];
    }

    /* 時間帯の決まっていない荷物を増加コストの低い時間帯に追加していく */
    int greedy()
    {
        for (int i = 0; i < g_anytime_size; ++i) {
            const int &idx = g_anytime[i];

            int minFuel = inf;
            int bestPeriod = -1;

            bool f = false;
            for (int j = 0; j < periodMax; ++j) {
                if (f && !g_tmp_eachItemIndices_size[j])
                    continue;
                f |= !g_tmp_eachItemIndices_size[j];

                if (weightMax < g_tmp_eachWeight[j] + g_itemsWeight[idx])
                    continue;
                g_tmp_eachItemIndices[j][g_tmp_eachItemIndices_size[j]++] = idx;
                g_tmp_eachWeight[j] += g_itemsWeight[idx];
                g_tmp_eachMask[j] |= 1 << idx;
                const int fuel = leadRouteCost(g_tmp_eachItemIndices[j], g_tmp_eachItemIndices_size[j], g_tmp_eachMask[j]) - g_tmp_eachFuel[j];
                if (fuel < minFuel) {
                   minFuel = fuel;
                   bestPeriod = j;
                }
                g_tmp_eachMask[j] ^= 1 << idx;
                g_tmp_eachWeight[j] -= g_itemsWeight[idx];
                --g_tmp_eachItemIndices_size[j];
            }

            g_tmp_eachItemIndices[bestPeriod][g_tmp_eachItemIndices_size[bestPeriod]++] = idx;
            g_tmp_eachWeight[bestPeriod] += g_itemsWeight[idx];
            g_tmp_eachFuel[bestPeriod] += minFuel;
            g_tmp_eachMask[bestPeriod] |= 1 << idx;

            a_itemIndicesMask |= bestPeriod << (i * 2);
        }

        int sumFuel = 0;
        for (int i = 0; i < periodMax; ++i) {
            sumFuel += g_tmp_eachFuel[i];
        }

        return sumFuel;
    }

    /* 最善の配達巡回路を導出
     * 消費燃料を返す
     */
    inline int leadRoute(const int period)
    {
        const int *const itemIndices = g_eachItemIndices[period];
        const int &itemIndicesSize = g_eachItemIndices_size[period];

        /* dp初期化 */
        for (int bit = 1; bit < (1 << itemIndicesSize); ++bit) {
            for (int gfidx = 0; g_from[bit][gfidx] != -1; ++gfidx) {
                g_dp[bit][g_from[bit][gfidx]] = inf;
            }
        }

        /* 各荷物の場所の初期値 */
        for (int i = 0; i < itemIndicesSize; ++i) {
            const int &idx = itemIndices[i];
            g_dp[1 << i][i] = truckWeight * g_dist[officeIndex][idx];
            g_weight[1 << i] = truckWeight + g_itemsWeight[idx];
        }

        /* bitDP */
        int bit;
        for (bit = 1; bit < (1 << itemIndicesSize) - 1; ++bit) {
            for (int gtidx = 0; g_to[bit][gtidx] < itemIndicesSize; ++gtidx) {
                const int &to = g_to[bit][gtidx];
                const int &tidx = itemIndices[to];
                const int nbit = bit | (1 << to);
                g_weight[nbit] = g_weight[bit] + g_itemsWeight[tidx];
                for (int gfidx = 0; g_from[bit][gfidx] != -1; ++gfidx) {
                    const int &from = g_from[bit][gfidx];
                    const int &fidx = itemIndices[from];
                    const int cost = g_dp[bit][from] + g_weight[bit] * g_dist[fidx][tidx];
                    if (cost < g_dp[nbit][to]) {
                        g_dp[nbit][to] = cost;
                        g_next[nbit][to] = from;
                    }
                }
            }
        }

        /* 巡回路復元 */
        g_eachRoute[period][g_eachRoute_size[period]++] = officeIndex;

        int minCost = inf;
        int src = -1;
        for (int from = 0; from < itemIndicesSize; ++from) {
            const int cost = g_dp[bit][from] + g_weight[bit] * g_dist[itemIndices[from]][officeIndex];
            if (cost < minCost) {
                minCost = cost;
                src = from;
            }
        }

        while (bit) {
            g_eachRoute[period][g_eachRoute_size[period]++] = itemIndices[src];
            int tmp = g_next[bit][src];
            bit ^= 1 << src;
            src = tmp;
        }

        g_eachRoute[period][g_eachRoute_size[period]++] = officeIndex;

        return minCost;
    }

    /* 配達巡回路は導出せず、最善の消費燃料を返すだけ */
    inline int leadRouteCost(const int* const itemIndices, const int& itemIndicesSize, int& memo_mask)
    {
        /* memo参照 */
        if (g_memo[memo_mask] != -1)
            return g_memo[memo_mask];

        /* dp初期化 */
        for (int bit = 1; bit < (1 << itemIndicesSize); ++bit) {
            for (int gfidx = 0; g_from[bit][gfidx] != -1; ++gfidx) {
                g_dp[bit][g_from[bit][gfidx]] = inf;
            }
        }

        /* 各荷物の場所の初期値 */
        for (int i = 0; i < itemIndicesSize; ++i) {
            const int &idx = itemIndices[i];
            g_dp[1 << i][i] = truckWeight * g_dist[officeIndex][idx];
            g_weight[1 << i] = truckWeight + g_itemsWeight[idx];
        }

        /* bitDP */
        int bit;
        for (bit = 1; bit < (1 << itemIndicesSize) - 1; ++bit) {
            int mm = 0;
            for (int gtidx = 0; g_to[bit][gtidx] < itemIndicesSize; ++gtidx) {
                const int &to = g_to[bit][gtidx];
                const int &tidx = itemIndices[to];
                const int nbit = bit | (1 << to);
                g_weight[nbit] = g_weight[bit] + g_itemsWeight[tidx];
                for (int gfidx = 0; g_from[bit][gfidx] != -1; ++gfidx) {
                    const int &from = g_from[bit][gfidx];
                    const int &fidx = itemIndices[from];
                    mm |= 1 << fidx;
                    g_dp[nbit][to] = std::min(g_dp[nbit][to], g_dp[bit][from] + g_weight[bit] * g_dist[fidx][tidx]);
                }
            }
            if (g_memo[mm] == -1) {
                int minCost = inf;
                for (int gfidx = 0; g_from[bit][gfidx] != -1; ++gfidx) {
                    const int &from = g_from[bit][gfidx];
                    minCost = std::min(minCost, g_dp[bit][from] + g_weight[bit] * g_dist[itemIndices[from]][officeIndex]);
                }
                g_memo[mm] = minCost;
            }
        }

        int minCost = inf;
        for (int from = 0; from < itemIndicesSize; ++from) {
            minCost = std::min(minCost, g_dp[bit][from] + g_weight[bit] * g_dist[itemIndices[from]][officeIndex]);
        }

        return g_memo[memo_mask] = minCost;
    }

    /* 配達巡回路は導出せず、最善の消費燃料を返すだけ */
    inline int leadRouteCost(const int* const itemIndices, const int& itemIndicesSize, int& memo_mask, const int limit)
    {
        /* memo参照 */
        if (g_memo[memo_mask] != -1)
            return g_memo[memo_mask];

        /* 部分集合のmemo参照 */
        int tmp_mask = memo_mask;
        while (tmp_mask) {
            const int lsb = tmp_mask & -tmp_mask;
            if (limit <= g_memo[memo_mask ^ lsb])
                return inf;
            tmp_mask ^= lsb;
        }

        /* dp初期化 */
        for (int bit = 1; bit < (1 << itemIndicesSize); ++bit) {
            for (int gfidx = 0; g_from[bit][gfidx] != -1; ++gfidx) {
                g_dp[bit][g_from[bit][gfidx]] = inf;
            }
        }

        /* 各荷物の場所の初期値 */
        for (int i = 0; i < itemIndicesSize; ++i) {
            const int &idx = itemIndices[i];
            g_dp[1 << i][i] = truckWeight * g_dist[officeIndex][idx];
            g_weight[1 << i] = truckWeight + g_itemsWeight[idx];
        }

        /* bitDP */
        int bit;
        for (bit = 1; bit < (1 << itemIndicesSize) - 1; ++bit) {
            int mm = 0;
            for (int gtidx = 0; g_to[bit][gtidx] < itemIndicesSize; ++gtidx) {
                const int &to = g_to[bit][gtidx];
                const int &tidx = itemIndices[to];
                const int nbit = bit | (1 << to);
                g_weight[nbit] = g_weight[bit] + g_itemsWeight[tidx];
                for (int gfidx = 0; g_from[bit][gfidx] != -1; ++gfidx) {
                    const int &from = g_from[bit][gfidx];
                    const int &fidx = itemIndices[from];
                    mm |= 1 << fidx;
                    g_dp[nbit][to] = std::min(g_dp[nbit][to], g_dp[bit][from] + g_weight[bit] * g_dist[fidx][tidx]);
                }
            }
            if (g_memo[mm] == -1) {
                int minCost = inf;
                for (int gfidx = 0; g_from[bit][gfidx] != -1; ++gfidx) {
                    const int &from = g_from[bit][gfidx];
                    minCost = std::min(minCost, g_dp[bit][from] + g_weight[bit] * g_dist[itemIndices[from]][officeIndex]);
                }
                g_memo[mm] = minCost;
            }
        }

        int minCost = inf;
        for (int from = 0; from < itemIndicesSize; ++from) {
            minCost = std::min(minCost, g_dp[bit][from] + g_weight[bit] * g_dist[itemIndices[from]][officeIndex]);
        }

        return g_memo[memo_mask] = minCost;
    }

} *solve;

/// プロコン問題環境を表します。
namespace hpc {

    //------------------------------------------------------------------------------
    /// 各ステージ開始時に呼び出されます。
    ///
    /// ここで、各ステージに対して初期処理を行うことができます。
    ///
    /// @param[in] aStage 現在のステージ。
    void Answer::Init(const Stage& aStage)
    {
        solve = new Solve(aStage);
    }

    //------------------------------------------------------------------------------
    /// 各配達時間帯開始時に呼び出されます。
    ///
    /// ここで、この時間帯に配達する荷物をトラックに積み込みます。
    /// どの荷物をトラックに積み込むかを決めて、引数の aItemGroup に対して
    /// setItem で荷物番号を指定して積み込んでください。
    ///
    /// @param[in] aStage 現在のステージ。
    /// @param[in] aItemGroup 荷物グループ。
    void Answer::InitPeriod(const Stage& aStage, ItemGroup& aItemGroup)
    {
        /* 荷物を登録 */
        const int period = aStage.period();
        for (int i = 0; i < g_eachItemIndices_size[period]; ++i) {
            aItemGroup.addItem(g_eachItemIndices[period][i]);
        }
    }

    //------------------------------------------------------------------------------
    /// 各ターンでの動作を返します。
    ///
    /// @param[in] aStage 現在ステージの情報。
    ///
    /// @return これから行う動作を表す Action クラス。
    Action Answer::GetNextAction(const Stage& aStage)
    {
        return g_action[g_action_size++];
    }

    //------------------------------------------------------------------------------
    /// 各配達時間帯終了時に呼び出されます。
    ///
    /// ここで、この時間帯の終了処理を行うことができます。
    ///
    /// @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)
    {
        //if (aStageState == StageState_Failed) {
        //    // 失敗したかどうかは、ここで検知できます。
        //}
        //else if (aStageState == StageState_TurnLimit) {
        //    // ターン数オーバーしたかどうかは、ここで検知できます。
        //}

        delete solve;
    }
}

//------------------------------------------------------------------------------
// EOF