読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

Distributed Code Jam 2017, Round 1

f:id:n4_t:20170501012223p:plain

  • bBcCd-eE と提出して、コンテスト終了時点で70点280位。→C,Eがlarge落とされて21点626位。(5/15 11am暫定結果;Round2進出とTシャツGETならず)

A. Testrun (0pt)

https://code.google.com/codejam/contest/8314486/dashboard#s=p0

開いてない、というか使ってない

B. pancakes

https://code.google.com/codejam/contest/8314486/dashboard#s=p1
GCJではパンケーキ食べすぎてpancakesというだけではどんな問題だったか思い出せない

small (2pt; AC)

 ↓

large (11pt; submitted→AC)

・数列が途中で何回減ってるか数えるだけ?
・担当範囲を等分するときに継ぎ目の部分で1つ余分に調べる、とか
・GetNumDiners() いらない子では?

#include "0.cc" // 共通ライブラリ。実際はここに展開してる
#include "pancakes.h"

int main() {
    two_layers();
    return 0;
}

void run_impl(int level, NODEID parent, vector<NODEID> children) {
    int nN = NumberOfNodes();
    int me = MyNodeId();

    ll N = GetStackSize();

    if (level == 1) {
        Allocation alloc = allocate(children, N); // Nを子ノードに等分して送る
        int br = 0;
        int nActive = alloc.size();
        rep(i, nActive) {
            NODEID target = alloc[i].first;
            Receive(target);
            br += GetInt(target);
        }
        cout << br << endl;
    } else if (level == 2){
        llll range = get_range(); // 等分された区間を受け取る。(ノード数>Nの場合で、このノードに配当がなければexitする)
        int from = range.first, to = range.second;
        assert(from < to);

        int w = to - from;
        vector<ll> sti(w+1);
        for (int i=from; i<=to; ++i) {
            if (i == N) sti[i-from]=-1;
            else sti[i-from] = GetStackItem(i);
        }
        int br = 0;
        for (ll i=0; i<w; ++i) {
            if (sti[i] > sti[i+1]) ++br;
        }

        NODEID root = 0;
        PutInt(root, br);
        Send(root);
    }
}

C. weird_editor

https://code.google.com/codejam/contest/8314486/dashboard#s=p2
ウィアードという脳内発音とweirdという綴りが結びつかなくてtypo頻発

small (3pt; AC)

区間を等分。(ノード数の方が多かったら余ったノードは殺す)
・9 がいくつあるか、一番右の9はどこかを調べる
・一番右の9より右に、8がいくつあるか、一番右の8はどこかを調べる
・・・・
・一番右の2より右に、1がいくつあるか調べる
で、10進整数 `9*8*7*6*5*4*3*2*1*0*` が作れる。(メモリもったいないしこの整数を組み上げる必要はない)
あとは、各桁が (1e9+7) を法としていくつになるか、1の位から求めながら足しあげていくだけ

#include "0.cc"
#include "weird_editor.h"

int main() {
    two_layers();
    return 0;
}

#define MOD 1000000007LL

void run_impl(int level, NODEID parent, vector<NODEID> children) {
    int nN = NumberOfNodes();
    int me = MyNodeId();

    ll N = GetNumberLength();

    if (level == 1) {
        Allocation alloc = allocate(children, N);
        int nActive = alloc.size();

        vector<int> dcount(10, 0);
        int ofs = -1;
        for (int d=9; d>0; --d) {
            rep(i, nActive) {
                NODEID target = alloc[i].first;
                PutChar(target, d);
                PutInt(target, ofs);
                Send(target);
            }
            int cnt = 0;
            int rightmost = ofs;
            rep(i, nActive) {
                NODEID source = alloc[i].first;
                Receive(source);
                int lastofs = GetInt(source);
                if (lastofs >= 0) {
                    rightmost = max(rightmost, lastofs);
                }
                cnt += GetInt(source);
            }

            dcount[d] = cnt;
            ofs = rightmost;
        }

        int d0 = N;
        for (int d=9; d>0; --d) d0 -= dcount[d];
        dcount[0] = d0;

        ll base = 1LL;
        int k = 0;
        ll ans = 0LL;
        for (int d=0; d<=9; ++d) {
            int dc = dcount[d];
            rep(j, dc) {
                ++k;
                ans = (ans + base*d) % MOD;
                base = (base*10) % MOD;
            }
        }
        assert(k == N);

        cout << ans << endl;
    } else if (level == 2){
        llll range = get_range();
        int from = range.first, to = range.second;
        assert(from < to);

        int w = to - from; /// 1e7
        vector<char> ds(w);
        for (int i=from; i<to; ++i) {
            ds[i-from] = (char)GetDigit(i);
        }

        NODEID root = 0;
        for (int d=9; d>0; --d) {
            Receive(root);
            int _d = GetChar(root);
            assert(_d == d);
            int ofs = GetInt(root);

            int lastofs = -1;
            int cnt = 0;
            int _from = max(ofs+1, from);
            for (int i=_from; i<to; ++i) {
                if (ds[i-from] == _d) { ++cnt; lastofs = i; }
            }

            PutInt(root, lastofs);
            PutInt(root, cnt);
            Send(root);
        }
    }
}

