kimiyukiさんの作品（ソースコード）

#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <functional>
#include <iostream>
#include <memory>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include "Answer.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = int(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
typedef long long ll;
template <class T, class U> inline void chmax(T & a, U const & b) { a = std::max<T>(a, b); }
template <class T, class U> inline void chmin(T & a, U const & b) { a = std::min<T>(a, b); }

//------------------------------------------------------------------------------
namespace hpc {

using namespace std;

typedef array<uint32_t, Parameter::OvenHeight> packed_oven_t;
packed_oven_t pack_oven(Oven const & oven) {
    static_assert (Parameter::OvenWidth < CHAR_BIT * sizeof(uint32_t), "");
    packed_oven_t a = {};
    REP (y, Parameter::OvenHeight) {
        REP (x, Parameter::OvenWidth) {
            if (oven.isAbleToPut(1, 1, Vector2i(x, y))) {
                a[y] |= 1u << x;
            }
        }
    }
    return a;
}

uint64_t hash_oven(Oven const & oven) {
    constexpr int H = Parameter::OvenHeight;
    constexpr int W = Parameter::OvenWidth;
#ifdef DEBUG
    // デバッグの都合で bitset を避けたい
    string s(H * W / CHAR_BIT, '\0');
    REP (y, H) REP (x, W) {
        if (oven.isAbleToPut(1, 1, Vector2i(x, y))) {
            int z = y * W + x;
            s[z / 8] |= 1u << (z % 8);
        }
    }
    return hash<string>()(s);
#else
    // ちょっとだけ速い気がする
    bitset<H * W> packed;
    REP (y, H) REP (x, W) {
        if (oven.isAbleToPut(1, 1, Vector2i(x, y))) {
            packed.set(y * W + x);
        }
    }
    return hash<bitset<H * W> >()(packed);
#endif
}

int get_oven_score(Oven const & oven) {
    constexpr int H = Parameter::OvenHeight;
    constexpr int W = Parameter::OvenWidth;
    array<array<int16_t, W>, H> packed = {};
    int score = 0;
    for (auto const & piece : oven.bakingPieces()) {
        int ly = piece.pos().y;
        int lx = piece.pos().x;
        int ry = ly + piece.height();
        int rx = lx + piece.width();
        int16_t t = piece.restRequiredHeatTurnCount();
        assert (t >= 1);
        REP3 (y, ly, ry) packed[y][lx] = t;
        REP3 (x, lx, rx) packed[ly][x] = t;
        if (ly == 0) score += t * (rx - lx);
        if (ry == H) score += t * (rx - lx);
        if (lx == 0) score += t * (ry - ly);
        if (rx == W) score += t * (ry - ly);
        score += 10 * piece.height() * piece.width();
    }
    for (auto const & piece : oven.bakingPieces()) {
        int ly = piece.pos().y;
        int lx = piece.pos().x;
        int ry = ly + piece.height();
        int rx = lx + piece.width();
        int16_t t = piece.restRequiredHeatTurnCount();
        if (rx < W) REP3 (y, ly, ry) {
            score += min(packed[y][rx], t);
        }
        if (ry < H) REP3 (x, lx, rx) {
            score += min(packed[ry][x], t);
        }
    }
    return score;
}

struct state_t {
    Oven oven;
    vector<pair<int, Action> > actions;
    uint8_t used;
    int turn;
    ll score;
};

Piece const & get_piece_from_action(Stage const & stage, Action const & action) {
    return stage.candidateLane(action.candidateLaneType()).pieces()[action.pieceIndex()];
}

bool is_intersect(Vector2i const & pos1, Piece const & piece1, Vector2i const & pos2, Piece const & piece2) {
    return Util::IsIntersect(
        pos1, piece1.width(), piece1.height(),
        pos2, piece2.width(), piece2.height());
}

shared_ptr<state_t> new_initial_state(Stage const & stage) {
    auto a = make_shared<state_t>();
    a->oven = stage.oven();
    a->used = 0;
    REP (i, Parameter::CandidatePieceCount) {
        auto const & piece = stage.candidateLane(CandidateLaneType_Large).pieces()[i];
        if (stage.turn() + piece.requiredHeatTurnCount() >= Parameter::GameTurnLimit) {
            a->used |= 1u << i;
        }
    }
    a->turn = stage.turn();
    a->score = 0;
    return a;
}

shared_ptr<state_t> new_next_state(shared_ptr<state_t> const & a, Stage const & stage, Action const & action) {
    auto b = make_shared<state_t>(*a);

    if (not action.isWaiting()) {  // 置く
        b->actions.emplace_back(b->turn, action);
        Piece piece = get_piece_from_action(stage, action);
        bool baked = b->oven.tryToBake(&piece, action.putPos());
        assert (baked);
        b->used |= 1u << action.pieceIndex();
        b->score += 100 * pow(piece.height() * piece.width(), 1.5);
    }

    // 進める
    b->turn += 1;
    b->oven.bakeAndDiscard();
    b->score += get_oven_score(b->oven);

    // 腐らせる
    REP (i, Parameter::CandidatePieceCount) if (not (b->used & (1u << i))) {
        auto const & piece = stage.candidateLane(CandidateLaneType_Large).pieces()[i];
        if (b->turn + piece.requiredHeatTurnCount() >= Parameter::GameTurnLimit) {
            b->used |= 1u << i;
        }
    }
    return b;
}

template <typename Func>
void iterate_all_puttable_pos(Oven const & oven, Piece const & piece, Func func) {
    constexpr int H = Parameter::OvenHeight;
    constexpr int W = Parameter::OvenWidth;
    array<array<char, W + 1>, H + 1> imos = {};
    for (auto const & baking : oven.bakingPieces()) {
        int ly = baking.pos().y;
        int lx = baking.pos().x;
        int ry = ly + baking.height();
        int rx = lx + baking.width();
        ly = max(0, ly - piece.height() + 1);
        lx = max(0, lx - piece.width() + 1);
        imos[ly][lx] += 1;
        imos[ly][rx] -= 1;
        imos[ry][lx] -= 1;
        imos[ry][rx] += 1;
    }
    REP (y, H - piece.height() + 1) {
        REP (x, W - piece.width() + 1) {
            imos[y    ][x + 1] += imos[y][x];
            imos[y + 1][x    ] += imos[y][x];
            imos[y + 1][x + 1] -= imos[y][x];
            if (not imos[y][x]) {
                func(Vector2i(x, y));
            }
        }
    }
}

bool operator == (Action const & a, Action const & b) {
    if (a.isWaiting() or b.isWaiting()) {
        return a.isWaiting() == b.isWaiting();
    } else {
        return make_tuple(a.candidateLaneType(), a.pieceIndex(), a.putPos())
            == make_tuple(b.candidateLaneType(), b.pieceIndex(), b.putPos());
    }
}
bool operator != (Action const & a, Action const & b) {
    return not (a == b);
}

vector<pair<int, Action> > do_large_beam_search(Stage const & stage) {
    constexpr int BEAM_DEPTH = 13;
    constexpr int BEAM_WIDTH = 5;
    static vector<shared_ptr<state_t> > cur, prv;
    static array<int, (1 << Parameter::CandidatePieceCount)> used_pieces = {};
    static unordered_set<uint64_t> used_oven;

    cur.push_back(new_initial_state(stage));
    shared_ptr<state_t> best = cur.front();
    for (int iteration = 0; iteration < BEAM_DEPTH; ++ iteration) {
        // 置いてみる
        cur.swap(prv);
        cur.clear();
        for (auto const & a : prv) {
            cur.push_back(new_next_state(a, stage, Action::Wait()));
            REP (i, Parameter::CandidatePieceCount) if (not (a->used & (1u << i))) {
                auto const & piece = stage.candidateLane(CandidateLaneType_Large).pieces()[i];
                iterate_all_puttable_pos(a->oven, piece, [&](Vector2i const & pos) {
                    auto action = Action::Put(CandidateLaneType_Large, i, pos);
                    cur.push_back(new_next_state(a, stage, action));
                });
            }
        }

        // 並べ替え
        sort(ALL(cur), [&](shared_ptr<state_t> const & a, shared_ptr<state_t> const & b) {
            return a->score > b->score;
        });
        if (best->score < cur.front()->score) {
            best = cur.front();
        }

        // 重複排除
        cur.swap(prv);
        cur.clear();
        for (auto const & a : prv) {
            if (used_pieces[a->used] >= 2) continue;
            uint64_t hash = hash_oven(a->oven);
            if (used_oven.count(hash)) continue;
            cur.push_back(a);
            used_pieces[a->used] += 1;
            used_oven.insert(hash);
            if ((int)cur.size() >= BEAM_WIDTH) break;
        }
        fill(ALL(used_pieces), 0);
        used_oven.clear();

        // 結果が確定してたら打ち切り
        if (not best->actions.empty() and best->actions.front().first == stage.turn()) {
            auto action = best->actions.front().second;
            bool all_same = true;
            for (auto const & a : cur) {
                if (a->actions.empty() or a->actions.front().second != action) {
                    all_same = false;
                    break;
                }
            }
            if (all_same) {
                break;
            }
        }
    }
    cur.clear();
    prv.clear();

    // 結果の取り出し
    return best->actions;
}

Action do_small_greedy(Stage const & stage, vector<pair<int, Action> > const & actions) {
    array<int, Parameter::CandidatePieceCount> order;
    iota(ALL(order), 0);
    sort(ALL(order), [&](int i, int j) {
        auto const & p = stage.candidateLane(CandidateLaneType_Small).pieces()[i];
        auto const & q = stage.candidateLane(CandidateLaneType_Small).pieces()[j];
        return p.height() * p.width() > q.height() * q.width();
    });
    for (int i : order) {
        auto const & piece = stage.candidateLane(CandidateLaneType_Small).pieces()[i];
        bool found = false;
        Vector2i found_pos;
        iterate_all_puttable_pos(stage.oven(), piece, [&](Vector2i const & pos) {
            if (found) return;

            // 大型クッキーの予定と整合するか確認
            for (auto const & it : actions) {
                if (stage.turn() + piece.requiredHeatTurnCount() < it.first) break;
                auto const & action = it.second;
                if (is_intersect(pos, piece, action.putPos(), get_piece_from_action(stage, action))) {
                    return;
                }
            }

            found = true;
            found_pos = pos;
        });

        if (found) {
            return Action::Put(CandidateLaneType_Small, i, found_pos);
        }
    }

    return Action::Wait();
}

class solver {
    packed_oven_t last_oven;

public:
    Stage const & stage;
    solver(Stage const & stage_)
            : stage(stage_) {
        last_oven = pack_oven(stage_.oven());
    }

