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

//------------------------------------------------------------------------------
#include "Answer.hpp"
 
//------------------------------------------------------------------------------
namespace hpc {
 
//------------------------------------------------------------------------------
namespace {
const int sInvalid = -1;
const float sEpsilon = 0.001f;
const int sThresholdMin = 40;
const int sThresholdMax = 150;
const int sLoopCount = 260;
}
     
//------------------------------------------------------------------------------
class Solver
{
public:
     
    void init(const Stage& aStage, int aThreshold, Random& aRandom)
    {
        // 初期化
        mThreshold = aThreshold;
        mDeliverdCount = 0;
         
        const int houseCount = aStage.houses().count();
        for (int i=0; i<houseCount; ++i) {
            mIsDeliverd[i] = false;
        }
         
        for (int i=0; i<sThresholdMax; ++i) {
            mActions[i].clear();
            mTargetPositions[i].clear();
        }
         
        // UFOの動作を計算
        int ufoIndex = 0;
        while (ufoIndex < Parameter::LargeUFOCount) {
            calcLarge(aStage, ufoIndex, aRandom);
            ufoIndex++;
        }
        while (ufoIndex < Parameter::UFOCount) {
            calcSmall(aStage, ufoIndex, aRandom);
            ufoIndex++;
        }
 
        // 結果に応じた設定
        mIsFinish = (houseCount == mDeliverdCount);
        mCurrentIndex = 0;
    }
 
    bool isFinish() const { return mIsFinish; }
 
    void moveItems(const Stage& aStage, Actions& aActions)
    {
        if (sThresholdMax <= mCurrentIndex) { return; }
        const int actionCount = mActions[mCurrentIndex].count();
        for (int i = 0; i < actionCount; ++i) {
            aActions.add(mActions[mCurrentIndex][i]);
        }
    }
 
    void moveUFOs(const Stage& aStage, TargetPositions& aTargetPositions)
    {
        const int ufoCount = aStage.ufos().count();
        for (int ufoIndex = 0; ufoIndex < ufoCount; ++ufoIndex) {
            if (mCurrentIndex < sThresholdMax && ufoIndex < mTargetPositions[mCurrentIndex].count()) {
                aTargetPositions.add(mTargetPositions[mCurrentIndex][ufoIndex]);
            } else {
                aTargetPositions.add(Vector2(10.0f, 10.0f));
            }
        }
    }
     
