//------------------------------------------------------------------------------
/// @file
/// @author ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright Copyright (c) 2018 HAL Laboratory, Inc.
/// @attention このファイルの利用は、同梱のREADMEにある
/// 利用条件に従ってください。
//------------------------------------------------------------------------------
#include "Answer.hpp"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define DEAPTH 7
//------------------------------------------------------------------------------
namespace hpc {
struct LargePiecesOnLane {
Piece pieces[8];
int timeStartBaking[8];
Vector2i putPos[8];
int nextBakingId;
};
bool newLargeCame = true;
LargePiecesOnLane largePiecePlan;
int setMapsGlobal[8][20][20] = {};
int wallMapGlobal[20][20] = {};
LargePiecesOnLane setLargePlan(const Stage& aStage, LargePiecesOnLane formerPlan);
void bestOrder(const Stage& aStage, LargePiecesOnLane largeLane, Array<int, 8> pieceIndexes,
int time, LargePiecesOnLane& bestLargeLane, int& bestTime, int deapth, int totalTime);
void setMaps(const Stage& aStage, LargePiecesOnLane largeLane);
void wallMap(const Stage& aStage);
void setLargeFuture2(const Stage& aStage, LargePiecesOnLane& largeLane, int pieceIndex, int& time);
int byTheWall(Piece piece, Vector2i pos, int wallMap[20][20], int time);
void wallShift(const Stage& aStage, LargePiecesOnLane& largeLane, int index);
void setSmall(const Stage& aStage, LargePiecesOnLane largeLane, int& index, Vector2i& putPos);
//------------------------------------------------------------------------------
/// コンストラクタ。
/// @detail 最初のステージ開始前に実行したい処理があればここに書きます。
Answer::Answer()
{
}
//------------------------------------------------------------------------------
/// デストラクタ。
/// @detail 最後のステージ終了後に実行したい処理があればここに書きます。
Answer::~Answer()
{
}
//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出される処理。
/// @detail 各ステージに対する初期化処理が必要ならここに書きます。
/// @param aStage 現在のステージ。
void Answer::init(const Stage& aStage)
{
newLargeCame = true;
}
//------------------------------------------------------------------------------
/// このターンでの行動を指定する。
/// @detail 希望する行動を Action の static 関数で生成して return してください。
/// 正常ではない行動を return した場合、何も起きません。
/// 詳細は Action のヘッダを参照してください。
/// @param aStage 現在のステージ。
Action Answer::decideNextAction(const Stage& aStage)
{
int pieceIndex = 0;
if (aStage.turn() % 100 == 0) std::cerr << "・";
Vector2i putPos;
//largePicePlanにターン経過を反映
for (int i = 0; i < 8; i++) {
largePiecePlan.timeStartBaking[i] --;
}
//クッキーの壁情報の更新
wallMap(aStage);
// 大きいクッキーの配置順序を確定
if (newLargeCame) {
largePiecePlan = setLargePlan(aStage, largePiecePlan);
newLargeCame = false;
}
//即座に配置できる大きいクッキーがあれば、配置する
pieceIndex = largePiecePlan.nextBakingId;
if (largePiecePlan.timeStartBaking[pieceIndex] == 0) {
newLargeCame = true;
return Action::Put(CandidateLaneType_Large, pieceIndex, largePiecePlan.putPos[largePiecePlan.nextBakingId]);
}
// 配置できないなら、小さいクッキーを配置
//しかし大きいクッキーを今後焼くための領域は避ける
setSmall(aStage, largePiecePlan, pieceIndex, putPos);
if (pieceIndex >= 0) return Action::Put(CandidateLaneType_Small, pieceIndex, putPos);
//このターンは何もしない
return Action::Wait();
}
//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出される処理。
/// @detail 各ステージに対する終了処理が必要ならここに書きます。
/// @param aStage 現在のステージ。
void Answer::finalize(const Stage& aStage)
{
}
LargePiecesOnLane setLargePlan(const Stage& aStage, LargePiecesOnLane formerPlan) {
//初期化処理
int time = 0;
LargePiecesOnLane largeLane;
Array<int, 8> pieceIndexes;
pieceIndexes.clear();
for (int i = 0; i < 8; i++) {
largeLane.pieces[i] = aStage.candidateLane(CandidateLaneType_Large).pieces()[i];
largeLane.putPos[i] = Vector2i(0, 0);
largeLane.timeStartBaking[i] = 1000;
if (aStage.turn() + largeLane.pieces[i].requiredHeatTurnCount() < 1000) {
pieceIndexes.add(i);
}
}
//基準となる配置順序の設定
LargePiecesOnLane bestLargeLane = largeLane;
int bestTime = 10000;
int deapth = DEAPTH;
setMaps(aStage, largeLane);
bestOrder(aStage, largeLane, pieceIndexes, time, bestLargeLane, bestTime, Math::Min(deapth, pieceIndexes.count()), 0);
Array<int, 8> nextBakingIds;
nextBakingIds.clear();
//timeStartBakingを昇順にするid列を取得
for (int i = 0; i < 8; i++) {
Array<int, 8> copyIds = nextBakingIds;
nextBakingIds.clear();
while (1) {
if (copyIds.count() == 0) {
if (nextBakingIds.count() == i) nextBakingIds.add(i);
break;
}
if (bestLargeLane.timeStartBaking[copyIds[0]] > bestLargeLane.timeStartBaking[i]) {
nextBakingIds.add(i);
while (copyIds.count() > 0) {
nextBakingIds.add(copyIds[0]);
copyIds.erase(0);
}
break;
}
nextBakingIds.add(copyIds[0]);
copyIds.erase(0);
}
}
//可能なら、クッキーを壁に寄せる
for (int i = 7; i >= 0; i--) wallShift(aStage, bestLargeLane, nextBakingIds[i]);
bestLargeLane.nextBakingId = nextBakingIds[0];
return bestLargeLane;
}
//並び替え対象→largeLane
//pieceIndexesの初期値は[0,1,2,3,4,5,6,7]
//置き始める時刻→time
//bestLargeLaneに効率の良い配置方法が格納されます
//bestTimeに生地が焼きあがるまでの時間の総和が格納されます
//探索の深さ→deapth
void bestOrder(const Stage& aStage, LargePiecesOnLane largeLane, Array<int, 8> pieceIndexes,
int time, LargePiecesOnLane& bestLargeLane, int& bestTime, int deapth, int totalTime) {
if (deapth == 1) {
int ignoredPieces = 0;
bool ignoredAll = false;
for (int i = 0; i < pieceIndexes.count(); i++) {
LargePiecesOnLane mlargeLane = largeLane;
int mtime = time;
int mtotalTime = totalTime;
//間に合わないクッキーは無視
if (aStage.turn() + time + mlargeLane.pieces[pieceIndexes[i]].requiredHeatTurnCount() >= 1000) {
ignoredPieces++;
if (ignoredAll) {
}
else {
if (ignoredPieces == pieceIndexes.count() - 1) {
ignoredAll = true;
i = -1;
continue;
}
else {
continue;
}
}
}
setLargeFuture2(aStage, mlargeLane, pieceIndexes[i], mtime);
if (aStage.turn() + mtime + mlargeLane.pieces[pieceIndexes[i]].requiredHeatTurnCount() >= 1000) {
mtotalTime += 100;
mlargeLane.timeStartBaking[pieceIndexes[i]] = 1000;
}
//枝刈り
if (totalTime + deapth * (mtime * 2 + deapth - 1) / 2 > bestTime) {
continue;
}
Array<int, 8> newIndexes = pieceIndexes;
newIndexes.erase(i);
mtotalTime += mtime;
if (mtotalTime < bestTime) {
bestLargeLane = mlargeLane;
bestTime = mtotalTime;
}
}
}
else {
//std::cerr << "->";
int ignoredPieces = 0;
bool ignoredAll = false;
for (int i = 0; i < pieceIndexes.count(); i++) {
int mbestTime = bestTime;
LargePiecesOnLane mbestLargeLane;
LargePiecesOnLane mlargeLane = largeLane;
int mtime = time;
int mtotalTime = totalTime;
//間に合わないクッキーは無視
if (aStage.turn() + time + mlargeLane.pieces[pieceIndexes[i]].requiredHeatTurnCount() >= 1000) {
ignoredPieces++;
if (ignoredAll) {
}
else {
if (ignoredPieces == pieceIndexes.count() - 1) {
ignoredAll = true;
i = -1;
continue;
}
else {
continue;
}
}
}
setLargeFuture2(aStage, mlargeLane, pieceIndexes[i], mtime);
if (aStage.turn() + mtime + mlargeLane.pieces[pieceIndexes[i]].requiredHeatTurnCount() >= 1000) {
mtotalTime += 100;
mlargeLane.timeStartBaking[pieceIndexes[i]] = 1000;
}
//枝刈り
if (totalTime + deapth * (mtime * 2 + deapth - 1) / 2 > bestTime) {
continue;
}
//再帰呼び出し
Array<int, 8> newIndexes = pieceIndexes;
newIndexes.erase(i);
mtotalTime += mtime;
bestOrder(aStage, mlargeLane, newIndexes, mtime + 1, mbestLargeLane, mbestTime, deapth - 1, mtotalTime);
if (mbestTime < bestTime) {
bestLargeLane = mbestLargeLane;
bestTime = mbestTime;
}
}
}
}
//ovenにいまあるクッキーを考慮したときに、各点に関してクッキーを置けるようになる時刻を記録
void setMaps(const Stage& aStage, LargePiecesOnLane largeLane) {
int setMaps[8][20][20] = {};
for (int index = 0; index < 8; index++) {
Piece piece = largeLane.pieces[index];
for (const auto& bakingPiece : aStage.oven().bakingPieces()) {
int xRangeMin = Math::Max(0, bakingPiece.pos().x - piece.width() + 1);
int xRangeMax = Math::Min(21 - piece.width(), bakingPiece.pos().x + bakingPiece.width());
int yRangeMin = Math::Max(0, bakingPiece.pos().y - piece.height() + 1);
int yRangeMax = Math::Min(21 - piece.height(), bakingPiece.pos().y + bakingPiece.height());
int restCount = bakingPiece.restRequiredHeatTurnCount() + 1;
for (int i = xRangeMin; i < xRangeMax; i++) {
for (int j = yRangeMin; j < yRangeMax; j++) {
if (setMaps[index][i][j] < restCount) setMaps[index][i][j] = restCount;
}
}
}
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
setMapsGlobal[index][i][j] = setMaps[index][i][j];
}
}
}
return;
}
//ovenにいまあるクッキーを考慮したときに、壁となるマスを記録
void wallMap(const Stage& aStage) {
int wallMap[20][20] = {};
for (const auto& bakingPiece : aStage.oven().bakingPieces()) {
for (int i = bakingPiece.pos().x; i < bakingPiece.pos().x + bakingPiece.width(); i++) {
for (int j = bakingPiece.pos().y; j < bakingPiece.pos().y + bakingPiece.height(); j++) {
wallMap[i][j] = bakingPiece.restRequiredHeatTurnCount() + 1;
}
}
}
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
wallMapGlobal[i][j] = wallMap[i][j];
}
}
}
//aStage→現在のステージ
//largeLane→クッキーの配置計画(piece[pieceIndex]の配置を踏まえて更新されます)
//pieceIndex→配置対象となるクッキーのId
//time→現在時刻(クッキーを配置できた時刻に更新されます)
void setLargeFuture2(const Stage& aStage, LargePiecesOnLane& largeLane, int pieceIndex, int& time) {
largeLane.timeStartBaking[pieceIndex] = 1000;
auto& piece = largeLane.pieces[pieceIndex];
int setMap[20][20] = {};
int wallMap[20][20] = {};
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
setMap[i][j] = setMapsGlobal[pieceIndex][i][j];
wallMap[i][j] = wallMapGlobal[i][j];
}
}
int xRangeMin = 0;
int xRangeMax = 20;
int yRangeMin = 0;
int yRangeMax = 20;
int restCount = 0;
for (int k = 0; k < 8; k++) {
Piece bakingPiece = largeLane.pieces[k];
Vector2i bakingPos = largeLane.putPos[k];
if (largeLane.timeStartBaking[k] < time &&
largeLane.timeStartBaking[k] + bakingPiece.requiredHeatTurnCount() >= time &&
k != pieceIndex) {
//配置予定のクッキーを考慮したsetMap生成
xRangeMin = Math::Max(0, bakingPos.x - piece.width() + 1);
xRangeMax = Math::Min(21 - piece.width(), bakingPos.x + bakingPiece.width());
yRangeMin = Math::Max(0, bakingPos.y - piece.height() + 1);
yRangeMax = Math::Min(21 - piece.height(), bakingPos.y + bakingPiece.height());
restCount = largeLane.timeStartBaking[k] + bakingPiece.requiredHeatTurnCount() + 1;
for (int i = xRangeMin; i < xRangeMax; i++) {
for (int j = yRangeMin; j < yRangeMax; j++) {
if (setMap[i][j] < restCount) setMap[i][j] = restCount;
}
}
//配置予定のクッキーを考慮したwallMap生成
for (int i = bakingPiece.pos().x; i < bakingPiece.pos().x + bakingPiece.width(); i++) {
for (int j = bakingPiece.pos().y; j < bakingPiece.pos().y + bakingPiece.height(); j++) {
wallMap[i][j] = restCount;
}
}
}
}
int bestScore = -1;
Array<Vector2i, 400> settablePos;
settablePos.clear();
int waitTime = 1000;
//配置可能となる時刻が最小となる点を全て見つける
for (int i = 0; i < 20 - piece.width() + 1; i++) {
for (int j = 0; j < 20 - piece.height() + 1; j++) {
int settableTime = Math::Max(setMap[i][j], time);
if (settableTime < waitTime) {
settablePos.clear();
settablePos.add(Vector2i(i, j));
waitTime = settableTime;
}
else if (settableTime == waitTime) {
settablePos.add(Vector2i(i, j));
}
}
}
//より壁沿いにあるものを抽出
for (Vector2i pos : settablePos) {
int score = byTheWall(piece, pos, wallMap, waitTime);
if (score > bestScore) {
largeLane.putPos[pieceIndex] = pos;
bestScore = score;
}
}
largeLane.timeStartBaking[pieceIndex] = waitTime;
time = waitTime;
return;
}
//いかに壁沿いに配置できたかを評価する関数
int byTheWall(Piece piece, Vector2i pos, int wallMap[20][20], int time) {
int score = 0;
if (pos.x == 0) score += piece.height();
else {
for (int i = 0; i < piece.height();i++) {
if (wallMap[pos.x - 1][pos.y + i] > time + piece.requiredHeatTurnCount()) score++;
}
}
if (pos.x == 20 - piece.width()) score += piece.height();
else {
for (int i = 0; i < piece.height();i++) {
if (wallMap[pos.x + piece.width()][pos.y + i] > time + piece.requiredHeatTurnCount()) score++;
}
}
if (pos.y == 0) score += piece.width();
else {
for (int i = 0; i < piece.width();i++) {
if (wallMap[pos.x + i][pos.y - 1] > time + piece.requiredHeatTurnCount()) score++;
}
}
if (pos.y == 20 - piece.height()) score += piece.width();
else {
for (int i = 0; i < piece.width();i++) {
if (wallMap[pos.x + i][pos.y + piece.height()] > time + piece.requiredHeatTurnCount()) score++;
}
}
return score;
}
//大きいクッキーを壁に寄せる処理
void wallShift(const Stage& aStage, LargePiecesOnLane& largeLane, int index) {
Piece piece = largeLane.pieces[index];
Vector2i pos = largeLane.putPos[index];
int time = largeLane.timeStartBaking[index];
if (pos.x != 0 && pos.y != 0) {
if (setMapsGlobal[index][20 - piece.width()][20 - piece.height()] <= time) {
bool intersect = false;
for (int k = 0; k < 8; k++) {
if (k == index) continue;
if (largeLane.timeStartBaking[k] <= piece.requiredHeatTurnCount() + time &&
largeLane.timeStartBaking[k] + largeLane.pieces[k].requiredHeatTurnCount() >= time) {
if (Util::IsIntersect(Vector2i(20 - piece.width(), 20 - piece.height()), piece.width(), piece.height(), largeLane.putPos[k],
largeLane.pieces[k].width(), largeLane.pieces[k].height())) {
intersect = true;
break;
}
}
}
if (intersect == false) {
largeLane.putPos[index] = Vector2i(20 - piece.width(), 20 - piece.height());
return;
}
}
}
if (pos.x != 0) {
if (setMapsGlobal[index][20 - piece.width()][pos.y] <= largeLane.timeStartBaking[index]) {
bool intersect = false;
for (int k = 0; k < 8; k++) {
if (k == index) continue;
if (largeLane.timeStartBaking[k] <= piece.requiredHeatTurnCount() + time &&
largeLane.timeStartBaking[k] + largeLane.pieces[k].requiredHeatTurnCount() >= time) {
if (Util::IsIntersect(Vector2i(20 - piece.width(), pos.y), piece.width(), piece.height(), largeLane.putPos[k],
largeLane.pieces[k].width(), largeLane.pieces[k].height())) {
intersect = true;
break;
}
}
}
if (intersect == false) {
largeLane.putPos[index] = Vector2i(20 - piece.width(), pos.y);
return;
}
}
}
if (pos.y != 0) {
if (setMapsGlobal[index][pos.x][20 - piece.height()] <= largeLane.timeStartBaking[index]) {
for (int k = 0; k < 8; k++) {
if (k == index) continue;
if (largeLane.timeStartBaking[k] <= piece.requiredHeatTurnCount() + time &&
largeLane.timeStartBaking[k] + largeLane.pieces[k].requiredHeatTurnCount() >= time) {
if (Util::IsIntersect(Vector2i(pos.x, 20 - piece.height()), piece.width(), piece.height(), largeLane.putPos[k],
largeLane.pieces[k].width(), largeLane.pieces[k].height()))
return;
}
}
largeLane.putPos[index] = Vector2i(pos.x, 20 - piece.height());
}
}
return;
}
//largeLaneの配置計画を妨げない小クッキーの配置
void setSmall(const Stage& aStage, LargePiecesOnLane largeLane, int& index, Vector2i& putPos) {
index = 0;
Array<Vector2i, 400> pos;
for (index = 0; index < 8; index++) {
int bestScore = -1;
pos.clear();
Piece piece = aStage.candidateLane(CandidateLaneType_Small).pieces()[index];
if (aStage.turn() + piece.requiredHeatTurnCount() >= 1000) continue;
for (int i = 0; i < 21 - piece.width(); i++) {
for (int j = 0; j < 21 - piece.height(); j++) {
bool intersect = false;
for (int k = 0; k < 8; k++) {
if (largeLane.timeStartBaking[k] > piece.requiredHeatTurnCount()) continue;
if (Util::IsIntersect(Vector2i(i, j), piece.width(), piece.height(),
largeLane.putPos[k], largeLane.pieces[k].width(), largeLane.pieces[k].height())) {
intersect = true;
break;
}
}
//配置可能箇所が複数ある場合は、より壁沿いにあるものを選択
if (intersect) continue;
if (aStage.oven().isAbleToPut(piece, Vector2i(i, j))) {
int score = byTheWall(piece, Vector2i(i, j), wallMapGlobal, 0);
if (score > bestScore) {
bestScore = score;
putPos = Vector2i(i, j);
}
}
}
}
if (bestScore >= 0) return;
}
index = -1;
}
} // namespace
// EOF