あいをなくした。

あいをなくしたボカロP「あいなし」と、知識欲に飢えた大学生「アライさん」の週記です。

【参加したよ】天才魔導士からの入団試験 / バンダイナムコスタジオ【C++プログラミングコンテスト】

2020年8月12日

 今回は、株式会社バンダイナムコスタジオが行った「天才魔導士からの入団試験」を行いました。とりあえず新しい問題に取り組み、新しい知識がただほしかったので参加することにしました。  本当は、参加を始めたのは8月の上旬、丁度一週間くらい前の出来事だったのですが、この一週間をとってみても新曲の投稿だったり、大学生の課題の提出だったりと忙しい日々だったので、実質始めてから二日くらいと今日で三日くらいしか手を付けていないような状態だったりします。 (どれも言い訳です。最初滅茶苦茶難しすぎて最初二日手を付けても全然公開テストケースのスコアが取れなかったのであきらめてました。)

 この記事には、その記録を残していきたいと思います。

現状報告

 公開テストケースと実際に評価として用いる「正確さの平均」という値があるのですが、私は今まで公開テストケースばかりに目を向けていて正確さの平均に目を向けていなかった、まずはその事実から認めなければいけません。  正確さの平均は0が最小値、1が最大値となって数が大きければ大きいほど高評価となる値なのですが、これが開始二日目時点で0.42(長いので四捨五入)でした。正直、これは普通に低いのだろうな~と思っていたのですが、私が想像していた順位よりも高く、39人中18位でした。この事実を今日知って、私はただ単純に驚いてしまった次第です。私は少しでも順位を上げるために、制限時間がオーバーにならないようにするための対策を行いました。

2020年8月14日

現状報告

 一昨日提出したプログラムの結果、上位20%になりました(多分今だけ)。 今日は趣向を変えて点における識別から直線との距離を計測することを試してみたのですが、ダメでした。

…???

 と思われたのですが、午後三時ごろ、長い編集作業の末、公開テストケースでの正答率をわずかながらではありますが上げることに成功しました。また、一昨日提出したプログラムも非効率な箇所であったり、バグがあったため、それを反映したうえで提出しました。

2020年8月23日

現状報告

 前回以来、たいした進展がありませんでした。この間にかなり順位は落とされ、今となっては上位30%ラインも危うくなっていましたが、今日、ようやく駒を一つ動かすことが出来ました。  かなり重大なバグが残っていたため、すぐに修正、読み取り方をより効率的に、かつ、点で読み取っていた干渉計算を辺で読み取るように修正を行いました。  (実は辺で計算を行うこと自体は前からできていたのですが、ここに書くことを忘れていました。ごめんなさい。)  この時点で、識別精度はすべての公開ケースで80%を超え、その大半が90%も超える結果となりましたが、実行時間がかかってしまうことが欠点となっているようです。  私はすぐに、面での干渉計算を行うための準備を行います。

2020年9月12日

 なんか全然ブログの更新していなかったのであれ~?ってなりました。  結果として、私は300人以上いる中で見事ベスト20になることが出来ました。ありがとうございました。  昨日の上位入賞者懇親会はいろいろな話が聴けました。一番印象深かったのはどの人も目標を持ってこのコンテストに参加していた事とか、英語翻訳は機械の手ばかり借りるわけにもいかず、自分でリファレンスを翻訳していくしかない事とかがとても印象的でした。

 なんだかんだ楽しいコンテストでした。バンダイナムコスタジオの皆様、ありがとうございました。

 今回の参加賞は太鼓の達人パックマンのハンカチ2枚と未来小町のシール、付箋でした。大切に使わせていただきます。 f:id:H_J_Ainashi:20200919192832p:plain

今回の工夫ポイント

 ボクは計算速度を減らすことをあきらめ、各球の「交差してるっぽい」三角形を高速で選択した後、実際に交差してる割合を調べます。  昨日の表彰式で知ったのですが、この問題は一回当たりの計算速度を確実に減らし、無駄な計算は行わないという方針が重要だったらしく、最初からソートも行わずに期待値で突っ込むボクのやり方はなかなかイレギュラーな部類だったのではないのかな?と思う次第です。

提出したコード

