//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright Copyright (c) 2018 HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください。
//------------------------------------------------------------------------------
#include "Answer.hpp"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
//------------------------------------------------------------------------------
namespace hpc {
#define ll long long
// 生地に関する情報
typedef struct {
CandidateLaneType lane;
int index;
int score;
} PInfo;
// 配置され、箱と化してしまった生地
typedef struct {
int x1; // 最小値
int y1;
int z1;
int x2; // 最大値
int y2;
int z2;
PInfo p;
} Box;
// 配置前の生地
typedef struct {
int width;
int height;
int depth; // 焼き時間+1
PInfo p;
} P;
float bestScore; // 試した中で最も良いスコア
int bestOrder[8]; // 試した中で最も良いスコアを出した順列
int lastLargeOrder[8]; // 前回の大きい生地の順列
int largeOrderSkipCount; // 次に大きい生地を配置するまでのターン数
int lastSmallOrder[8]; // 前回の小さい生地の順列
int smallOrderSkipCount; // 次に小さい生地を配置するまでのターン数
int turnCount; // 現在のステージ内のターン数#
int compCountLarge; // 大きい生地の順列を計算した回数
int compCountSmall; // 小さい生地の順列を計算した回数
bool stageNearsEnd; // ステージ終盤か？
bool stageNearsEndLarge; // 大きい生地用のステージ終盤フラグ
bool stageNearsEndSmall; // 小さい生地用のステージ終盤フラグ
int maxScoreEvaluateDepth; // 評価関数の有効範囲
// 次のBL点の候補のZ座標を探す
inline int nextZ(const Box *bs, int numBs, int z) {
int minZ = 10000;
for (int i = 0; i < numBs; i++) {
if (bs[i].z2 > z && bs[i].z2 < minZ) {
minZ = bs[i].z2;
}
}
return minZ;
}
// y方向のマスク用定数
const ll ymask3[8] = {
0x0000000000000000ll, 0x00000000001fffffll,
0x000003ffffe00000ll, 0x000003ffffffffffll,
0x7ffffc0000000000ll, 0x7ffffc00001fffffll,
0x7fffffffffe00000ll, 0x7fffffffffffffffll
};
// 21x21のbitboardの特定の範囲を1で埋める
static inline void fill(ll *board, int x, int y, int w, int h) {
// 21x21 bitboard
//
// 0 -- x+
// |
// y+
//
// index bit lower <- -> higher
// 0 1-21 000000000000000000000
// 0 22-42 000000000000000000000
// 0 43-63 000000000000000000000
// 1 1-21 000000000000000000000
// 1 22-42 000000000000000000000
// 1 43-63 000000000000000000000
// 2 1-21 000000000000000000000
// 2 22-42 000000000000000000000
// 2 43-63 000000000000000000000
// 3 1-21 000000000000000000000
// 3 22-42 000000000000000000000
// 3 43-63 000000000000000000000
// 4 1-21 000000000000000000000
// 4 22-42 000000000000000000000
// 4 43-63 000000000000000000000
// 5 1-21 000000000000000000000
// 5 22-42 000000000000000000000
// 5 43-63 000000000000000000000
// 6 1-21 000000000000000000000
// 6 22-42 000000000000000000000
// 6 43-63 000000000000000000000
ll xmask = (1ll << (x + w)) - (1ll << x);
ll ymask = (1ll << (y + h)) - (1ll << y);
xmask = xmask | xmask << 21 | xmask << 42;
board[0] |= xmask & ymask3[ymask & 7];
board[1] |= xmask & ymask3[ymask >> 3 & 7];
board[2] |= xmask & ymask3[ymask >> 6 & 7];
board[3] |= xmask & ymask3[ymask >> 9 & 7];
board[4] |= xmask & ymask3[ymask >> 12 & 7];
board[5] |= xmask & ymask3[ymask >> 15 & 7];
board[6] |= xmask & ymask3[ymask >> 18 & 7];
}
// ビット数カウント
inline int popcount(ll t) {
t = (t & 0x5555555555555555ll) + (t >> 1 & 0x5555555555555555ll);
t = (t & 0x3333333333333333ll) + (t >> 2 & 0x3333333333333333ll);
t = (t & 0x0f0f0f0f0f0f0f0fll) + (t >> 4 & 0x0f0f0f0f0f0f0f0fll);
t = (t & 0x00ff00ff00ff00ffll) + (t >> 8 & 0x00ff00ff00ff00ffll);
t = (t & 0x0000ffff0000ffffll) + (t >> 16 & 0x0000ffff0000ffffll);
t = (t & 0x00000000ffffffffll) + (t >> 32 & 0x00000000ffffffffll);
return (int) t;
}
// 最初に出現する0の位置
inline int indexOfZero(ll t) {
return popcount(t ^ (t + 1)) - 1;
}
// 指定されたz座標の範囲でのBL点を見つける
void findBL(const Box *bs, int numBs, int z1, int z2, int w, int h, int &xOut, int &yOut) {
ll board[7];
board[0] = 0;
board[1] = 0;
board[2] = 0;
board[3] = 0;
board[4] = 0;
board[5] = 0;
board[6] = 0;
// 壁のNFPを埋める
fill(board, 21 - w, 0, w, 21);
fill(board, 0, 21 - h, 21, h);
// z方向に重なっている箱のNFPを埋める
for (int i = 0; i < numBs; i++) {
const Box &b = bs[i];
if (b.z1 < z2 && z1 < b.z2) {
// nfpX, nfpY は負になりうる
int nfpX = b.x1 + 1 - w;
int nfpY = b.y1 + 1 - h;
// 負になったら0にする
nfpX &= -(~nfpX >> 31 & 1);
nfpY &= -(~nfpY >> 31 & 1);
int nfpW = b.x2 - nfpX;
int nfpH = b.y2 - nfpY;
// NFPを埋める
ll xmask = (1ll << (nfpX + nfpW)) - (1ll << nfpX);
ll ymask = (1ll << (nfpY + nfpH)) - (1ll << nfpY);
xmask = xmask | xmask << 21 | xmask << 42;
board[0] |= xmask & ymask3[ymask & 7];
board[1] |= xmask & ymask3[ymask >> 3 & 7];
board[2] |= xmask & ymask3[ymask >> 6 & 7];
board[3] |= xmask & ymask3[ymask >> 9 & 7];
board[4] |= xmask & ymask3[ymask >> 12 & 7];
board[5] |= xmask & ymask3[ymask >> 15 & 7];
board[6] |= xmask & ymask3[ymask >> 18 & 7];
}
}
// 最初に0になっているビットを発見して場所を計算する
for (int i = 0; i < 7; i++) {
ll b = board[i];
if (b != 0x7fffffffffffffffll) {
int x = indexOfZero(b);
xOut = x % 21;
yOut = x / 21 + i * 3;
return;
}
}
xOut = -1;
yOut = -1;
}
// 生地を配置する場所を探索する
void findPos(Box *bs, int &numBs, const P &p, bool *ng, int &xOut, int &yOut, int &zOut, int pieceIndex, int numPuts) {
int z = 0;
while (true) {
// z値チェック
while (ng[z]) {
z++; // 既に置いてある
}
int posX = 0;
int posY = 0;
// BL点を探す
findBL(bs, numBs, z, z + p.depth, p.width, p.height, posX, posY);
// 置ける場所が見つかったか？
if (posX != -1) {
xOut = posX;
yOut = posY;
zOut = z;
return;
}
z = nextZ(bs, numBs, z); // 次のzを探す
}
}
// 置かれたピースから終盤のスコアを計算する
inline float computeScoreNearEnd(const Box *bs, int numBs, int evaluateLastNPieces) {
// 末尾から evaluateLastNPieces 個だけを評価
float score = 0;
for (int i = numBs - evaluateLastNPieces; i < numBs; i++) {
const Box &b = bs[i];
if (b.z2 + turnCount - 1 <= 1000) { // 1000ターン以内に焼きあがるものだけ加算
score += b.p.score;
}
}
// 生地が収まり切らなかったときに終盤と判定されるが、生地が全て収まる方が好ましいためスコアを小さくする
return score * 0.01f;
}
// 特定の範囲にあるスコアを計算する
inline float computeScoreIn(const Box *bs, int numBs, int minZ, int maxZ, int evaluateLastNPieces) {
float res = 0;
// 末尾から evaluateLastNPieces 個だけを評価
for (int i = numBs - evaluateLastNPieces; i < numBs; i++) {
const Box &b = bs[i];
int z1 = b.z1;
int z2 = b.z2;
if (z2 + turnCount - 1 <= 1000 && z1 < maxZ && minZ < z2) { // 1000ターン以内に焼き上がり、かつ一部でも重なっていたら
if (z1 < minZ) z1 = minZ;
if (z2 > maxZ) z2 = maxZ;
// スコアの最大化は充填率の最大化と見なせるため、体積をスコアとする
int volume = (b.x2 - b.x1) * (b.y2 - b.y1) * (z2 - z1);
res += volume;
}
}
return res;
}
// 置かれたピースからこの先見込めるスコアを計算する
float computeScore(const Box *bs, int numBs, int evaluateLastNPieces, bool nearEnd) {
if (nearEnd) {
return computeScoreNearEnd(bs, numBs, evaluateLastNPieces); // ステージ終盤のスコア計算を行う
}
#define NUM_DIV 6
int maxZ = maxScoreEvaluateDepth;
int zs[NUM_DIV + 1];
float ws[NUM_DIV];
for (int i = 0; i < NUM_DIV; i++) {
float t = 1.0f - i * 1.0f / NUM_DIV;
zs[i + 1] = maxZ * (i + 1) / NUM_DIV; // 0～maxZをNUM_DIV分割し、
ws[i] = t; // 重みを設定する
}
float score = 0;
for (int i = 0; i < NUM_DIV; i++) {
// 分割された各範囲に対して重みを付けて加算
score += computeScoreIn(bs, numBs, zs[i], zs[i + 1], evaluateLastNPieces) * ws[i];
}
return score;
#undef NUM_DIV
}
void tryBruteImpl(Box *bs, int &numBs, const P *ps, int numPs, bool* ng, int *pieceToOrder, int idx, int numPuts, int prevZ, int maxDepthToBrute, int unableToPutCount) {
bool seemsToBeUnableToPutPiecesAnyMore = unableToPutCount >= 3; // 3つ以上生地が置けなければもう置けないと判断して停止
bool allPiecesPut = idx == numPs; // 全部置いたら停止
if (allPiecesPut || seemsToBeUnableToPutPiecesAnyMore) {
bool nearEnd = unableToPutCount >= 3; // 3つ以上置けなかった場合はステージ終盤と見なす
stageNearsEnd |= nearEnd; // ステージ終盤に突入したフラグを立てる
float score = computeScore(bs, numBs, numPuts, nearEnd); // 暫定スコア計算
// 最高スコアの更新処理
if (score > bestScore) {
bestScore = score;
// pieceToOrder を orderToPiece に変換する
// 実際に配置するピースは8個より少なくても
// インデックスが0～7まであるのでループは8回回す必要がある
int orderToPiece[8];
for (int i = 0; i < 8; i++) {
orderToPiece[i] = -1;
}
for (int i = 0; i < 8; i++) {
if (pieceToOrder[i] != -1) orderToPiece[pieceToOrder[i]] = i;
}
// 順列更新
for (int i = 0; i < 8; i++) {
bestOrder[i] = orderToPiece[i];
}
}
return;
}
// 全探索中か？
bool bruteSearch = idx < maxDepthToBrute;
// idx番目に置くピースを選ぶ
for (int i = 0; i < numPs; i++) {
int pieceIndex = i;
const P &p = ps[pieceIndex];
if (pieceToOrder[pieceIndex] != -1) continue; // 使用済み
// 次置ける場所を探す
int x = 0;
int y = 0;
int z = 0;
findPos(bs, numBs, p, ng, x, y, z, pieceIndex, numPuts);
bool doPut = z + p.depth + turnCount - 1 <= 1000; // 制限を突破したら置かない
if (doPut) {
// 試しに置く
pieceToOrder[pieceIndex] = numPuts;
ng[z] = true;
bs[numBs].x1 = x;
bs[numBs].y1 = y;
bs[numBs].z1 = z;
bs[numBs].x2 = x + p.width;
bs[numBs].y2 = y + p.height;
bs[numBs].z2 = z + p.depth;
bs[numBs].p = p.p;
numBs++;
numPuts++;
} else {
// 置けなかった
pieceToOrder[pieceIndex] = -1;
unableToPutCount++;
}
// 再帰的に計算
int nextZ = doPut ? z : prevZ; // ※最終的にはこの変数は使われなかった
tryBruteImpl(bs, numBs, ps, numPs, ng, pieceToOrder, idx + 1, numPuts, nextZ, maxDepthToBrute, unableToPutCount);
if (doPut) {
// 元に戻す
pieceToOrder[pieceIndex] = -1;
ng[z] = false;
numBs--;
numPuts--;
} else {
unableToPutCount--;
}
if (!bruteSearch) break; // 許容深さを超えたら全探索しない
}
}
// 指定の深さまでの全探索で最適な配置を計算する
inline void tryBrute(Box *bs, int &numBs, const P *ps, int numPs, bool* ng, int maxDepthToBrute) {
int order[8];
for (int i = 0; i < 8; i++) order[i] = -1;
tryBruteImpl(bs, numBs, ps, numPs, ng, order, 0, 0, 0, maxDepthToBrute, 0);
}
// 事前計算された順列に従って生地を配置する
void putByOrder(Box *bs, int &numBs, P *ps, int numPs, bool* ng, const int *orderToPiece) {
int numPuts = 0;
for (int i = 0; i < numPs; i++) {
int pieceIndex = orderToPiece[i];
if (pieceIndex == -1) continue; // i番目には無が置かれた
P &p = ps[pieceIndex]; // i番目に置かれたのは pieceIndex 番目のピース
// 次置ける場所を探す
int x = 0;
int y = 0;
int z = 0;
findPos(bs, numBs, p, ng, x, y, z, pieceIndex, numPuts);
// 置く
numPuts++;
ng[z] = true;
bs[numBs].x1 = x;
bs[numBs].y1 = y;
bs[numBs].z1 = z;
bs[numBs].x2 = x + p.width;
bs[numBs].y2 = y + p.height;
bs[numBs].z2 = z + p.depth;
bs[numBs].p = p.p;
numBs++;
}
}
Answer::Answer() {
}
Answer::~Answer() {
}
void Answer::init(const Stage& aStage) {
largeOrderSkipCount = 0;
smallOrderSkipCount = 0;
// 初期の順列
for (int i = 0; i < 8; i++) {
lastLargeOrder[i] = i;
lastSmallOrder[i] = i;
}
turnCount = 0;
compCountLarge = 0;
compCountSmall = 0;
stageNearsEnd = false;
stageNearsEndLarge = false;
stageNearsEndSmall = false;
}
Action Answer::decideNextAction(const Stage& aStage) {
typedef Vector2i v2;
auto slane = CandidateLaneType_Small;
auto llane = CandidateLaneType_Large;
const CandidatePieces &sps = aStage.candidateLane(slane).pieces();
const CandidatePieces &lps = aStage.candidateLane(llane).pieces();
const Oven &ov = aStage.oven();
Box bs[20 * 20 + 8 + 8 + 10]; // 空間内の箱
int numBs = 0; // 配置済みの箱の数
P lb[8]; // 手持ちの大きい生地
P sb[8]; // 手持ちの小さい生地
turnCount++;
// オーブンに既にあるやつを調べる
{
const OvenedPieces &ovps = ov.bakingPieces();
int num = ovps.count();
for (int i = 0; i < num; i++) {
const Piece &p = ovps[i];
v2 pos = p.pos();
int width = p.width();
int height = p.height();
int depth = p.restRequiredHeatTurnCount() + 1; // 焼きあがってから回収までに1ターンかかる
bs[numBs].x1 = pos.x;
bs[numBs].y1 = pos.y;
bs[numBs].z1 = 0;
bs[numBs].x2 = pos.x + width;
bs[numBs].y2 = pos.y + height;
bs[numBs].z2 = depth;
bs[numBs].p.index = -1;
bs[numBs].p.score = 0;
numBs++;
}
}
// 手持ちを調べる
{
for (int i = 0; i < 8; i++) {
const Piece &p = lps[i];
lb[i].width = p.width();
lb[i].height = p.height();
lb[i].depth = p.requiredHeatTurnCount() + 1;
lb[i].p.lane = llane;
lb[i].p.index = i;
lb[i].p.score = p.score();
}
for (int i = 0; i < 8; i++) {
const Piece &p = sps[i];
sb[i].width = p.width();
sb[i].height = p.height();
sb[i].depth = p.requiredHeatTurnCount() + 1;
sb[i].p.lane = slane;
sb[i].p.index = i;
sb[i].p.score = p.score();
}
}
bool ng[1000]; // 1ターンに生地を1枚しか置けないため、既に置いたzはtrueにしておく
for (int i = 0; i < 1000; i++) ng[i] = false;
// ------------------------------------------------------------------
// 大きい生地の計算
// ------------------------------------------------------------------
bool doPutSmall = true;
maxScoreEvaluateDepth = 64; // スコアが高くなるよう調整
{
// スコアと順列初期化
bestScore = 0; for (int i = 0; i < 8; i++) bestOrder[i] = -1;
if (largeOrderSkipCount > 0) {
// 大きい生地に変化なし、前回のを使う
putByOrder(bs, numBs, lb, 8, ng, lastLargeOrder);
largeOrderSkipCount--;
} else {
// 時間内に収まるように深さを調整しつつ探索
int bruteSearchDepth;
if (stageNearsEndLarge) {
// 最後は深さ5で探索
bruteSearchDepth = 5;
} else {
// 4回に1回は深さ5で探索
bruteSearchDepth = compCountLarge % 4 == 0 ? 5 : 4;
}
stageNearsEnd = false;
tryBrute(bs, numBs, lb, 8, ng, bruteSearchDepth);
putByOrder(bs, numBs, lb, 8, ng, bestOrder);
stageNearsEndLarge |= stageNearsEnd;
// 順番を記憶
for (int i = 0; i < 8; i++) {
lastLargeOrder[i] = bestOrder[i];
}
// 最も下にある箱を探す
int minZ = 10000000;
for (int i = 0; i < numBs; i++) {
Box &b = bs[i];
if (b.p.index != -1 && b.z1 < minZ) {
minZ = b.z1;
}
}
// 今後minZ回は新しい生地が補給されない
largeOrderSkipCount = minZ;
// 小さい生地も配置し直す
smallOrderSkipCount = 0;
compCountLarge++;
}
}
// ------------------------------------------------------------------
// 小さい生地の計算
// ------------------------------------------------------------------
maxScoreEvaluateDepth = 46; // スコアが高くなるよう調整
if (doPutSmall) {
// スコアと順列初期化
bestScore = 0; for (int i = 0; i < 8; i++) bestOrder[i] = -1;
if (smallOrderSkipCount > 0) {
// 小さい生地に変化なし、前回のを使う
putByOrder(bs, numBs, sb, 8, ng, lastSmallOrder);
smallOrderSkipCount--;
} else {
// 時間内に収まるように深さを調整しつつ探索
int bruteSearchDepth;
if (stageNearsEndSmall) {
// 最後は深さ5で探索
bruteSearchDepth = 5;
} else {
// 4回に1回は深さ3で探索
bruteSearchDepth = compCountSmall % 4 == 0 ? 3 : 2;
}
stageNearsEnd = false;
tryBrute(bs, numBs, sb, 8, ng, bruteSearchDepth);
putByOrder(bs, numBs, sb, 8, ng, bestOrder);
stageNearsEndSmall |= stageNearsEnd;
// 順番を記憶
for (int i = 0; i < 8; i++) {
lastSmallOrder[i] = bestOrder[i];
}
// 最も下にある箱を探す
int minZ = 10000000;
for (int i = 0; i < numBs; i++) {
Box &b = bs[i];
if (b.p.index != -1 && b.z1 < minZ) {
minZ = b.z1;
}
}
// 今後minZ回は新しい生地が補給されない
smallOrderSkipCount = minZ;
compCountSmall++;
}
}
Action action = Action::Wait();
// 今のターンに置くべき生地を探す
for (int i = 0; i < numBs; i++) {
Box &b = bs[i];
if (b.z1 == 0 && b.p.index != -1) { // z座標が0の生地があれば、それが今のターンに置くべき生地
action = Action::Put(b.p.lane, b.p.index, v2(b.x1, b.y1));
break;
}
}
return action;
}
void Answer::finalize(const Stage& aStage) {
}
} // namespace
// EOF