large (20pt; submitted→X)

smallの解法だと(ノード数×10)往復のメッセージが飛び交うのだけれど
1往復が5ms x 2 = 10ms で 990往復なら9.9secでTLE、だよね…

子ノードで各区間について個別に、「9 がいくつあるか、一番右の9はどこか、一番右の9より右に8がいくつあるか、…」を調べて、vector(10) を返す。(0の数なんてどうでもいいからvector(9) でいいんだろうけど±1するのはバグの元)
これだけの情報があればいちいち問い合わせなくても親ノード側で再構成できる。

#include "0.cc"
#include "weird_editor.h"

int main() {
    two_layers();
    return 0;
}

#define MOD 1000000007LL

void run_impl(int level, NODEID parent, vector<NODEID> children) {
    int nN = NumberOfNodes();
    int me = MyNodeId();

    ll N = GetNumberLength();

    if (level == 1) {
        Allocation alloc = allocate(children, N);
        int nActive = alloc.size();

        vector<int> dcount(10, 0);

        vector<vector<int> > locals(100, vector<int>(10, 0));
        rep(i, nActive) {
            vector<int> local_dcount;
            NODEID source = receive_vec(-1, local_dcount, false); // vector<T>受信
            assert(local_dcount.size() == 10);
            locals[source] = local_dcount;
        }

        rep(i, nActive) {
            NODEID source = alloc[i].first;
            for (int d=9; d>0; --d) {
                int ld = locals[source][d];
                if (ld > 0) {
                    dcount[d] += ld;
                    for (int j=0; j<d; ++j) dcount[j] = 0;
                }
            }
        }
        int d0 = N;
        for (int d=9; d>0; --d) d0 -= dcount[d];
        dcount[0] = d0;

        ll base = 1LL;
        int k = 0;
        ll ans = 0LL;
        for (int d=0; d<=9; ++d) {
            int dc = dcount[d];
            rep(j, dc) {
                ++k;
                ans = (ans + base*d) % MOD;
                base = (base*10) % MOD;
            }
        }
        assert(k == N);

        cout << ans << endl;
    } else if (level == 2){
        NODEID root = 0;

        llll range = get_range();
        int from = range.first, to = range.second;
        assert(from < to);

        int w = to - from; /// 1e7
        vector<int> dcount(10, 0);

        for (int i=from; i<to; ++i) {
            int d = GetDigit(i);
            ++dcount[d];
            for (int i=0; i<d; ++i) dcount[i] = 0;
        }
        send_vec(root, dcount, false); // vector<T>送信
    }
}

D. todd_and_steven

https://code.google.com/codejam/contest/8314486/dashboard#s=p3

small (1pt; AC)

1ノードで全部取得してソートしてchecksum出しても間に合う

#include "0.cc"
#include "todd_and_steven.h"

int main() {
    standalone();
    return 0;
}

#define MOD 1000000007LL;

void run_impl(int level, NODEID parent, vector<NODEID> children) {
    int nN = NumberOfNodes();
    int me = MyNodeId();

    int ol = GetToddLength();
    int el = GetStevenLength();
    vector<ll> data(ol+el);
    rep(i, ol) data[i] = GetToddValue(i);
    rep(i, el) data[ol+i] = GetStevenValue(i);
    sort(all(data));
    ll sum = 0LL;
    rep(j, ol+el) {
        ll x = data[j] ^ j;
        sum = (sum + x) % MOD;
    }
    cout << sum << endl;
}

large (30pt; skipped)

先にE-smallやろうと思って飛ばした(そしてそのまま終了)

E. query_of_death

https://code.google.com/codejam/contest/8314486/dashboard#s=p4

small (4pt; AC)

ノード0: i=0から1つずつ、各100回見ていって、どこから狂ったか (=i_qod) を調べてノード1に教える(答えが全部同じなら信じる方式)
ノード1: 狂ってない i について先に GetValue(i) して取得してから最後に GetValue(i_qod) を求めて足して標準出力
ノード2以降: おやすみなさい

