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

naoya_t@hatenablog

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

Distributed Code Jam, Round 1

5/29(日) 23:00〜26:00
(23:30過ぎまで寝てた…ここでの約35分のロストが痛い)
oo oo -- o- (33pts) で533位。あと一歩のところでRound 2進出ならず。
D-smallをsubmitしたのが2:58:17で、D-smallがACになるまで2分待たないとD-largeを投稿できない仕組みなのでD-largeが投稿できず。あと20秒あればD-large通せてたのに。
(D-large通さなくても、あと35分早ければ500位に食い込んでた…)
というわけで、今回の敗因は寝過ごし。通過できるレベルだっただけに無念。

ローカル環境の構築

message.hで定義されてるAPIのローカル実装は勉強がてら自前で。
ZeroMQというライブラリを使って実装しました;コードは割愛)

A. Testrun

先日practice roomが動いてた時に試してるのでパス;

B. oops

N個の64ビット値があって、それを使って何か計算して返すんだけど
するべき計算は問題文のサンプルコードを読み解いて把握しなければならない。
二重のforループで、i番目の要素とj番目の要素の差をマスターノードに送信して、マスターノード側で、送られてきた数の最大値を求めて表示している、ってことは、最大値と最小値を見つけて差を求めればよさそう。

long long GetN(); // [1..30000] or [1..1e9], (takes 0.05μs)
long long GetNumber(long long i); // [0..N-1], (takes 0.05μs)
  • 時間制限: 6sec
  • 使用ノード数: small/largeともに20ノード(この問題だけ例外。通常はsmall=10, large=100)
  • ノードあたりのメモリ制限: 128MB
  • ノードあたりの送信可能メッセージ数:1000
  • ノードあたりの送信可能メッセージ合計サイズ:8MB
small

GetNumber() を30000回呼んだところで1.5msecしかかからないので、1ノードで十分。

large

GetNumber() を1e9回呼んだら50秒かかってしまうが、20ノードに分散すれば各ノード2.5秒になってTLEを免れる。
それぞれのノードが読み込んだ部分集合内の最大値・最小値をマスターノードに送って、マスターノードで集計して全体での最大値・最小値を求め、その差を表示すればいい。
(small/largeともにAC)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

#include <message.h>
#include "oops.h"

#define RANGE_MIN -1000000000000000000LL
#define RANGE_MAX  1000000000000000000LL

int main(int argc, char **argv) {
    int nn = NumberOfNodes(), me = MyNodeId();

    int N = GetN(); // 1-30000, 1-1e9
    ll xmin = RANGE_MAX+1, xmax = RANGE_MIN-1;
    int w = (N + nn - 1) / nn;
    int from = w * me, to = from + (w-1);
    for (int i=from; i<=to; ++i) {
        if (i >= N) break;
        ll x = GetNumber(i);
        xmin = min(xmin, x);
        xmax = max(xmax, x);
    }
    PutLL(0, xmin);
    PutLL(0, xmax);
    Send(0);

    if (me == 0) {
        ll gmin = RANGE_MAX+1, gmax = RANGE_MIN-1;
        for (int i=0; i<nn; ++i) {
            int from = Receive(-1);
            ll xmin = GetLL(from);
            ll xmax = GetLL(from);
            gmin = min(gmin, xmin);
            gmax = max(gmax, xmax);
        }
        printf("%lld\n", gmax - gmin);
    }

    return 0;
}

C. rps

GCJ Round 2のじゃんけんトーナメント問題の類題。
N回戦で、2^N人が対戦するのだけれど、今回は、あいこの場合は左側が勝つことにして進める。

long long GetN(); // [1..10] or [1..28] (takes 0.09μs)
char GetFavoriteMove(long long id); // 'R', 'P' or 'S' (takes 0.09μs)
  • 時間制限: 3sec
  • 使用ノード数: small=10, large=100
  • ノードあたりのメモリ制限: 128MB
  • ノードあたりの送信可能メッセージ数:1000
  • ノードあたりの送信可能メッセージ合計サイズ:8MB
small

GetFavoriteMove() を 2^10回呼ぶと 9e-8 * 1e3 = 9e-5 = 90msec
これなら1ノードで片付くだろうし特に工夫はいらなさそう

large

GetFavoriteMove() を 2^28 回呼ぶと 9e-8 * 2.6e8 ≒ 24.2sec
これでは時間が足りない。100ノードで分割すれば各ノード0.24secなんだけど、
トーナメントの部分計算を対戦ブロックの切れ目でない所で切るのは無理だと思うので
2^nで分割したい。読み込みと部分計算に64ノード使って、集計に1ノード使って、残りの35ノードは捨てよう。
部分計算も集計も、トーナメントのシミュレーションをただやるだけだし、計算量は O(2^N)。
(small/largeともにAC)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

