ninjaさんの作品(ソースコード)

//------------------------------------------------------------------------------
/// @file
/// @author   ハル研究所プログラミングコンテスト実行委員会
///
/// @copyright  Copyright (c) 2017 HAL Laboratory, Inc.
/// @attention  このファイルの利用は、同梱のREADMEにある
///             利用条件に従ってください。
//------------------------------------------------------------------------------
   
// 回答の方針
//
// 家を各UFOに分割し, 最適化する
   
#include "Answer.hpp"
#include "Vector2.hpp"
#include "Parameter.hpp"
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<set>
   
// 家の構造体
typedef struct {
  hpc::Vector2 pos;
  float angle;
  int id;
  bool isDelivered;
} Node;
   
// 角度によって比較可能
bool operator<(const Node &lhs, const Node &rhs) {
  return lhs.angle < rhs.angle;
}
   
// TSP DP用ノード
typedef struct {
  float x, y;
  short from, score, restId;
} TSP;
   
// bitのk桁目が1かどうか
inline bool containBit(unsigned int bit, int k) {
  return (bit & (1 << k)) > 0;
}
   
// bitの二進数表記で1の数を返す
inline int countBit(unsigned int bit) {
  int ret = 0;
  while(bit > 0) {
    ret += bit & 1;
    bit >>= 1;
  }
  return ret;
}
   
// e^x
inline float power(float e, int x) {
  if(x == 0) return 1;
  if(x == 1) return e;
  if(x % 2 == 0) return power(e * e, x / 2);
  return e * power(e, x - 1);
}
   
inline int min(int a, int b) {
  return a > b ? b : a;
}
   
/// プロコン問題環境を表します。
namespace hpc {
   
static const int MAX_TIME = 2000;
static Vector2 ORIGIN(375.0, 375.0), X_ASIS(-750.0, 0.0);
static int counter = 0;
static TSP tsp[(1 << 12) * 12];
static const int BIT_MAX = (1 << 12);
static Vector2 restPosList[100000];
static Vector2 housePoses[20];
static int bigUFOids[2], smallUFOids[8], houseIds[100];
static Node houses[100];
   
class Solver
{
private:
  int mTurn, mLimit, mHouseSize;
  std::vector<std::vector<int>> mSmallUFOTargets;
  std::vector<Vector2> mBigTargetPos, mSmallUFOTargetPos;
  std::vector<std::vector<std::pair<Vector2, int>>> mBigTargets;
  int mSmallUFOProgress[8];
  Vector2 mSmallUFORestTargets[8][4];
   
  // bigUFO_iのnターン後の位置を返す関数
  Vector2 bigUFOPos(const Stage &stage, int i, int n) {
    Vector2 ufoPos = stage.ufos()[bigUFOids[i]].pos();
    if(mTurn + n < mBigTargets[i][0].second) {
      float dist = (mBigTargets[i][0].first - ufoPos).length();
      int turn = ceil(dist);
      Vector2 unit = (mBigTargets[i][0].first - ufoPos).unit();
      if(turn <= n) return mBigTargets[i][0].first;
      return ufoPos + 5 * unit * n;
    } else if(mTurn + n < mBigTargets[i][1].second) {
      int diff = n - mTurn - mBigTargets[i][0].second;
      Vector2 dir = (mBigTargets[i][1].first - mBigTargets[i][0].first).unit();
      return mBigTargets[i][0].first + dir * 5 * diff;
    } else {
      return mBigTargets[i][1].first;
    }
  }
   
  // UFOが移動にかかるターン数を計算する関数
  inline int calcDist(const Vector2 &pos, float spd, float radius) {
    if(spd <= 0) return 0;
    return ceil(fmax(0.0, pos.length() - radius) / spd);
  }
   
  // 二分探索用関数
  bool f(const Stage &stage, Vector2 pos, int i, int turn, int plus) {
    Vector2 bUFOPos = bigUFOPos(stage, i, turn + plus + 1);
    Vector2 sUFOPos = movePos(pos, bUFOPos, 10, plus);
    if((bUFOPos - sUFOPos).squareLength() < 100) {
      return true;
    }
    return false;
  }
   