    void next() { mCurrentIndex++; }
 
private:
    // 大きいUFOの経路計算
    void calcLarge(const Stage& aStage, int aUfoIndex, Random& aRandom)
    {
        // 初期化
        const UFO& ufo = aStage.ufos()[aUfoIndex];
        Vector2 currentPos = ufo.pos();
        mLargeUfoItemCount[aUfoIndex] = ufo.capacity();
        int turn = 0;
        //
        Vector2 targetPos;
        int count = 0;
         
        // 最初のPickUp
        mActions[turn].add(Action::PickUp(aUfoIndex));
 
        // 次の家を選択しておく
        int houseIndex = getNearHouseIndex(aStage, currentPos, aRandom, turn, 700000.0f);
 
        // 家に移動 -> 配達のループ
        while (turn < mThreshold && houseIndex != sInvalid) {
            // 次の家までの情報を計算する
            const House& house = aStage.houses()[houseIndex];
            Vector2 toHouse = house.pos() - currentPos;
            float toHouseLength = toHouse.length() - house.radius() - ufo.radius() + sEpsilon;
            if (0.0f < toHouseLength) {
                toHouse.unitAssign(toHouseLength);
                targetPos = currentPos + toHouse;
                count = (int)(toHouseLength / ufo.maxSpeed()) + 1;
            } else {
                targetPos = currentPos;
                count = 0;
            }
             
            // 次の次の家を選択する
            int houseIndexNext = sInvalid;
            if (1 < mLargeUfoItemCount[aUfoIndex]) {
                mIsDeliverd[houseIndex] = true;
                houseIndexNext = getNearHouseIndex(aStage, targetPos, aRandom, turn, 10000.0f);
                mIsDeliverd[houseIndex] = false;
            }
             
            // 次の次の家の場所から次の家までの情報を計算しなおす
            if (houseIndexNext != sInvalid) {
                const House& house2 = aStage.houses()[houseIndexNext];
                const float x1 = currentPos.x;
                const float y1 = currentPos.y;
                const float x2 = house2.pos().x;
                const float y2 = house2.pos().y;
                const float a = y1 - y2;
                const float b = x2 - x1;
                const float c = -(a * x1 + b * y1);
                const float aabb = a * a + b * b;
                const float d = Math::Abs(a * house.pos().x + b * house.pos().y + c) / Math::Sqrt(aabb);
                const float r = ufo.radius() + house.radius() - sEpsilon;
                if (r < d) {
                    const Vector2 vec1 = currentPos - house.pos();
                    const Vector2 vec2 = house2.pos() - house.pos();
                    if (0.0f < vec1.squareLength()) {
                        targetPos = house.pos() + (vec1.unit() + vec2.unit()).unit(r);
                        count = (int)((targetPos - currentPos).length() / ufo.maxSpeed()) + 1;
                    }
                }
            }
             
            // 移動する
            const Vector2 toTargetSpeed = (targetPos - currentPos).unit(ufo.maxSpeed());
            for (int i=0; i<count; ++i) {
                mLargeUfoHistory[aUfoIndex][turn] = currentPos;
                currentPos += toTargetSpeed;
                mTargetPositions[turn++].add(targetPos);
                if (mThreshold <= turn) { return; }
            }
            // 位置を更新しておく
            currentPos = targetPos;
             
            // 配達する
            mDeliverdCount++;
            mIsDeliverd[houseIndex] = true;
            mLargeUfoItemCount[aUfoIndex]--;
            mActions[turn].add(Action::Deliver(aUfoIndex, houseIndex));
             
            // もう荷物がない
            if (mLargeUfoItemCount[aUfoIndex] == 0) { break; }
             
            // 次の家をセット
            houseIndex = houseIndexNext;
        }
         
        // 残っているターンを適当に埋める
        while (turn < mThreshold) {
            mLargeUfoHistory[aUfoIndex][turn] = currentPos;
            mTargetPositions[turn++].add(currentPos);
        }
    }
 