#include <iostream>
#include <string>
#include <vector>
#include <memory>
#include <cmath>
#include <chrono>
#include <algorithm>
#include <random>

using namespace std;
using namespace chrono;

typedef long long Long;
const double scope = 30.0;
const Long scopeI = 30;
Long Pow2[20000 * scopeI + 1];

inline Long Scope(const double& src)
{

    return (Long)((src * scope) + 0.2);

}

inline Long GetPos(const double& src)
{

    return Scope(src + 10000.0);

}

const int
UNKNOWN = 0,
CLOSSED = 1,
UNCLOSS = 2;

struct Point
{

public:

    Long x, y, z;

    Point(const double& argx, const double& argy, const double& argz) :
        x(GetPos(argx)),
        y(GetPos(argy)),
        z(GetPos(argz)) {}

    Point(const Long& argx, const Long& argy, const Long& argz) :
        x(argx),
        y(argy),
        z(argz) {}

    Point() {}

};

inline Long MeasurePow2(const Point& a, const Point& b)
{

    return Pow2[abs(a.x - b.x)] + Pow2[abs(a.y - b.y)] + Pow2[abs(a.z - b.z)];

}

struct Triangle
{

public:

    bool IsClossed(const Point& center, const Long& radius) const
    {

        {

            auto inner = 0, outer = 0;
            auto fstSmaller = LLONG_MAX, sndSmaller = LLONG_MAX;
            auto fstSmIdx = 0, sndSmIdx = 0;

            for (int i = 0; i < 3; ++i)
            {

                Long length = MeasurePow2(center, vertex[i]);
                if (length < Pow2[radius]) ++inner;
                else if (length == Pow2[radius]) return true;
                else
                {

                    ++outer;

                    if (length <= fstSmaller)
                    {

                        sndSmaller = fstSmaller;
                        sndSmIdx = fstSmIdx;

                        fstSmaller = length;
                        fstSmIdx = i;

                    }
                    else if (length <= sndSmaller)
                    {

                        sndSmaller = length;
                        sndSmIdx = i;

                    }

                }

                if (!(!inner || !outer)) return true;

            }

            if (inner) return false;
            else if ((sndSmaller - fstSmaller) <= sidePow2[sndSmIdx][fstSmIdx])
            {

                auto buf = sndSmaller - fstSmaller + sidePow2[sndSmIdx][fstSmIdx];
                if (buf * buf >= ((sidePow2[sndSmIdx][fstSmIdx] * (sndSmaller - Pow2[radius])) << 2))
                    return true;

            }

        }

        Long bufr, bufs;
        Long buffer = (a * center.x) + (b * center.y) + (c * center.z) + d;
        if ((buffer * buffer) > Pow2[radius] * abcPow2) return false;

        /*

       Long ao_x = A->x - center.x, ao_y = A->y - center.y, ao_z = A->z - center.z;
       Long alpha2 = (ao_x * ba_x) + (ao_y * ba_y) + (ao_z * ba_z),
           beta2 = (ao_x * ca_x) + (ao_y * ca_y) + (ao_z * ca_z);

       if (k > 0)
           if ((beta2 * gamma) > (alpha2 * beta1) || (alpha2 * gamma) > (beta2 * alpha1))
               return false;
           else
               return ((alpha1 * beta2) + (alpha2 * beta1) - (gamma * (alpha2 + beta2))) <= k;
       else if (k < 0)
           if ((beta2 * gamma) < (alpha2 * beta1) || (alpha2 * gamma) < (beta2 * alpha1))
               return false;
           else
               return ((alpha1 * beta2) + (alpha2 * beta1) - (gamma * (alpha2 + beta2))) >= k;
       else return true;
       */

        //*

        Long alpha, rplus, rminus, splus, sminus;

        if (a != 0)
        {

            alpha = a;

            auto sa_y__b = (abcPow2 * (center.y - A->y)) - (b * buffer);
            auto sa_z__c = (abcPow2 * (center.z - A->z)) - (c * buffer);

            rplus = (sa_y__b * ca_z); rminus = (sa_z__c * ca_y);
            splus = (sa_z__c * ba_y); sminus = (sa_y__b * ba_z);

        }
        else if (b != 0)
        {

            alpha = b;

            auto sa_x__a = (abcPow2 * (center.x - A->x)) - (a * buffer);
            auto sa_z__c = (abcPow2 * (center.z - A->z)) - (c * buffer);

            rplus = (sa_x__a * ca_z); rminus = (sa_z__c * ca_x);
            splus = (sa_z__c * ba_x); sminus = (sa_x__a * ba_z);


        }
        else
        {

            alpha = c;

            auto sa_x__a = (abcPow2 * (center.x - A->x)) - (a * buffer);
            auto sa_y__b = (abcPow2 * (center.y - A->y)) - (b * buffer);

            rplus = (sa_x__a * ca_y); rminus = (sa_y__b * ca_x);
            splus = (sa_y__b * ba_x); sminus = (sa_x__a * ba_y);

        }

        if (alpha > 0)
            if (rplus >= rminus && splus >= sminus)
                if (rplus - rminus <= (alpha * abcPow2) - (splus - sminus))
                    return true;
                else;
            else;
        else
            if (rplus <= rminus && splus <= sminus)
                if (rplus - rminus >= (alpha * abcPow2) - (splus - sminus))
                    return true;

        return false;

        //*/
    }