  //posのsmallUFOがbigUFO_iに衝突するまでのターン数を返す関数
  int toBig(const Stage &stage, Vector2 pos, int i, int turn) {
    int ansMin = 50, notMax = 0;
    if(!f(stage, pos, i, turn, 50)) return 100;
    if(f(stage, pos, i, turn, 0)) return turn;
    while(ansMin - notMax > 1) {
      int piv = (ansMin + notMax) / 2;
      if(f(stage, pos, i, turn, piv)) ansMin = piv;
      else notMax = piv;
    }
    return ansMin;
  }
   
  // fromからtoに速さspdでturnターン移動した後の座標を返す関数
  inline Vector2 movePos(Vector2 &from, Vector2 &to, float spd, int turn) {
    if(spd * turn * turn * spd > (to - from).squareLength()) return to;
    if(to.equals(from)) return from;
    return from + (to - from).unit() * spd * turn;
  }
   
  // originから見て家のある方向を返す
  std::vector<Vector2> calcBothEnds(const Stage& stage, Vector2 origin, int ids[100]) {
    std::vector<Vector2> ret;
    for(int i = 0; i < mHouseSize; i++) {
      if(stage.houses()[ids[i]].delivered() || houses[i].isDelivered) continue;
      Vector2 pos = stage.houses()[ids[i]].pos();
      if((pos - origin).length() < 1) continue;
      Vector2 unit = (pos - origin).unit();
      Vector2 orth(unit.y, -unit.x);
      ret.push_back(pos + orth * 12);
      ret.push_back(pos);
      ret.push_back(pos - orth * 12);
    }
    return ret;
  }
   
  // fromからtoの方向に向けてlimitターン移動した場合に経路上に存在する家の配列を返す
  std::vector<int> countNear(const Stage& stage, Vector2 from, Vector2 to, int ids[100], int limit) {
    Vector2 unit = (to - from).unit();
    Vector2 orth(unit.y, -unit.x);
    std::vector<int> ret;
    for(int i = 0; i < mHouseSize; i++) {
      if(stage.houses()[houses[ids[i]].id].delivered() || houses[i].isDelivered) continue;
      Vector2 vec = stage.houses()[ids[i]].pos();
      float d = ceil(unit.dot(vec - from) / 5) * 5 - unit.dot(vec - from);
      if((vec - from).dot(unit) < 0) continue;
      if((vec - from).dot(unit) / 5 > limit) continue;
      if(power((vec - from).dot(orth), 2) + power(d, 2) < 15 * 15) ret.push_back(i);
    }
    return ret;
  }
   