    Action decide_next_action(Stage const & stage_) {
        assert (&stage == &stage_);

        // 状況が変わってないなら省略
        if (not stage_.oven().isEmpty()) {
            auto packed_oven = pack_oven(stage_.oven());
            if (packed_oven == last_oven) {
                return Action::Wait();
            }
            last_oven = packed_oven;
        }

        // 置けるやつがひとつもないなら省略
        bool is_puttable = false;
        for (auto lane_type : { CandidateLaneType_Large, CandidateLaneType_Small }) {
            REP (i, Parameter::CandidatePieceCount) {
                if (is_puttable) break;
                auto const & piece = stage.candidateLane(lane_type).pieces()[i];
                iterate_all_puttable_pos(stage.oven(), piece, [&](Vector2i const & pos) {
                    is_puttable = true;
                });
            }
        }
        if (not is_puttable) {
            return Action::Wait();
        }

        // 大型クッキーについてビームサーチ
        auto actions = do_large_beam_search(stage);
        if (not actions.empty() and actions.front().first == stage.turn()) {
            return actions.front().second;
        }

        // 小型クッキーは貪欲
        auto action = do_small_greedy(stage, actions);
        if (not action.isWaiting()) return action;

        return Action::Wait();
    }
};

solver *g_solver = nullptr;
#ifdef LOCAL
int g_stage = 0;
int g_score = 0;
#endif


//------------------------------------------------------------------------------
/// コンストラクタ。
/// @detail 最初のステージ開始前に実行したい処理があればここに書きます。
Answer::Answer()
{
}

//------------------------------------------------------------------------------
/// デストラクタ。
/// @detail 最後のステージ終了後に実行したい処理があればここに書きます。
Answer::~Answer()
{
}

//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出される処理。
/// @detail 各ステージに対する初期化処理が必要ならここに書きます。
/// @param aStage 現在のステージ。
void Answer::init(const Stage& aStage)
{
#ifdef LOCAL
    cerr << "[*] stage = " << (g_stage ++) << endl;
    g_score = 0;
#endif
    g_solver = new solver(aStage);
}

//------------------------------------------------------------------------------
/// このターンでの行動を指定する。
/// @detail 希望する行動を Action の static 関数で生成して return してください。
///         正常ではない行動を return した場合、何も起きません。
///         詳細は Action のヘッダを参照してください。
/// @param aStage 現在のステージ。
Action Answer::decideNextAction(const Stage& aStage)
{
#ifdef LOCAL
    for (auto const & piece : aStage.oven().lastBakedPieces()) {
        g_score += piece.score();
    }
    if (aStage.turn() % 50 == 0 or aStage.turn() >= 999) {
        cerr << "[*] turn = " << aStage.turn() << ": score = " << g_score << endl;
    }
#endif
    return g_solver->decide_next_action(aStage);
}

//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出される処理。
/// @detail 各ステージに対する終了処理が必要ならここに書きます。
/// @param aStage 現在のステージ。
void Answer::finalize(const Stage& aStage)
{
    delete g_solver;
    g_solver = nullptr;
}

} // namespace
// EOF