最悪ケースで1e4個x101回,で1.01e6回のGetValue() コールになるけど0.202秒だし大丈夫。
100回問い合わせて答えが全部同じなら信じる方式の100って別に根拠あるわけじゃないけど、2^26<10^8 <2^27 だから26あたりでは偶然全部同じになる可能性が普通にあるわけで。100回もやれば大丈夫でしょという。

#include "0.cc"
#include "query_of_death.h"

int main() {
    int nN = NumberOfNodes();
    int me = MyNodeId();

    ll N = GetLength();// 1e4

    if (me == 0) {
        vector<int> cnt(N, 0);
        int W = 100; // 1e6, 0.2s
        int broken = -1;
        rep(i, N){
            rep(j, W) {
                int b = GetValue(i);
                if (b) cnt[i]++;
            }
            if (cnt[i] == 0 || cnt[i] == W) continue;
            broken = i; break;
        }
        assert(broken >= 0);

        PutInt(1, broken);
        Send(1);
    }
    else if (me == 1) {
        Receive(0);
        int broken = GetInt(0);
        assert(broken >= 0);

        int sum = 0;
        rep(i, N) {
            if (i == broken) continue;
            int b = GetValue(i);
            sum += b;
        }
        fprintf(stderr, "broken=%d, sum=%d\n", broken, sum);

        sum += GetValue(broken);
        cout << sum << endl;
    }

    return 0;
}

void run_impl(int level, NODEID parent, vector<NODEID> children){
}

large (29pt; submitted→X)

同じ調べ方で1e8個x100回、を100ノードに分散しても、GetValue() コールは1ノードあたり20秒かかる。制限時間2秒では10回ずつしかやれない。これでは無理だ。

100等分(実際は99等分)した各区間ごとに和を求めて、壊れてるとこだけやり直す方式で、壊れているところをまた100等分(実際は98等分)、したら、二度目の壊れてる区間は高々1e4個だし、smallの解法で(0.2秒で)行ける範囲。
で、ある区間が壊れてるかどうかは、区間最初の値を覚えておいて、一旦(足し算しながら)スキャンした後に、最初の値を100回GetValue()して調べた。
最初の100等分時には1ノード辺り1e8/99+100≒1010201回、次の100等分時には1ノード辺り1010201/98+100=10408回のGetValue()呼び出しになる。合わせて1020609回で0.204秒。この後のsmall解法が0.202秒。
あとはメッセージ送受信にかかる時間が心配。(100個のノードとメッセージを2往復すると400x5msec=2.0秒とかかからない?5msecって送信したものが受信されるまでにかかる時間で、送信側をブロックする時間は高々1.3msecとか?なら大丈夫だけど)

腹痛のため最後のE-largeはトイレから提出。

#include "0.cc"
#include "query_of_death.h"

int main() {
    ll N = GetLength();
    int me = MyNodeId();

    if (N < 100) {
        if (me == 0) {
            vector<int> cnt(N, 0);
            int W = 100; // 1e6, 0.2s
            int broken = -1;
            rep(i, N){
                rep(j, W) {
                    int b = GetValue(i);
                    if (b) cnt[i]++;
                }
                if (cnt[i] == 0 || cnt[i] == W) continue;
                broken = i; break;
            }
            assert(broken >= 0);

            PutInt(1, broken);
            Send(1);
        }
        else if (me == 1) {
            Receive(0);
            int broken = GetInt(0);
            assert(broken >= 0);

            int sum = 0;
            rep(i, N) {
                if (i == broken) continue;
                int b = GetValue(i);
                sum += b;
            }
            fprintf(stderr, "broken=%d, sum=%d\n", broken, sum);

            sum += GetValue(broken);
            cout << sum << endl;
        }
    } else {
        two_layers();
    }

    return 0;
}

bool wee(int from, int to) { // トイレで書いた関数
    bool broken = false;
    ll sum = 0LL;

    if (from < to) {
        int w = to - from;
        ll v0;
        for (int i=from; i<to; ++i) {
            ll val = GetValue(i);
            sum += val;
            if (i == from) v0 = val;
        }

        int RP = 100;
        rep(i, RP) {
            ll val = GetValue(from);
            if (val != v0) { broken = true; break; }
        }
        // 2e-7 * (1e6 + 100) ~= 0.200(s)
    }

    NODEID root = 0;

    fprintf(stderr, "<< %d %lld\n", broken, broken ? 0LL : sum);
    PutChar(root, broken);
    PutLL(root, broken ? 0LL : sum);
    Send(root);

    return broken;
}