  // smallUFOの経路最適化
  // 動的計画法を用いて最適な経路を得る
  std::pair<std::vector<int>, int> optimizeRoute(const Stage &stage, int id, std::vector<int> route, Vector2 from) {
    int size = route.size();
    std::vector<int> ret;
    if(size == 0) return std::make_pair(route, 0);
    if(size <= 1) return std::make_pair(route, ceil((stage.houses()[houseIds[route[0]]].pos() - from).length() - 7) / 12);
    // 14以上はMLE
    if(size >= 14) return std::make_pair(route, MAX_TIME);
   
    bool lightMode = false;
   
    for(int i = 0; i < size; i++) {
      housePoses[i] = houses[route[i]].pos;
    }
   
    // 13のとき最終地点を固定する
    if(size == 13) {
      size = 12;
      lightMode = true;
    }
    int bitSize = 1 << size;
   
    // tsp[踏破集合][現在地] を1次元配列化したもの
    short restPosIt = 0;
   
    // 初期化
    for(int bit = 0; bit < bitSize; bit++) for(int i = 0; i < size; i++) {
      tsp[bit + BIT_MAX * i].score = MAX_TIME;
    }
    tsp[0].x = ORIGIN.x;
    tsp[0].y = ORIGIN.y;
    tsp[0].from = -1;
    tsp[0].score = 0;
    float longest = 0;
    int maxId = 0;
    for(int i = 0; i < size; i++) {
      if((housePoses[i] - ORIGIN).squareLength() > longest) {
        longest = (housePoses[i] - ORIGIN).squareLength();
        maxId = i;
      }
    }
    for(int i = 0; i < size; i++) {
      if(i == maxId) continue;
      tsp[(1 << i) + BIT_MAX * i].from = -1;
      Vector2 housePos = housePoses[i];
      Vector2 nowPos(tsp[0].x, tsp[0].y);
      int plusTurn = calcDist(housePos - nowPos, 12, 7);
      tsp[(1 << i) + BIT_MAX * i].score = plusTurn;
      Vector2 nextPos = movePos(nowPos, housePos, 12, plusTurn);
      tsp[(1 << i) + BIT_MAX * i].x = nextPos.x;
      tsp[(1 << i) + BIT_MAX * i].y = nextPos.y;
    }
   
    // tsp[set][i] = min(tsp[set/{i}][j] + cost(j, i) (forall j in V))
    for(int bit = 1; bit < bitSize; bit++) {
      for(int i = 0; i < size; i++) {
        if(!containBit(bit, i)) {
          tsp[bit + BIT_MAX * i].score = MAX_TIME;
          continue;
        }
        if(tsp[bit + BIT_MAX * i].score > 100) continue;
        for(int j = 0; j < size; j++) {
          // i->jの遷移を計算する
          int nextBit = bit | (1 << j);
          if(containBit(bit, j)) continue;
          Vector2 housePos = housePoses[j];
          Vector2 nowPos(tsp[bit + BIT_MAX * i].x, tsp[bit + BIT_MAX * i].y);
          int plusTurn = calcDist(housePos - nowPos, 12, 7);
          int visited = countBit(bit);
          Vector2 nextPos = movePos(nowPos, housePos, 12, plusTurn);
          Vector2 nextRestPos = ORIGIN;
   
          // 後ろから数えて5の倍数のとき, 遷移に荷物の回収を考慮する
          if((!lightMode && (size - visited) % 5 == 0 && (size - visited) > 0) || (lightMode && (13 - visited) % 5 == 0)) {
            // i->農場->j
            int restCost1 = calcDist(ORIGIN - nowPos, 12, 22);
            Vector2 restPos = movePos(nowPos, ORIGIN, 12, restCost1);
            int restCost2 = calcDist(housePos - restPos, 12, 7);
            nextPos = movePos(restPos, housePos, 12, restCost2);
            plusTurn = restCost1 + restCost2;
   
            // i->bigUFO_k->j
            for(int k = 0; k < 2; k++) {
              int toBigCost = toBig(stage, nowPos, k, tsp[bit + BIT_MAX * i].score);
              Vector2 targetPos = bigUFOPos(stage, k, tsp[bit + BIT_MAX * i].score + toBigCost + 1);
              Vector2 bigRestPos = movePos(nowPos, targetPos, 12, toBigCost);
              int fromBigCost = calcDist(housePos - bigRestPos, 12, 7);
              Vector2 fromBigPos = movePos(bigRestPos, housePos, 12, fromBigCost);
              if(plusTurn > toBigCost + fromBigCost) {
                plusTurn = toBigCost + fromBigCost;
                nextPos = fromBigPos;
                nextRestPos = targetPos;
              }
            }
            restPosList[++restPosIt] = nextRestPos;
          }
          // スコアが小さいもので上書き
          if(tsp[nextBit + BIT_MAX * j].score > tsp[bit + BIT_MAX * i].score + plusTurn) {
            tsp[nextBit + BIT_MAX * j].score = tsp[bit + BIT_MAX * i].score + plusTurn;
            tsp[nextBit + BIT_MAX * j].from = i;
            tsp[nextBit + BIT_MAX * j].x = nextPos.x;
            tsp[nextBit + BIT_MAX * j].y = nextPos.y;
            tsp[nextBit + BIT_MAX * j].restId = restPosIt;
          }
        }
      }
    }
    int minId = 0;
    int to13score[size];
    if(lightMode) {
      int to13MinScore = 10000;
      for(int i = 0; i < size; i++) {
        to13score[i] = calcDist(housePoses[12] - Vector2(tsp[(bitSize - 1) + BIT_MAX * i].x, tsp[(bitSize - 1) + BIT_MAX * i].y), 12, 7);
        if(to13MinScore > to13score[i] + tsp[(bitSize - 1) + BIT_MAX * i].score) {
          minId = i;
          to13MinScore = to13score[i] + tsp[(bitSize - 1) + BIT_MAX * i].score;
        }
      }
    } else {
      for(int i = 1; i < size; i++) {
        if(tsp[(bitSize - 1) + BIT_MAX * minId].score > tsp[(bitSize - 1) + BIT_MAX * i].score) minId = i;
      }
    }
   
    if(lightMode) {
      ret.push_back(route[12]);
    }
    unsigned int bit = bitSize - 1, now = minId, restCount = 0;
    for(int i = 0; i < size; i++) {
      ret.push_back(route[now]);
      if((!lightMode && i + 1 != size && (i + 1) % 5 == 0) || (lightMode && (i + 2) % 5 == 0)) {
        ret.push_back((ORIGIN.dist(restPosList[tsp[bit + BIT_MAX * now].restId]) < 1) ? -1 : -2);
        mSmallUFORestTargets[id][restCount] = restPosList[tsp[bit + BIT_MAX * now].restId];
        restCount++;
      }
      int next = tsp[bit + BIT_MAX * now].from;
      bit = (bit & ~(1 << now));
      now = next;
    }
    std::reverse(ret.begin(), ret.end());
    std::reverse(mSmallUFORestTargets[id], mSmallUFORestTargets[id] + restCount);
    if(lightMode) return std::make_pair(ret, tsp[(bitSize - 1) + BIT_MAX * minId].score + to13score[minId]);
    else return std::make_pair(ret, tsp[(bitSize - 1) + BIT_MAX * minId].score);
  }
   
public:
  void init(const Stage& aStage) {
    counter++;
    mBigTargetPos.clear();
    mSmallUFOTargetPos.clear();
    mSmallUFOTargets.clear();
    mSmallUFOTargets.resize(8);
    mBigTargetPos.resize(2);
    mSmallUFOTargetPos.resize(8);
    for(int i = 0; i < 8; i++) mSmallUFOProgress[i] = 0;
    mHouseSize = aStage.houses().count();
    mTurn = 0;
   
    int bigUFOIndex = 0, smallUFOIndex = 0;
    // ufoの大小を区別してindexを格納
    for (int ufoId = 0, leng = aStage.ufos().count(); ufoId < leng; ufoId++) {
      if(aStage.ufos()[ufoId].type() == UFOType::UFOType_Small) smallUFOids[smallUFOIndex++] = ufoId;
      else bigUFOids[bigUFOIndex++] = ufoId;
    }
   
    // houseを角度でソートする
    for(int houseId = 0; houseId < mHouseSize; houseId++) {
      Vector2 pos = aStage.houses()[houseId].pos();
      houses[houseId].pos = aStage.houses()[houseId].pos();
      houses[houseId].angle = (pos - aStage.ufos()[0].pos()).rotSign(X_ASIS);
      houses[houseId].id = houseId;
      houses[houseId].isDelivered = false;
    }
    std::sort(houses, houses + mHouseSize);
    for(int i = 0; i < mHouseSize; i++) houseIds[i] = houses[i].id;
   
    mLimit = mHouseSize - 5;
    int befRestSize = 0, befLimit = 0;
    Vector2 befTargets[4] = {Vector2(1000, 1000), Vector2(1000, 1000), Vector2(1000, 1000), Vector2(1000, 1000)};
   
    // mLimitターンのBigUFOの動きを探索し,
    // smallUFOの動きを探索する
    // smallUFOの配達終了の最大値とmLimitの差を小さくするためmLimitを平均値にし再度探索する
    for(int search = 0; search < 3; search++) {
      if(abs(befLimit - mLimit) / 2 == 0) break;
      // BigUFOの探索
      for(int i = 0; i < mHouseSize; i++) houses[i].isDelivered = false;
      mBigTargets.clear();
      mBigTargets.resize(2);
      // 1回目のbigUFO0の方向探索
      // 探索点列挙
      std::vector<Vector2> tos = calcBothEnds(aStage, aStage.ufos()[bigUFOids[0]].pos(), houseIds);
      std::vector<int> ans;
      int id = 0;
      // 探索点評価, 決定
      int firstRange = 67;
      for(int i = 0, leng = tos.size(); i < leng; i++) {
        std::vector<int> ids = countNear(aStage, aStage.ufos()[bigUFOids[0]].pos(), tos[i], houseIds, min(firstRange, mLimit));
        if(ans.size() < ids.size()) {
          ans = ids;
          id = i;
        }
      }
      // 反映
      Vector2 ufoPos = aStage.ufos()[bigUFOids[0]].pos(), targetPos = ufoPos, unit = (tos[id] - ufoPos).unit();
      for(int i = 0, leng = ans.size(); i < leng; i++) {
        houses[ans[i]].isDelivered = true;
        Vector2 housePos = aStage.houses()[houseIds[ans[i]]].pos();
        Vector2 tempPos = ufoPos + unit * 5 * floor((housePos - ufoPos).dot(unit) / 5 + 0.5);
        if((targetPos - ufoPos).length() < (tempPos - ufoPos).length()) {
          targetPos = tempPos;
        }
      }
      mBigTargetPos[0] = targetPos;
      mBigTargets[0].push_back(std::make_pair(targetPos, floor((targetPos - ufoPos).length() / 5 + 0.5)));
   
      // 2回目
      ufoPos = targetPos;
      tos = calcBothEnds(aStage, ufoPos, houseIds);
      ans.clear();
      id = 0;
      // 探索点評価, 決定
      for(int i = 0, leng = tos.size(); i < leng; i++) {
        std::vector<int> ids = countNear(aStage, ufoPos, tos[i], houseIds, mLimit - mBigTargets[0][0].second);
        if(ans.size() < ids.size()) {
          ans = ids;
          id = i;
        }
      }
      // 反映
      unit = (tos[id] - ufoPos).unit();
      for(int i = 0, leng = ans.size(); i < leng; i++) {
        houses[ans[i]].isDelivered = true;
        Vector2 housePos = aStage.houses()[houseIds[ans[i]]].pos();
        Vector2 tempPos = ufoPos + unit * 5 * floor((housePos - ufoPos).dot(unit) / 5 + 0.5);
        if((targetPos - ufoPos).length() < (tempPos - ufoPos).length()) {
          targetPos = tempPos;
        }
      }
      mBigTargets[0].push_back(std::make_pair(targetPos, mBigTargets[0][0].second + floor((targetPos - ufoPos).length() / 5 + 0.5)));
   
      // 2台目のBigUFOの方向探索
      // 1台目と近い方向とならないようにする
      Vector2 ufo1dir = (targetPos - aStage.ufos()[bigUFOids[0]].pos()).unit();
      ans.clear();
      for(int i = 0, leng = tos.size(); i < leng; i++) {
        if(ufo1dir.dot((tos[i] - aStage.ufos()[bigUFOids[1]].pos()).unit()) > 0.9) continue;
        std::vector<int> ids = countNear(aStage, aStage.ufos()[bigUFOids[1]].pos(), tos[i], houseIds, min(firstRange, mLimit));
        if(ans.size() < ids.size()) {
          ans = ids;
          id = i;
        }
      }
   
      ufoPos = aStage.ufos()[bigUFOids[1]].pos();
      targetPos = ufoPos;
      unit = (tos[id] - ufoPos).unit();
      for(int i = 0, leng = ans.size(); i < leng; i++) {
        Vector2 housePos = aStage.houses()[houseIds[ans[i]]].pos();
        Vector2 tempPos = ufoPos + unit * 5 * floor((housePos - ufoPos).dot(unit) / 5 + 0.5);
        houses[ans[i]].isDelivered = true;
        if((targetPos - ufoPos).length() < (tempPos - ufoPos).length()) {
          targetPos = tempPos;
        }
      }
      mBigTargetPos[1] = targetPos;
      mBigTargets[1].push_back(std::make_pair(targetPos, floor((targetPos - ufoPos).length() / 5 + 0.5)));
   
      ufoPos = targetPos;
      tos = calcBothEnds(aStage, ufoPos, houseIds);
      ans.clear();
      id = 0;
      // 探索点評価
      for(int i = 0, leng = tos.size(); i < leng; i++) {
        std::vector<int> ids = countNear(aStage, ufoPos, tos[i], houseIds, mLimit - mBigTargets[1][0].second);
        if(ans.size() < ids.size()) {
          ans = ids;
          id = i;
        }
      }
      // 反映
      unit = (tos[id] - ufoPos).unit();
      for(int i = 0, leng = ans.size(); i < leng; i++) {
        houses[ans[i]].isDelivered = true;
        Vector2 housePos = aStage.houses()[houseIds[ans[i]]].pos();
        Vector2 tempPos = ufoPos + unit * 5 * floor((housePos - ufoPos).dot(unit) / 5 + 0.5);
        if((targetPos - ufoPos).length() < (tempPos - ufoPos).length()) {
          targetPos = tempPos;
        }
      }
      mBigTargets[1].push_back(std::make_pair(targetPos, mBigTargets[1][0].second + floor((targetPos - ufoPos).length() / 5 + 0.5)));
   
   
   
      // smallUFOの探索
   
      // 残りの家を列挙
      std::vector<int> rest;
      for(int i = 0; i < mHouseSize; i++) {
        if(!houses[i].isDelivered) rest.push_back(i);
      }
      int restSize = rest.size();
      if(befRestSize == restSize && befTargets[0].equals(mBigTargets[0][0].first) && befTargets[1].equals(mBigTargets[0][1].first) && befTargets[2].equals(mBigTargets[1][0].first) && befTargets[3].equals(mBigTargets[1][1].first)) {
        break;
      }
      befRestSize = restSize;
      befTargets[0] = mBigTargets[0][0].first;
      befTargets[1] = mBigTargets[0][1].first;
      befTargets[2] = mBigTargets[1][0].first;
      befTargets[3] = mBigTargets[1][1].first;
   
      // samllUFOの経路最適化
      // 角度によって9区間に分割し, その区間内を配達するために必要なターン数を均すため, 最大の区間の家数を減らす
      // 上の操作を行って最も最大値が小さいものを採用する
      int rem = restSize % 8;
      std::vector<int> thr(9);
      thr[0] = 0;
      thr[8] = restSize;
      for(int i = 1; i < 8; i++) {
        thr[i] = thr[i - 1] + restSize / 8 + ((rem > i) ? 1 : 0);
      }
      unsigned long long minData = 0;
      int minmax = MAX_TIME;
      for(int i = 8; i >= 0; i--) {
        minData *= 100;
        minData += thr[i];
      }
   
      int loopNum = 28 + search;
      std::pair<int, int> memo[8];
      int memo0 = -1;
      for(int i = 0; i < 8; i++) memo[i].first = memo[i].second = -1;
      std::pair<std::vector<int>, int> scorememo[8];
      for(int loop = 0; loop < loopNum; loop++) {
        for(int i = 1; i < 9; i++) {
          mSmallUFOTargets[i - 1].clear();
          for(int j = thr[i - 1]; j < thr[i]; j++) mSmallUFOTargets[i - 1].push_back(rest[j]);
        }
        for(int i = thr[8]; i < restSize; i++) mSmallUFOTargets[0].push_back(rest[i]);
   
        int increaseId = 0, maxId = 0, maxScore = 0;
        for(int i = 0; i < 8; i++) {
          std::pair<std::vector<int>, int> score;
          if(i == 0) {
            if(thr[8] == memo0 && thr[0] == memo[0].first && thr[1] == memo[0].second) {
              score = scorememo[0];
            } else {
              score = optimizeRoute(aStage, i, mSmallUFOTargets[i], aStage.ufos()[smallUFOids[i]].pos());
            }
            memo0 = thr[8];
            memo[0].first = thr[0];
            memo[0].second = thr[1];
            scorememo[0] = score;
          } else {
            if(thr[i] == memo[i].first && thr[i + 1] == memo[i].second) {
              score = scorememo[i];
            } else {
              score = optimizeRoute(aStage, i, mSmallUFOTargets[i], aStage.ufos()[smallUFOids[i]].pos());
            }
            memo[i].first = thr[i];
            memo[i].second = thr[i + 1];
            scorememo[i] = score;
          }
          mSmallUFOTargets[i] = score.first;
          if(maxScore < score.second) {
            maxId = i;
            maxScore = score.second;
          }
        }
        if(maxScore < minmax) {
          minmax = maxScore;
          minData = 0;
          for(int i = 8; i >= 0; i--) {
            minData *= 100;
            minData += thr[i];
          }
        }
        increaseId = (maxId + 1) % 8;
        if(maxId < increaseId) {
          for(int i = maxId; i < increaseId; i++) thr[i + 1]--;
        } else {
          for(int i = maxId; i < 9; i++) thr[i + 1]--;
          for(int i = 0; i < increaseId; i++) thr[i + 1]--;
        }
        if(thr[1] < 0) {
          for(int i = 1; i < 8; i++) thr[i] = thr[i + 1];
          thr[8] = restSize;
        }
      }
   
      for(int i = 0; i < 9; i++) {
        thr[i] = minData % 100;
        minData /= 100;
      }
//      std::cerr << "stage" << counter - 1 << " " << mHouseSize - restSize << std::endl;
   
      for(int i = 1; i < 9; i++) {
        mSmallUFOTargets[i - 1].clear();
        for(int j = thr[i - 1]; j < thr[i]; j++) mSmallUFOTargets[i - 1].push_back(rest[j]);
      }
      for(int i = thr[8]; i < restSize; i++) mSmallUFOTargets[0].push_back(rest[i]);
      int maxScore = 0;
      for(int i = 0; i < 8; i++) {
        std::pair<std::vector<int>, int> score = optimizeRoute(aStage, i, mSmallUFOTargets[i], aStage.ufos()[smallUFOids[i]].pos());
        mSmallUFOTargets[i] = score.first;
        if(maxScore < score.second) maxScore = score.second;
      }
      mLimit = (mLimit * 3 + maxScore * 2) / 5;
    }
  }
   
