naoya_t@hatenablog

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

Facebook HackerCup 2018 - Round 1

7/22 2:00am JST〜(24時間)
法事の行き帰りの新幹線の中で参戦

2問通して35点獲得したので(時間や順位に関係なく)Round 2に進出。
というか自分の回りみんな35点だった(みんなやる気ない、あるいは3問目以降が激ムズ)
というか出てない人(ICFPCに没頭してて忘れてた人etc.)も結構いるのでは?
f:id:n4_t:20180723075644p:plain:w540

A - Let It Flow (15)

行きの新幹線で解いて提出。DP。
→AC

// 色々略
ll solve(int W, vector<string>& m) {
    vector<ll> dp(3, 0);
    dp[0] = 1;
    for (int x=0; x<W; ++x) {
        vector<ll> dp2(3, 0);
        if (m[0][x] == '.' && m[1][x] == '.') {
            dp2[0] = ADD(dp2[0], dp[1]);
            dp2[1] = ADD(dp2[1], dp[0]);
        }
        if (m[1][x] == '.' && m[2][x] == '.') {
            dp2[1] = ADD(dp2[1], dp[2]);
            dp2[2] = ADD(dp2[2], dp[1]);
        }
        dp = dp2;
    }
    return dp[2];
}

int main() {
    int T; cin >> T;
    rep(t,T){
        int N; cin >> N;
        vector<string> m(3);
        rep(i, 3) cin >> m[i];
        printf("Case #%d: %lld\n", 1+t, solve(N,m));
    }
    return 0;
}

B - Ethan Traverses a Tree (20)

帰りの新幹線で読んで、思いついた解法で帰宅後実装して提出。

  • pre-order, post-order でtraverseした結果をa, b とする
  • UnionFind
    • それぞれの i 番目(0≦i<N)、a_i, b_i をくっつける
    • 同じ島になったノード同士は同じ番号
    • 複数の島に同じ番号を割り振っても大丈夫
    • 島の数がK以上あれば行ける。なければ無理。

→AC

// 色々略
vi pre_order(int N, vi& left, vi& right) {
    vi res;
    stack<int> st;
    st.push(0);
    while (!st.empty()) {
        int curr = st.top(); st.pop();
        res.pb(curr);
        if (right[curr] != -1) {
            st.push(right[curr]);
        }
        if (left[curr] != -1) {
            st.push(left[curr]);
        }
    }
    return res;
}

vi post_order(int N, vi& left, vi& right) {
    vi res;
    stack<int> st;
    int curr = 0, last = -1;
    while (curr != -1 || !st.empty()){
        if (curr != -1) {
            st.push(curr);
            curr = left[curr];
        } else {
            int tmp = st.top();
            if (right[tmp] != -1 && last != right[tmp]) {
                curr = right[tmp];
            } else {
                res.pb(tmp);
                last = tmp; st.pop();
            }
        }
    }
    return res;
}

void solve(int N,int K,vi& left,vi& right) {
    vi pre = pre_order(N,left,right);
    vi post = post_order(N,left,right);

    UnionFind uf(N);
    rep(i,N) { uf.unionSet(pre[i], post[i]); }
    map<int,vi> R;
    rep(i,N) { R[uf.root(i)].pb(i); }

    vi roots;
    for (auto p: R){
        int root = p.first;
        roots.pb(root);
    }
    if (roots.size() < K) {
        printf(" Impossible\n");
        return;
    }
    // len(roots) >= K
    map<int,int> mp;
    rep(i, roots.size()) {
        mp[roots[i]] = min(1+i, K);
    }
    rep(i,N){
        printf(" %d", mp[uf.root(i)]);
    }
    printf("\n");
}

int main() {
    int T; cin >> T;
    rep(t,T){
        int N, K; cin >> N >> K;
        vi left(N), right(N);
        rep(i,N) {
            cin >> left[i] >> right[i];
            left[i]--; right[i]--;
        }
        printf("Case #%d:", 1+t);
        solve(N,K,left,right);
    }
    return 0;
}

C - Platform Parkour (28)

読みかけて寝落ち

D - Evening of the Living Dead (37)

読んでない