void run_impl(int level, NODEID parent, vector<NODEID> children) {
    int nN = NumberOfNodes();
    int me = MyNodeId();

    ll N = GetLength(); // 1e8

    if (level == 1) {
        Allocation alloc = allocate(children, N);

        int nActive = alloc.size();
        int broken_node = -1;
        ll sum = 0LL;
        rep(i, nActive) {
            NODEID _source = alloc[i].first;
            NODEID source = Receive(_source);
            bool is_broken = GetChar(source);
            if (is_broken) {
                broken_node = source;
            } else {
                ll localsum = GetLL(source);
                sum += localsum;
            }
        }
        assert(broken_node > 0);
        fprintf(stderr, "broken<1> = %d\n", broken_node);

        llll broken_range = alloc[broken_node-1].second;
        ll b_from = broken_range.first, b_to = broken_range.second;
        ll bw = b_to - b_from;

        ll each = ceil_quotient(bw, nActive-1); // (x+y-1)/yを返すやつ
        int nActive2 = ceil_quotient(bw, each);

        map<int,int> mp;
        int i = 0;
        tr(it, children) {
            NODEID target = *it;
            if (target == broken_node) {
                continue;
            }
            mp[target] = i;
            ll from = b_from + each*i;
            ll to = min(b_from + each*(i+1), b_to);
            // assert(from < to);
            if (from < to) {
                fprintf(stderr, ">>%d, [%lld .. %lld]\n", target, from, to);
                PutLL(target, from);
                PutLL(target, to);
                Send(target);
            } else {
                PutLL(target, -1LL);
                PutLL(target, -1LL);
                Send(target);
            }

            ++i;
        }
        assert(i >= 0);

        //
        int last_broken_node = broken_node;
        broken_node = -1;
        rep(i, nActive) {
            NODEID _source = alloc[i].first;
            if (_source == last_broken_node) continue;
            NODEID source = Receive(_source);
            bool is_broken = GetChar(source);
            if (is_broken) {
                broken_node = source;
            } else {
                ll localsum = GetLL(source);
                sum += localsum;
            }
        }
        assert(broken_node > 0);

        int bi = mp[broken_node];
        ll b2_from = b_from + each*bi;
        ll b2_to = min(b_from + each*(bi+1), b_to);
        fprintf(stderr, "broken<2> = %d : %d : %lld-%lld\n", broken_node, bi, b2_from,b2_to);

        int safe = 1;

        set<int> xs;
        xs.insert(last_broken_node);
        xs.insert(broken_node);
        while (found(xs, safe)) ++safe;

        {// small
            vector<int> cnt(N, 0);
            int W = 100; // 1e6, 0.2s
            int broken = -1;
            for (ll i=b2_from; i<b2_to; ++i) {
                rep(j, W) {
                    int b = GetValue(i);
                    if (b) cnt[i]++;
                }
                if (cnt[i] == 0 || cnt[i] == W) continue;
                broken = i; break;
            }
            assert(broken >= 0);

            for (int i=1; i<=nActive; ++i) {
                if (found(xs, i)) continue;
                if (i == safe) {
                    PutLL(i, sum);
                    PutInt(i, b2_from);
                    PutInt(i, b2_to);
                    PutInt(i, broken);
                } else {
                    PutLL(i, -1);
                    PutInt(i, -1);
                    PutInt(i, -1);
                    PutInt(i, -1);
                }
                Send(i);
            }
        }

    } else if (level == 2) {
        ll sum = 0;
        llll range = get_range();
        ll from = range.first, to = range.second;
        if (from == -1) goto hold_on;
        {
            assert(from < to);

            fprintf(stderr, "<1>[%lld .. %lld]\n", from, to);
            if (wee(from, to)) {
                cerr << "(broken 1)" << endl;
                return;
            }

            //
            Receive(0);
            ll b_from = GetLL(0);
            ll b_to = GetLL(0);
            if (b_from < 0) return;

            fprintf(stderr, "<2>[%lld .. %lld]\n", b_from, b_to);
            if (wee(b_from, b_to)) {
                cerr << "(broken 2)" << endl;
                return;
            }
        }
    hold_on:
        Receive(0);
        sum = GetLL(0);
        if (sum >= 0) {
            int b2_from = GetInt(0);
            int b2_to = GetInt(0);
            int broken = GetInt(0);
            for (int i=b2_from; i<b2_to; ++i) {
                if (i == broken) continue;
                sum += GetValue(i);
            }
            sum += GetValue(broken);
            cout << sum << endl;
        }
        //
    }
}