  void moveItems(const Stage& aStage, Actions& aActions) {
    mTurn++;
   
    for(int i = 0; i < 2; i++) {
      if (Util::IsIntersect(aStage.ufos()[bigUFOids[i]], aStage.office())) {
        aActions.add(Action::PickUp(bigUFOids[i]));
      }
      if(aStage.ufos()[bigUFOids[i]].itemCount() > 5) {
        for(int j = 0; j < 8; j++) {
          if(aStage.ufos()[smallUFOids[j]].itemCount() < 5) {
            if (Util::IsIntersect(aStage.ufos()[bigUFOids[i]], aStage.ufos()[smallUFOids[j]])) {
              aActions.add(Action::Pass(bigUFOids[i], smallUFOids[j]));
            }
          }
        }
      }
   
      for(int j = 0; j < mHouseSize; j++) {
        if(Util::IsIntersect(aStage.ufos()[bigUFOids[i]], aStage.houses()[j])) {
          if(aStage.houses()[j].delivered()) continue;
          aActions.add(Action::Deliver(bigUFOids[i], j));
        }
      }
    }
   
    for(int i = 0; i < 8; i++) {
      int idsSize = mSmallUFOTargets[i].size();
      if(mSmallUFOProgress[i] >= idsSize) continue;
      if (Util::IsIntersect(aStage.ufos()[smallUFOids[i]], aStage.office())) {
        aActions.add(Action::PickUp(smallUFOids[i]));
      }
      while(mSmallUFOProgress[i] < idsSize && mSmallUFOTargets[i][mSmallUFOProgress[i]] >= 0 && aStage.houses()[houses[mSmallUFOTargets[i][mSmallUFOProgress[i]]].id].delivered()) {
        mSmallUFOProgress[i]++;
      }
      if(mSmallUFOProgress[i] >= idsSize) continue;
      if(mSmallUFOTargets[i][mSmallUFOProgress[i]] < 0) {
        if(aStage.ufos()[smallUFOids[i]].itemCount() == 5) {
          mSmallUFOProgress[i]++;
        } else {
          continue;
        }
      }
      if (Util::IsIntersect(aStage.ufos()[smallUFOids[i]], aStage.houses()[houses[mSmallUFOTargets[i][mSmallUFOProgress[i]]].id])) {
        aActions.add(Action::Deliver(smallUFOids[i], houses[mSmallUFOTargets[i][mSmallUFOProgress[i]]].id));
        mSmallUFOProgress[i]++;
        continue;
      }
    }
  }
   