    // 小さいUFOの経路計算
    void calcSmall(const Stage& aStage, int aUfoIndex, Random& aRandom)
    {
        // 初期化
        const Office& office = aStage.office();
        const UFO& ufo = aStage.ufos()[aUfoIndex];
        Vector2 currentPos = ufo.pos();
        int itemCount = ufo.capacity();
        int turn = 0;
        //
        Vector2 targetPos;
        int count = 0;
 
        // 最初のPickUp
        mActions[turn].add(Action::PickUp(aUfoIndex));
         
        // 次の家を選択しておく
        int houseIndex = getNearHouseIndex(aStage, currentPos, aRandom, turn, 65000.0f);
 
        // 家に移動 -> 配達のループ
        while (turn < mThreshold && houseIndex != sInvalid) {
            // 次の家までの情報を計算する
            const House& house = aStage.houses()[houseIndex];
            Vector2 toHouse = house.pos() - currentPos;
            float toHouseLength = toHouse.length() - house.radius() - ufo.radius() + sEpsilon;
            if (0.0f < toHouseLength) {
                toHouse.unitAssign(toHouseLength);
                targetPos = currentPos + toHouse;
                count = (int)(toHouseLength / ufo.maxSpeed()) + 1;
            } else {
                targetPos = currentPos;
                count = 0;
            }
             
            // 次の次の家を選択する
            int houseIndexNext = sInvalid;
            if (1 < itemCount) {
                mIsDeliverd[houseIndex] = true;
                houseIndexNext = getNearHouseIndex(aStage, targetPos, aRandom, turn, 1000.0f);
                mIsDeliverd[houseIndex] = false;
            }
 
            // 次の次の家の場所から次の家までの情報を計算しなおす
            if (houseIndexNext != sInvalid) {
                const House& house2 = aStage.houses()[houseIndexNext];
                const float x1 = currentPos.x;
                const float y1 = currentPos.y;
                const float x2 = house2.pos().x;
                const float y2 = house2.pos().y;
                const float a = y1 - y2;
                const float b = x2 - x1;
                const float c = -(a * x1 + b * y1);
                const float aabb = a * a + b * b;
                const float d = Math::Abs(a * house.pos().x + b * house.pos().y + c) / Math::Sqrt(aabb);
                const float r = ufo.radius() + house.radius() - sEpsilon;
                if (r < d) {
                    const Vector2 vec1 = currentPos - house.pos();
                    const Vector2 vec2 = house2.pos() - house.pos();
                    if (0.0f < vec1.squareLength()) {
                        targetPos = house.pos() + (vec1.unit() + vec2.unit()).unit(r);
                        count = (int)((targetPos - currentPos).length() / ufo.maxSpeed()) + 1;
                    }
                }
            }
 
            if (2 <= count) {
                count = count - 2;
                 
                // 直前の位置まで移動する
                for (int i=0; i<count; ++i) {
                    mTargetPositions[turn++].add(targetPos);
                    if (mThreshold <= turn) { return; }
                }
                // 位置を更新しておく
                currentPos += (targetPos - currentPos).unit(ufo.maxSpeed()) * count;
                 
                // 再度家までの距離を計算しなおす
                toHouse = house.pos() - currentPos;
                toHouseLength = toHouse.length() - house.radius() - ufo.radius() + sEpsilon;
 
                //
                const int restCount = (int)(toHouseLength / ufo.maxSpeed()) + 1;
 
                //
                if (0.0f < toHouseLength && restCount == 1) {
                    toHouse.unitAssign(toHouseLength);
                    targetPos = currentPos + toHouse;
                    count = 1;
                } else {
                    count = 2;
                }
            }
             
            // 移動する
            for (int i=0; i<count; ++i) {
                mTargetPositions[turn++].add(targetPos);
                if (mThreshold <= turn) { return; }
            }
            // 位置を更新しておく
            currentPos = targetPos;
 
            // 配達する
            mDeliverdCount++;
            mIsDeliverd[houseIndex] = true;
            itemCount--;
            mActions[turn].add(Action::Deliver(aUfoIndex, houseIndex));
             
            // 荷物がなくなった
            if (itemCount == 0) {
                const int needItemCount = 5 - itemCount;
                 
                // オフィスまでの位置を計算
                Vector2 toOffice = aStage.office().pos() - currentPos;
                float toOfficeLength = toOffice.length() - office.radius() - ufo.radius() + sEpsilon;
                if (0.0f < toOfficeLength) {
                    toOffice.unitAssign(toOfficeLength);
                    targetPos = currentPos + toOffice;
                    count = (int)(toOfficeLength / ufo.maxSpeed()) + 1;
                } else {
                    targetPos = currentPos;
                    count = 0;
                }
                 
                // ラージユーフォーが近ければそちらを使う
                bool isUseLargeUfo = false;
                int useLargeUfoIndex = 0;
                for (int largeUfoIndex = 0; largeUfoIndex < Parameter::LargeUFOCount; largeUfoIndex++) {
                    if (mLargeUfoItemCount[largeUfoIndex] < needItemCount) { continue; }
                    Vector2 targetPosTmp;
                    int countTmp = 0;
                    for (int i=0; i<count; ++i) {
                        if (mThreshold <= turn + i) { break; }
                        Vector2 toUfo = mLargeUfoHistory[largeUfoIndex][turn + i] - currentPos;
                        float toUfoLength = toUfo.length() - Parameter::LargeUFORadius - ufo.radius() + sEpsilon;
                        if (0.0f < toUfoLength) {
                            toUfo.unitAssign(toUfoLength);
                            targetPosTmp = currentPos + toUfo;
                            countTmp = (int)(toUfoLength / ufo.maxSpeed()) + 1;
                        } else {
                            targetPosTmp = currentPos;
                            countTmp = 0;
                        }
                         
                        if (i < countTmp) { continue; }
                         
                        targetPos = targetPosTmp;
                        count = i;
                        isUseLargeUfo = true;
                        useLargeUfoIndex = largeUfoIndex;
                         
                        break;
                    }
                }
                 
                // 次の家を選択する
                houseIndexNext = getNearHouseIndex(aStage, targetPos, aRandom, turn, 1000.0f);
                if (houseIndexNext == sInvalid) { break; }
                 
                // 次の家の場所からオフィスまでの情報を計算しなおす
                if (!isUseLargeUfo) {
                    const House& house2 = aStage.houses()[houseIndexNext];
                    const float x1 = currentPos.x;
                    const float y1 = currentPos.y;
                    const float x2 = house2.pos().x;
                    const float y2 = house2.pos().y;
                    const float a = y1 - y2;
                    const float b = x2 - x1;
                    const float c = -(a * x1 + b * y1);
                    const float aabb = a * a + b * b;
                    const float d = Math::Abs(a * office.pos().x + b * office.pos().y + c) / Math::Sqrt(aabb);
                    const float r = ufo.radius() + office.radius() - sEpsilon;
                    if (r < d) {
                        const Vector2 vec1 = currentPos - office.pos();
                        const Vector2 vec2 = house2.pos() - office.pos();
                        if (0.0f < vec1.squareLength()) {
                            targetPos = office.pos() + (vec1.unit() + vec2.unit()).unit(r);
                            count = (int)((targetPos - currentPos).length() / ufo.maxSpeed()) + 1;
                        }
                    }
                }
                 
                // 移動する
                for (int i=0; i<count; ++i) {
                    mTargetPositions[turn++].add(targetPos);
                    if (mThreshold <= turn) { return; }
                }
                // 位置を更新しておく
                currentPos = targetPos;
 
                // 荷物を集荷
                itemCount = ufo.capacity();
                if (isUseLargeUfo) {
                    mActions[turn].add(Action::Pass(useLargeUfoIndex, aUfoIndex));
                    mLargeUfoItemCount[useLargeUfoIndex] -= needItemCount;
                } else {
                    mActions[turn].add(Action::PickUp(aUfoIndex));
                }
            }
             
            // 次の家をセット
            houseIndex = houseIndexNext;
        }
         
        // 残っているターンを適当に埋める
        while (turn < mThreshold) {
            mTargetPositions[turn++].add(currentPos);
        }
    }
     