#include <message.h>
#include "rps.h"

int wins[3][3] = {
// R P S
  { 0, 1, 0 },
  { 1, 1, 2 },
  { 0, 2, 2 },
};

pair<int,int> solve(vector<int>& v, int w) {
    vector<int> ids(w);
    for (int i=0; i<w; ++i) ids[i] = i;

    while (w > 1) {
        w /= 2;
        for (int i=0; i<w; ++i) {
            int win = wins[ v[i*2] ][ v[i*2+1] ];
            ids[i] = (win == v[i*2]) ? ids[i*2] : ids[i*2+1];
            v[i] = win;
        }
    }
    return make_pair(v[0], ids[0]);
}

int main(int argc, char **argv) {
    int nn = NumberOfNodes(), me = MyNodeId();

    int N = GetN(); // 28
    int M = 1 << N;

    int sh = 0;
    switch (nn) {
        case 5: sh = 2; break;
        case 10: sh = 3; break;
        case 100: sh = 6; break;
        default:
        {
            int x = nn-1;
            while (x > 1) {
                x >>= 1; ++sh;
            }
            break;
        }
    }

    if (sh > N) sh = N;
    int nn_ = 1 << sh;
    if (me > nn_) return 0;

    map<char,int> num;
    num['R'] = 0;
    num['P'] = 1;
    num['S'] = 2;

    if (me == nn_) {
        vector<int> buf(nn_);
        vector<int> ids(nn_);
        for (int i=0; i<nn_; ++i) {
            int from = Receive(-1);
            buf[from] = GetChar(from);
            ids[from] = GetInt(from);
        }
        pair<int,int> winner = solve(buf, nn_);
        printf("%d\n", ids[winner.second]);
    } else {
        int w = M >> sh; // 1 << (N - sh);
        vector<int> buf(w);
        int from = me * w, to = from + w - 1;
        for (int i=from; i<=to; ++i) {
            buf[i-from] = num[ GetFavoriteMove(i) ];
        }
        pair<int,int> winner = solve(buf, w);
        PutChar(nn_, winner.first);
        PutInt(nn_, from + winner.second);
        Send(nn_);
    }

    return 0;
}

D. crates

挑戦者数が少なかったのでパスしてEへ

E. winning_move

N人のプレイヤーが、それぞれ正の整数を1つ言う。他の誰とも違う一番小さな数を言ったプレイヤーの勝ち。
各プレイヤーが言った数から、勝ったプレイヤーの言った数を求める。勝者なしなら0を返す。

long long GetNumPlayers(); // [1..1000] or [1..35000000] (takes 0.12μs)
long long GetSubmission(long long playernum); // [1..1e18] (takes 0.12μs)
  • 時間制限: 4sec
  • 使用ノード数: small=10, large=100
  • ノードあたりのメモリ制限: 1GB
  • ノードあたりの送信可能メッセージ数:1000
  • ノードあたりの送信可能メッセージ合計サイズ:1GB
small

GetSubmission() を1000回呼んでも0.12msecなので、1ノードで十分。

large

GetSubmission() を3500万回呼んだら 3.5 x 1.2 = 4.2sec。1ノードでは足りないが、100ノードも必要なわけでもない。複数ノードで分割統治。
それぞれのノードが読み込んだ数とその回数の統計情報をマスターノードに伝えて、マスターノードで集計して勝者を求める。
smallをsubmitした時点で残り2分を切っていて、largeをsubmitできないまま終了。
(あと30秒あれば…これsubmitすれば多分通ってたと思うんだけど…orz)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

#include <message.h>
#include "winning_move.h"

int main(int argc, char **argv) {
    int nn = NumberOfNodes(), me = MyNodeId();
    int N = GetNumPlayers(); // 1 - 1000 or 35000000

    int w = (N + nn - 1) / nn;
    int from = w * me, to = from + (w-1);

    map<ll,int> st;
    for (int i=from; i<=to; ++i) {
        if (i >= N) break;
        ll x = GetSubmission(i);
        st[x]++;
    }
    vector<ll> q, bd;
    PutInt(0, st.size());
    tr(it, st) {
      PutLL(0,it->first);
      PutInt(0,it->second);
    }
    Send(0);

    if (me == 0) {
        map<ll, int> st;
        for (int i=0; i<nn; ++i) {
            int from = Receive(-1);
            int qz = GetInt(from);
            rep(j, qz) {
                ll x = GetLL(from);
                int y = GetInt(from);
                st[x] += y;
            }
        }
        set<ll> s;
        tr(it,st){
            if (it->second == 1) {
                s.insert(it->first);
            }
        }
        if (s.empty()) {
            printf("0\n");
        } else {
            printf("%lld\n", *s.begin());
        }
    }
    return 0;
}