  void moveUFOs(const Stage& aStage, TargetPositions& aTargetPositions) {
    for(int ufoId = 0, ufoCount = aStage.ufos().count(); ufoId < ufoCount; ufoId++) {
      aTargetPositions.add(aStage.ufos()[ufoId].pos());
    }
   
    for(int i = 0; i < 2; i++) {
      if(mTurn <= mBigTargets[i][0].second) aTargetPositions[bigUFOids[i]] = mBigTargets[i][0].first;
      else aTargetPositions[bigUFOids[i]] = mBigTargets[i][1].first;
    }
   
    for(int i = 0; i < 8; i++) {
      int idsSize = mSmallUFOTargets[i].size();
      while(mSmallUFOProgress[i] < idsSize && mSmallUFOTargets[i][mSmallUFOProgress[i]] >= 0 && aStage.houses()[houses[mSmallUFOTargets[i][mSmallUFOProgress[i]]].id].delivered()) {
        mSmallUFOProgress[i]++;
      }
      if(mSmallUFOProgress[i] >= idsSize) continue;
      if(mSmallUFOTargets[i][mSmallUFOProgress[i]] == -1) {
        if(Util::IsIntersect(aStage.ufos()[smallUFOids[i]], aStage.office())) {
          aTargetPositions[smallUFOids[i]] = houses[mSmallUFOTargets[i][mSmallUFOProgress[i] + 1]].pos;
          continue;
        }
        Vector2 vec = (aStage.ufos()[smallUFOids[i]].pos() - ORIGIN).unit();
        aTargetPositions[smallUFOids[i]] = ORIGIN + vec * 21.9;
        continue;
      }
      if(mSmallUFOTargets[i][mSmallUFOProgress[i]] < -1) {
        if(Util::IsIntersect(aStage.ufos()[smallUFOids[i]], aStage.ufos()[bigUFOids[0]]) || Util::IsIntersect(aStage.ufos()[smallUFOids[i]], aStage.ufos()[bigUFOids[1]])) {
          aTargetPositions[smallUFOids[i]] = houses[mSmallUFOTargets[i][mSmallUFOProgress[i] + 1]].pos;
          continue;
        }
        aTargetPositions[smallUFOids[i]] = mSmallUFORestTargets[i][mSmallUFOProgress[i] / 6];
        continue;
      }
      aTargetPositions[smallUFOids[i]] = houses[mSmallUFOTargets[i][mSmallUFOProgress[i]]].pos;
    }
  }
};
   
Solver g_Solver;
   
//------------------------------------------------------------------------------
/// Answer クラスのコンストラクタです。
///
/// ここに最初のステージの開始前に行う処理を書くことができます。何も書かなくても構いません。
Answer::Answer()
{
}
   
//------------------------------------------------------------------------------
/// Answer クラスのデストラクタです。
///
/// ここに最後のステージの終了後に行う処理を書くことができます。何も書かなくても構いません。
Answer::~Answer()
{
}
   
//------------------------------------------------------------------------------
/// 各ステージ開始時に呼び出されます。
///
/// ここで、各ステージに対して初期処理を行うことができます。
///
/// @param[in] aStage 現在のステージ。
void Answer::init(const Stage& aStage)
{
    g_Solver.init(aStage);
}
   
//------------------------------------------------------------------------------
/// 各ターンの、受け渡しフェーズの行動を指定してください。
///
/// - Actionクラスのstatic関数で行動を生成し、aActionsに格納してください。
/// - 行動は、配列のインデックスの昇順で実行されます。
/// - 同じUFOが複数回行動することもできます。
/// - UFOが箱を持っていないなど、必要な条件を満たしていない場合は何も起こりません。
///   条件の詳細はActionクラスを参照してください。
/// - 1回のフェーズの最大行動数は、Parameter::MaxActionPerTurnです。
/// - aActionsの要素の、UFOや家のインデックスが範囲外の場合、アサートに失敗します。
///
/// @param[in] aStage 現在のステージ。
/// @param[out] aActions この受け渡しフェーズの行動を指定する配列。
void Answer::moveItems(const Stage& aStage, Actions& aActions)
{
    g_Solver.moveItems(aStage, aActions);
}
   
//------------------------------------------------------------------------------
/// 各ターンの、移動フェーズの行動を指定してください。
///
/// - 各UFOごとに、目標座標を指定してください。
/// - aTargetPositions[i]が、aStage.ufos()[i]の目標座標となります。
/// - aTargetPositions.count() == aStage.ufos().count()となるように、配列に座標を追加してください。
///   - 要素数が異なる場合はアサートに失敗します。
/// - aTargetPositionsの要素の値が NaN または ±Inf である場合、アサートに失敗します。
///
/// @param[in] aStage 現在のステージ。
/// @param[out] aTargetPositions 各UFOの目標座標を指定する配列。
void Answer::moveUFOs(const Stage& aStage, TargetPositions& aTargetPositions)
{
  g_Solver.moveUFOs(aStage, aTargetPositions);
}
   
//------------------------------------------------------------------------------
/// 各ステージ終了時に呼び出されます。
///
/// ここにステージ終了時の処理を書くことができます。何も書かなくても構いません。
///
/// @param[in] aStage 現在のステージ。
void Answer::finalize(const Stage& aStage)
{
}
   
} // namespace
// EOF