    // 次の家のIndexを取得する
    int getNearHouseIndex(const Stage& aStage, const Vector2& aPos, Random& aRandom, int aTurn, float aCoef)
    {
        const float rnd = (mThreshold - aTurn) / mThreshold * aCoef + 1.0f;
        int nearHouseIndex = sInvalid;
        float min = 9999999.9f;
        const int houseCount = aStage.houses().count();
        for (int i=0; i<houseCount; ++i) {
            if (mIsDeliverd[i]) { continue; }
            float length = aStage.houses()[i].pos().squareDist(aPos) + aRandom.randFloatTerm(rnd);
            if (length < min) {
                min = length;
                nearHouseIndex = i;
            }
        }
        return nearHouseIndex;
    }
     
    int mThreshold;
    int mDeliverdCount;
    bool mIsDeliverd[Parameter::MaxHouseCount];
    Vector2 mLargeUfoHistory[Parameter::LargeUFOCount][sThresholdMax];
    int mLargeUfoItemCount[Parameter::LargeUFOCount];
    Actions mActions[sThresholdMax];
    TargetPositions mTargetPositions[sThresholdMax];
    bool mIsFinish;
    int mCurrentIndex;
};
 
//------------------------------------------------------------------------------
// グローバル変数
Solver gSolver;
     
//------------------------------------------------------------------------------
Answer::Answer()
{
}
 
//------------------------------------------------------------------------------
Answer::~Answer()
{
}
     
//------------------------------------------------------------------------------
void Answer::init(const Stage& aStage)
{
    Random random(RandomSeed(0xf70c0303, 0x7b1cf62d, 0x727ff30d, 0x433d684d));
    for (int threshold = sThresholdMin; threshold <= sThresholdMax; threshold++) {
        for (int loopCount=0; loopCount<sLoopCount; loopCount++) {
            gSolver.init(aStage, threshold, random);
            if (gSolver.isFinish()) { return; }
        }
    }
}
 
//------------------------------------------------------------------------------
void Answer::moveItems(const Stage& aStage, Actions& aActions)
{
    gSolver.moveItems(aStage, aActions);
}
 
//------------------------------------------------------------------------------
void Answer::moveUFOs(const Stage& aStage, TargetPositions& aTargetPositions)
{
    gSolver.moveUFOs(aStage, aTargetPositions);
    gSolver.next();
}
 
//------------------------------------------------------------------------------
void Answer::finalize(const Stage& aStage)
{
}
 
//------------------------------------------------------------------------------
} // namespace
 
//------------------------------------------------------------------------------
// EOF