はじめに

おはこんばんにちは。テストが死んだLafoliaです。SuperCon予選にでました。実行時間はサンプルに対して0.50sec(4GHz環境)でした。やったことを書きます。

問題発表前

テスト直前って知ってますか？勉強したくないので勉強はしません。

発表当日

問題文を読みました。ディープラーニングさせたいらしいです。日本語が読めません。おわり。

ちょっと後

改めて問題を読むと諸々の設定がめちゃくちゃなことがわかります。大きな特徴は次の2点で、

活性化関数は0/1のステップ関数
重みは-1/1

です。これどういうことかというと、勾配が計算できません。つまりは逆伝播法が使えません重みが2値なのでシグモイドとかで近似するのも多分無理です。この方法で学習させるつもりがないことをなんとなく察しました。

やったこと

もうちょっと真面目に問題文を読むと、貪欲法(山登り法ですね)で解けって書いてありました。実装すると解ける(テストケースの結合がランダムに作られてるので解けないわけがない)ので、これを高速化すればいい気持ちになりました。

高速化

画期的なアルゴリズムを求めてくる声を聞きながらの高速化パートです。下にプログラムを貼ってあるので参考にしてください。

まずは高速化の初歩であるループ外しをします。早くなります。

次に計算値の再利用をします。n層とn+1層をつなぐ結合の重みを変えた場合、それ以前の層までの計算値は変化しないので、ここから計算するとシミュレーションが大幅に高速化されます。

(ここで何も思いつかなくなったので提出をしてしまいました。)

最後に変更する結合をランダムに選ぶことをやめます。ある結合が選ばれる回数の期待値は200回(結合の数が200コ)なので、この程度なら全探索を何回かやればいい気がします。乱数を得るのにも時間がかかるので、これでちょっとだけ早くなります。

(これ締切日の0時に出したんですけど再提出って受理されるんですかね？)

ここまでで画期的なアルゴリズムを何も思いつかないので実質的に敗北です。かなしいね。

ソースコード

はい

#include <array>
#include "sc1.h"

using namespace std;

const int_fast32_t complete = 6;
const int_fast32_t all_score = (4+complete)*10;
const array<int_fast32_t, 6> many = {6, 7, 7, 7, 7, 4};
array<array<bool,6>, 10> in;
array<array<bool,4>, 10> out;
array<array<array<int_fast32_t, 7>, 7>, 5> ans = {};
array<array<array<int_fast32_t, 7>, 6>, 10> check = {};

inline void sum(const int_fast32_t &id, const int_fast32_t &net, const int_fast32_t &&from) {
    check[id][net][0] += ans[net-1][from][0];
    check[id][net][1] += ans[net-1][from][1];
    check[id][net][2] += ans[net-1][from][2];
    check[id][net][3] += ans[net-1][from][3];
    check[id][net][4] += ans[net-1][from][4];
    check[id][net][5] += ans[net-1][from][5];
    check[id][net][6] += ans[net-1][from][6];

    return;
}

inline void sum(const int_fast32_t &id, const int_fast32_t &net) {
    if (check[id][net-1][0] > 0) sum(id, net, 0);
    if (check[id][net-1][1] > 0) sum(id, net, 1);
    if (check[id][net-1][2] > 0) sum(id, net, 2);
    if (check[id][net-1][3] > 0) sum(id, net, 3);
    if (check[id][net-1][4] > 0) sum(id, net, 4);
    if (check[id][net-1][5] > 0) sum(id, net, 5);
    if (check[id][net-1][6] > 0) sum(id, net, 6);

    return;
}


inline const int_fast32_t calc(const int_fast32_t &id) {
    int_fast32_t &&ret = ((check[id][5][0] > 0) == out[id][0]) +
                         ((check[id][5][1] > 0) == out[id][1]) +
                         ((check[id][5][2] > 0) == out[id][2]) +
                         ((check[id][5][3] > 0) == out[id][3]);

    return ret + (ret == 4) * complete;
}

inline void reset(const int_fast32_t &id, const int_fast32_t &net) {
    check[id][net][0] ^= check[id][net][0];
    check[id][net][1] ^= check[id][net][1];
    check[id][net][2] ^= check[id][net][2];
    check[id][net][3] ^= check[id][net][3];
    check[id][net][4] ^= check[id][net][4];
    check[id][net][5] ^= check[id][net][5];
    check[id][net][6] ^= check[id][net][6];

    return;
}

const int_fast32_t Simulation(const int_fast32_t &n) {
    int_fast32_t ret, id, net;
    ret = 0;
    for (id = 0; id != 10; ++id) {
        for (net = n+1; net != 6; ++net) {
            reset(id, net);
            sum(id, net);
        }

        ret += calc(id);
    }

    return ret;
}

inline void makeStartState() {
    int_fast32_t net, from, to, id;
    for (net = 0; net != 5; ++net) {
        for (from = 0; from != many[net]; ++from) {
            for (to = 0; to != many[net+1]; ++to) {
                ans[net][from][to] = (genrand_int31()&1) ? 1 : -1;
            }
        }
    }

    for (id = 0; id < 10; ++id) {
        for (from = 0; from < 6; ++from)
            check[id][0][from] = in[id][from];
    }

    return;
}

void Solve() {
    int_fast32_t net, from, to, score, maxi, change, search, turn;

    makeStartState();
    net = 0;
    score = Simulation(net);
    maxi = score;

    turn = 30;
    search = 5;
    while (--turn > 0 && score != all_score) {
        for (net = 0; net < 5; ++net) {
            for (from = 0; from < many[net]; ++from) {
                for (to = 0; to < many[net+1]; ++to) {
                    ans[net][from][to] *= -1;
                    search = min(search, net);
                    change = Simulation(search);
                    if (change > score) {
                        score = change;
                        maxi = max(maxi, change);
                        search = 5;
                        turn += 5;
                    } else if (change < score) {
                        ans[net][from][to] *= -1;
                    }

                    if (score == all_score) {
                        to = 9, from = 9, net = 4;
                    }
                }
            }
        }
    }

    if (score != all_score)
        return Solve();

    return;
}

int main() {
    SC_input();

    int_fast32_t problem, data, shift, net, to, from, cnt;
    init_genrand(614);
    for (problem = 0; problem < SC_n; ++problem) {
        for (data = 0; data < SC_NDATA; data += 2) {
            for (shift = 0; shift < 6; ++shift)
                in[data/2][shift] = (SC_prob[problem][data]>>shift)&1;
            for (shift = 0; shift < 4; ++shift)
                out[data/2][shift] = (SC_prob[problem][data+1]>>shift)&1;
        }

        Solve();
        cnt = 0;
        for (net = 0; net < 5; ++net)
            for (to = 0; to < many[net+1]; ++to)
                for (from = 0; from < many[net]; ++from)
                    SC_J[cnt++] = ans[net][from][to];
        SC_output();
    }

    return 0;
}

おわりに

ボーダー何秒だろうね。秒だとCPUの影響受けまくりなのでシミュレーション回数でアンケ取りたいお気持ち。

予選通ったらよろしくお願いしまうs。(通ってくれ)

Lafolia's 雑記

SuperCon2019予選参加記