    inline bool IsCheck(const Point& center, Long radius)
    {

        auto messure = MeasurePow2(center, gravity);

        if (Pow2[max(radius - length, (Long)0)] < messure && messure < Pow2[radius + length])
            return true;

        return false;

    }

    Triangle() {}

    Triangle(const Point& arga, const Point& argb, const Point& argc)
    {

        gravity = Point(((arga.x + argb.x + argc.x) / 3), ((arga.y + argb.y + argc.y) / 3), ((arga.z + argb.z + argc.z) / 3));

        vertex[0] = arga;
        vertex[1] = argb;
        vertex[2] = argc;

        A = &vertex[0];
        B = &vertex[1];
        C = &vertex[2];

        length = 0;

        for (int i = 0; i + 1 < 3; ++i)
        {
            for (int j = i + 1; j < 3; ++j)
            {

                sidePow2[i][j] = MeasurePow2(vertex[i], vertex[j]);
                sidePow2[j][i] = sidePow2[i][j];

            }

            length = max(MeasurePow2(gravity, vertex[i]), length);

        }
        length = (Long)((sqrt((double)length) + 0.2));

        ba_x = B->x - A->x;
        ba_y = B->y - A->y;
        ba_z = B->z - A->z;
        ca_x = C->x - A->x;
        ca_y = C->y - A->y;
        ca_z = C->z - A->z;

        a = (ba_y * ca_z) - (ca_y * ba_z);
        b = (ba_z * ca_x) - (ca_z * ba_x);
        c = (ba_x * ca_y) - (ca_x * ba_y);
        d = -((a * A->x) + (b * A->y) + (c * A->z));
        abcPow2 = a * a + b * b + c * c;

        /*

       alpha1 = Pow2[abs(ba_x)] + Pow2[abs(ba_y)] + Pow2[abs(ba_z)];
       beta1 = Pow2[abs(ca_x)] + Pow2[abs(ca_y)] + Pow2[abs(ca_z)];
       gamma = (ba_x * ca_x) + (ba_y * ca_y) + (ba_z * ca_z);
       k = (alpha1 * beta1) - (gamma * gamma);

       */
    }

private:

    Point gravity;
    Point vertex[3];
    Point* A, * B, * C;
    Long sidePow2[3][3];
    Long a, b, c, d,
        ba_x,           // B.x - A.x
        ba_y,           // B.y - A.y
        ba_z,           // B.z - A.z
        ca_x,           // C.x - A.x
        ca_y,           // C.y - A.y
        ca_z,           // C.z - A.z
        length,         // max(|AB|, |BC|, |CA|)
        abcPow2,        // a^2 + b^2 + c^2
        alpha1,
        beta1,
        gamma,
        k;

private:


    inline int IsClossed_VertexAndSide(const Point& center, const Long& radius) const
    {

        auto inner = 0, outer = 0;
        auto fstSmaller = LLONG_MAX, sndSmaller = LLONG_MAX;
        auto fstSmIdx = 0, sndSmIdx = 0;

        for (int i = 0; i < 3; ++i)
        {

            Long length = MeasurePow2(center, vertex[i]);
            if (length < Pow2[radius]) ++inner;
            else if (length == Pow2[radius]) return CLOSSED;
            else
            {

                ++outer;

                if (length <= fstSmaller)
                {

                    sndSmaller = fstSmaller;
                    sndSmIdx = fstSmIdx;

                    fstSmaller = length;
                    fstSmIdx = i;

                }
                else if (length <= sndSmaller)
                {

                    sndSmaller = length;
                    sndSmIdx = i;

                }

            }

            if (!(!inner || !outer)) return CLOSSED;

        }

        if (inner) return UNCLOSS;
        else if ((sndSmaller - fstSmaller) <= sidePow2[sndSmIdx][fstSmIdx])
        {

            auto buf = sndSmaller - fstSmaller + sidePow2[sndSmIdx][fstSmIdx];
            if (buf * buf >= ((sidePow2[sndSmIdx][fstSmIdx] * (sndSmaller - Pow2[radius])) << 2))
                return CLOSSED;

        }

        return UNKNOWN;


    }

};


class Sphere
{

private:

    Point center;
    vector<Triangle*> checked;

public:

    Long radius;

    inline int Count()
    {

        return checked.size();

    }

    inline void Register(Triangle* triangle)
    {

        if (triangle->IsCheck(center, radius))
            checked.push_back(triangle);

    }

    inline int IsClossed()
    {

        int ans = 0;

        for (auto check : checked)
        {

            if (check->IsClossed(center, radius))
                ++ans;

        }

        return ans;

    }

    Sphere(Point&& argc, const double& argr) :
        center(move(argc)),
        radius(Scope(argr)),
        checked() {}



};

int main(int argc, char* argv[])
{

    auto start = system_clock::now();

    for (Long i = 0, l = 20000 * scopeI + 1; i < l; i++)
        Pow2[i] = i * i;


    int n, q;
    cin >> n >> q;


    auto srcEnamies = new Triangle[n];
    auto enamies = vector<Triangle*>();
    auto launchers = vector<Sphere>();
    auto ans = new int[q];
    auto rand = mt19937_64();

    for (int i = 0; i < n; i++)
    {

        double p_ax, p_ay, p_az,
            p_bx, p_by, p_bz,
            p_cx, p_cy, p_cz;

        cin >> p_ax >> p_ay >> p_az >> p_bx >> p_by >> p_bz >> p_cx >> p_cy >> p_cz;

        srcEnamies[i] = Triangle(
            Point(move(p_ax), move(p_ay), move(p_az)),
            Point(move(p_bx), move(p_by), move(p_bz)),
            Point(move(p_cx), move(p_cy), move(p_cz))
        );

        enamies.push_back(&srcEnamies[i]);

    }

    if (n * q > 4000000) shuffle(enamies.begin(), enamies.end(), rand);


    for (int i = 0; i < q; i++)
    {

        double r, v_x, v_y, v_z;
        cin >> r >> v_x >> v_y >> v_z;
        ans[i] = -1;
        launchers.push_back(Sphere(Point(move(v_x), move(v_y), move(v_z)), r));

    }

    int registered, searched;
    double rate = 1.0, probability = 0.0;

    for (registered = 0; registered < n; registered++)
    {

        for (int j = 0; j < q; j++)
        {

            launchers[j].Register(enamies[registered]);

        }

        if (duration_cast<chrono::milliseconds>(system_clock::now() - start).count() > 8000)
        {

            ++registered;
            rate = ((double)n / (double)registered);

            break;

        }
    }



    for (searched = 0; searched < q; searched++)
    {

        const Long separator = 10 * scopeI;

        ans[searched] = launchers[searched].IsClossed();

        probability += ((double)ans[searched]) / (double)launchers[searched].Count();


        if (duration_cast<chrono::milliseconds>(system_clock::now() - start).count() > 9600)
        {

            ++searched;
            break;

        }

    }

    probability /= (double)searched;

    for (int i = 0; i < q; i++)
        if (ans[i] != -1)
            cout << ans[i] << endl;
        else
            cout << (Long)(((double)launchers[i].Count() * rate) * probability) << endl;

    return 0;


}