naoya_t@hatenablog

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

Facebook Hacker Cup 2017 Round 2

第2回戦。

全4問。上位200位以内で通過、500位以内でTシャツGET。
狙いはTシャツ。

→588位でTシャツGETならず。
(通過ラインはA+C,A+D,B+Dの2問かA+Bの速解き;TシャツラインはAの速解き)

Subtle Sabotage (12点) (AC)

Subtle Sabotage | Facebook Hacker Cup 2017 Round 2

N+M-2 って (N-1) + (M-1) 、即ち、右と下にだけ進めるならどこをどう通ってもN+M-2になる。ってことは、左か上に進ませるように妨害すれば良い。
S字に進まざるを得ないようにどこか一箇所に障害コースを設置。
K=1の時と2以上の時で必要なブロック数が変わる。

本当にそれでいいのか提出に慎重になってた分、少し時間をロスした。
(書いてすぐ自信をもってsubmitできていたらTシャツに手が届いていたかも。でもそれが実力というもの)

#include <iostream>
#include <cstdio>
using namespace std;

#define INFTY 999999

int sub1(int N, int M, int K) {
    if (N < K+1) return INFTY;
    if (M < 2*K+3) return INFTY;
    return (N + K-1) / K;
}

int sub2(int N, int M, int K) {
    if (N < 3*K+2) return INFTY;
    if (M < 2*K+1) return INFTY;
    if (K == 1) return 5;
    return 4;
}

int solve(int N, int M, int K) {
    int ans = INFTY;
    ans = min(ans, sub1(N, M, K));
    ans = min(ans, sub1(M, N, K));
    ans = min(ans, sub2(N, M, K));
    ans = min(ans, sub2(M, N, K));
    if (ans == INFTY) ans = -1;
    return ans;
}
int main() {
    int T; cin >> T;
    for (int t=1; t<=T; ++t) {
        int N, M, K; cin >> N >> M >> K;
        printf("Case #%d: %d\n", t, solve(N, M, K));
    }
    return 0;
}

Big Top (22点) (opened)

Big Top | Facebook Hacker Cup 2017 Round 2

折れ線(線分集合)を管理する方向で実装。
取れそうな気がしたんだけど実装がもつれて時間切れ。

(スパゲティコード割愛)

あとがたり

終了後、そのままの方針で書き進めたコードは、数は合うんだけど(低木が並ぶような)最悪ケースで全然進まない…

Editorialを見たら、(隣接する柱の間の)谷の位置は(簡単な一次式で求まるわけだから)保持する必要がないと気づいた。
あと、vector + lower_bound + insert/erase では遅かった。

vectorをsetに変えてみる。setってiteratorでincrement出来るのは知ってたけどdecrement出来るのは知らなかった。
あれ?前より遅くなってる… lower_boundがそのままだからか。とりあえずinsertしてから考えればいいわけだし、insertの返り値にiterator入ってるしそれを使えば…
入力データ(Case #305まであるぞ… T≦150 じゃなかったっけ?)が1分弱で処理できるようになった…
と思ったら答え違う…精度が悪いのか。long doubleじゃないとダメなのか。
double を long doubleに変えて無事AC。

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(e,s)  ((s).find(e)!=(s).end())
#define cons make_pair
#define car first
#define cdr second
#define sz(x)  (int)((x).size())

typedef long long ll;
typedef pair<int, int> ii;
typedef long double Double;

// #define DEBUG 1

#ifdef DEBUG
#undef NDEBUG
#endif
#include <cassert>

#define INFTY 19999999

inline Double area(int x0, int h0, int x1, int h1) {
    Double s0, s1;
    if (x0 + h0 <= x1 - h1) {
        s0 = 0.5 * h0 * h0;
        s1 = 0.5 * h1 * h1;
    } else {
        Double mx = 0.5 * ((x0+h0) + (x1-h1));
        Double mh = 0.5 * ((x0+h0) - (x1-h1));
        s0 = 0.5 * (mx - x0) * (h0 + mh);
        s1 = 0.5 * (x1 - mx) * (mh + h1);
    }
    return s0 + s1;
}

#define x first
#define h second

Double solve(int N, vector<int>& X, vector<int>& H) {
    set<ii> xs;
    xs.insert(cons(-INFTY, 0));
    xs.insert(cons(+INFTY, 0));

    Double total = 0.0, s = 0.0;

    rep(i, N) {
        int xi = X[i], hi = H[i];

        auto it = xs.insert(cons(xi, hi)).first;
        auto left = it; --left;
        auto right = it; ++right;

        if (left->h - (xi - left->x) >= hi || right->h - (right->x - xi) >= hi) {
            xs.erase(it);
            goto sum_up;
        }

        s -= area(left->x, left->h, right->x, right->h);

        // west
        while (true) {
            if (hi - (xi - left->x) >= left->h) {
                // swallow it
                auto next = left; --next;
                s -= area(next->x, next->h, left->x, left->h);
                xs.erase(left--);
                continue;
            }
            break;
        };

        // east
        while (true) {
            if (hi - (right->x - xi) >= right->h) {
                auto next = right; ++next;
                s -= area(right->x, right->h, next->x, next->h);
                xs.erase(right++);
                continue;
            }
            break;
        }

        s += area(left->x, left->h, xi, hi);
        s += area(xi, hi, right->x, right->h);

    sum_up:
        total += s;
    }

    return total;
}

int main(int argc, char **argv) {
    int T; cin >> T;

#if 0
    int N = 3;
    vector<int> X(3), H(3);
    X[0] = 20; H[0] = 10;
    X[1] = 30; H[1] = 15;
    X[2] = 24; H[2] = 3;
    Double ans = solve(N, X, H);
    printf("Case #%d: %.2Lf\n", 0, ans);
    return 0;
#endif

    for (int t=1; t<=T; ++t) {
        int N; cin >> N;
        ll X1, Ax, Bx, Cx; cin >> X1 >> Ax >> Bx >> Cx;
        ll H1, Ah, Bh, Ch; cin >> H1 >> Ah >> Bh >> Ch;

        vector<int> X(N), H(N);
        X[0] = (int)X1; H[0] = (int)H1;
        for (int i=1; i<N; ++i) {
            X[i] = (int)((Ax * X[i-1] + Bx) % Cx) + 1LL;
            H[i] = (int)((Ah * H[i-1] + Bh) % Ch) + 1LL;
        }
        Double ans = solve(N, X, H);

        // printf("Case #%d: %.2f\n", t, ans);
        char buf[80];
        sprintf(buf, "Case #%d: %.2Lf", t, ans);
        int len = strlen(buf);
        if (buf[len-1] == '0' && buf[len-2] == '0') buf[len-1] = 0;
        printf("%s\n", buf);
    }
    return 0;
}

Fighting all the Zombies (29点) (not opened)

Fighting all the Zombies | Facebook Hacker Cup 2017 Round 2

開いてない

Rain Over New York (37点) (not opened)

Rain Over New York | Facebook Hacker Cup 2017 Round 2

開いてない