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

Facebook Hacker Cup 2017 Round 1 - Manic Moving

競プロ

問題

Manic Moving | Facebook Hacker Cup 2017 Round 1

考察

まずは、各都市間の最小移動コストを出します。
N=100と小さいので、ワーシャルフロイドで簡単に求まります。

制約として、荷物は最大2組まで積み込めますが、積み込み・荷降ろしはそれぞれ順番に行われる必要があります。
ややこしく見えますが、積み込み・荷降ろしは独立していることを活かすと、次のようなDPが考えられます。

dp[i][j][k] := i個目まで荷降ろしが完了し、現在j組の荷物が乗っていて、k番目の都市にいる時の最小コスト

状態遷移としては、まず「積み込み」を考えます。
積み込みの時は荷降ろしは考えないので、iは変更されません。 現在いる都市(k)と、次に積みこむ都市(lp)はjが決まっていればすぐわかるので、jが増える方向に更新をします。

min: dp[i][j+1][lp] = dp[i][j][k] + dist[k][lp]

1個、2個の場合の積み込みを計算し終わったら、荷降ろしに移ります。
これはjを減らし、iを1増やす更新です。
同じ都市で2個降ろせる場合もありますが、そのような場合でも1つずつ考慮することで簡単になります(移動コストが0なので上手く行く)。
lpは次に荷降ろしをするべき都市なので、iを見ると簡単に求まります。

min: dp[i+1][j-1][lp] = dp[i][j][k] + dist[k][lp]

このようにDP表を更新すると、最後に荷降ろしする都市でのコストが答えになります。

コード

ll solve() {
    int N, M, K;
    cin >> N >> M >> K;

    const ll INF = 1ll << 60;
    vvll dist(N, vll(N, INF));
    rep(i, N)dist[i][i] = 0;

    rep(i, M) {
        int a, b, g;
        cin >> a >> b >> g;
        --a, --b;
        chmin(dist[a][b], (ll)g);
        chmin(dist[b][a], (ll)g);
    }

    rep(k, N) {
        rep(i, N) {
            rep(j, N) {
                chmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    vector<pii> fam(K);
    rep(i, K) {
        int s, d;
        cin >> s >> d;
        --s, --d;
        fam[i] = mp(s, d);
    }

    vector<vvll> dp(K+1, vvll(3, vll(N, INF)));
    dp[0][0][0] = 0;

    rep(i, K) {
        // load
        rep(j, 3-1) {
            int next = i + j;
            if(next >= K)
                continue;
            int lp = fam[next].first;
            rep(k, N) {
                if(dp[i][j][k] >= INF)
                    continue;
                chmin(dp[i][j+1][lp], dp[i][j][k] + dist[k][lp]);
            }
        }

        // unload
        REP(j, 1, 3) {
            int next = i;
            if(next >= K)
                continue;
            int lp = fam[next].second;
            rep(k, N) {
                if(dp[i][j][k] >= INF)
                    continue;
                chmin(dp[i+1][j-1][lp], dp[i][j][k] + dist[k][lp]);
            }
        }
    }

    ll ans = dp[K][0][fam[K-1].second];
    if(ans >= INF)
        return -1;
    else
        return ans;
}


int main() {
    int T;
    cin >> T;
    rep(__t, T) {
        cout << "Case #" << __t + 1 << ": ";
        cout << solve() << endl;
    }

    return 0;
}

感想

普通に引越し屋さんとかで使えそうです。

Facebook Hacker Cup 2017 Round 1 - Fighting the Zombies

競プロ

問題

Fighting the Zombies | Facebook Hacker Cup 2017 Round 1

考察

円で移動させ、四角で攻撃するので、少し厄介な感じがします。
が、円の大きさは自由、四角の大きさは正方形で決まっています。
移動させる範囲が所定の正方形より大きくても結局攻撃できないため、同じ大きさの四角を移動させると考えても問題ありません。

うまく円の大きさや位置をいじることで、正方形x2の片方に含まれるゾンビをもう片方の正方形に移動できます。
きちんと証明するのは厄介そうですが、なんとなくイメージではできそうです。

結局この問題は、一辺がRの正方形を2つ取り出して、それらに含まれるゾンビが最大になるようにすればよいです。

まず、正方形を列挙することから始めます。
存在するゾンビのx座標、y座標全ての組み合わせを左下座標とすると、抜け漏れ無く正方形が作れます。
このとき併せて内部に幾つゾンビがいるか調べておきます。
 O(N^{3})

次に、そこから2つ正方形を取り出し、含まれるゾンビを調べます。
基本的には足し合わせれば良いですが、両方の領域にまたがっているゾンビがいると、それらを引く必要があります。
四角形の交差判定などを利用して、かぶっている範囲を求めて減算しました。
 O(N^{4} * N)

トータルで O(N^{5})となり、 N \leq 50なので間に合います。

注意点として、ゾンビが1体しかいない場合に1と出るようにしないといけません。
私はこれで落としました。

コード

int solve() {
    int N, R;
    cin >> N >> R;

    vector<pii> points(N);
    set<int> sx, sy;
    rep(i, N) {
        int x, y;
        cin >> x >> y;
        points[i] = mp(x, y);
        sx.insert(x);
        sy.insert(y);
    }

    sort(all(points));

    vector<pair<pii, int> > boxes;
    tr(it, sx) {
        tr(it2, sy) {
            int x = *it;
            int y = *it2;

            int c = 0;
            rep(i, N) {
                if(x <= points[i].first && points[i].first <= x + R &&
                    y <= points[i].second && points[i].second <= y + R) {
                    c++;
                }
            }

            if(c > 0)
                boxes.push_back(mp(mp(x,y), c));
        }
    }

    const int sz = boxes.size();
    int ans = 0;

    rep(i, sz) {
        // only one
        chmax(ans, boxes[i].second);

        REP(j, i+1, sz) {
            // collision
            pii p1 = boxes[i].first;
            pii p2 = boxes[j].first;
            double cx1 = (double)p1.first + (double)R / 2;
            double cx2 = (double)p2.first + (double)R / 2;
            double cy1 = (double)p1.second + (double)R / 2;
            double cy2 = (double)p2.second + (double)R / 2;

            int cnt = boxes[i].second + boxes[j].second;

            if( abs(cx1 - cx2) <= R && abs(cy1 - cy2) <= R) {
                if(p1 > p2)
                    swap(p1, p2);

                pii s = mp(-1,-1);
                pii e = mp(-1, -1);
                if(p1.second <= p2.second && p2.second <= p1.second + R) {
                    s = p2;
                    e = mp(p1.first+R, p1.second+R);
                }
                else {
                    s = mp(p2.first, p1.second);
                    e = mp(p1.first+R, p2.second+R);
                }

                rep(i, N) {
                    int x = points[i].first;
                    int y = points[i].second;
                    if(s.first <= x && x <= e.first &&
                            s.second <= y && y <= e.second)
                        cnt--;
                }
            }

            chmax(ans, cnt);
        }
    }

    return ans;
}


int main() {
    int T;
    cin >> T;
    rep(__t, T) {
        cout << "Case #" << __t + 1 << ": ";
        cout << solve() << endl;
    }

    return 0;
}

感想

幾何か!?と思って身構えましたが、そこまで幾何ではなかったです。
もっとすっきり書けそうな気もします……。

Facebook Hacker Cup 2017 Round 1 - Pie Progress

競プロ

問題

Pie Progress | Facebook Hacker Cup 2017 Round 1

考察

購入する必要があるパイの個数は、日数と同じです。
N日間の中のどこでいくつ買うかを決定するので、以下のDPで処理できそうです。

dp[i][j] := i日目までにj個パイを買った場合の最小コスト

各日数でそれぞれのパイを買うかを試したいですが、普通にやっては計算量が増えすぎます。
そこで、「高いパイを買う必要はない」「追加コストは個数にのみ依存」という2点を活かすと、以下のような更新ができます。

  1. 最小コストのパイを取ってくる
  2. コストから00を引き、11を足す
  3. 1個買ったものとして、DP表を更新
  4. 次に小さいコストのパイを取ってくる
  5. コストから11を引き、22を足す
  6. 2個かったものとして、DP表を更新
  7. ...

このように、直前の個数の追加コストを引いてから新しく足すと、順番に処理できます。
更新し終わったDP表のdp[N][N]が答えになります。
priority_queueなどを使えば取り出しはO(logN)なので、全体で  O(T * N^{2} * logN) となり間に合いそうです。

なお、注意点として、「餓死するケース」を考える必要があります。
i日目の時点で買ったパイがi個未満だと餓死するので、そのケースは答えに含めないようにします。

コード

ll solve() {
    int N, M;
    cin >> N >> M;

    const int mN = N + 10;

    vector< priority_queue<int, vi, greater<int> > > pies(N);
    rep(i, N) {
        rep(j, M) {
            int t;
            cin >> t;
            pies[i].push(t);
        }
    }

    const ll INF = 1ll<<60;

    vvll dp(mN, vll(mN, INF));
    dp[0][0] = 0;

    rep(i, N) {
        // 0
        rep(j, mN)
            dp[i+1][j] = dp[i][j];

        const int sz = (int)pies[i].size();

        int cost = 0;
        rep(k, sz) {
            cost += pies[i].top();
            pies[i].pop();
            cost -= k*k;
            cost += (k+1)*(k+1);

            rep(j, mN) {
                int next = j + k + 1;
                if (dp[i][j] != INF && next < mN) {
                    chmin(dp[i+1][next], dp[i][j] + cost);
                }
            }
        }

        // check
        rep(j, i+1) {
            dp[i+1][j] = INF;
        }
    }

    return dp[N][N];
}

int main() {
    int T;
    cin >> T;
    rep(__t, T) {
        cout << "Case #" << __t + 1 << ": ";
        cout << solve() << endl;
    }

    return 0;
}

感想

思考停止DPで解きました。
オーダーがこれより大きくても、実行時間にゆとりはあるので通せそうです。

Facebook Hacker Cup 2017 Qualification Round - Fighting the Zombie

競プロ

問題

Fighting the Zombie | Facebook Hacker Cup 2017 Qualification Round

考察

Zは出目の合計を足した後に加算されるので、同じサイコロに対してX回振った場合の確率分布は一定になります。

dp[i][j] := i回同じサイコロを振った時に、合計が値jになる確率

これは、20回 * 400(出目の合計の最大) = 8000程度の大きさのテーブルで保持できます。 それぞれのマスに対して最大で20通りの状態遷移があるため、 20 * 8000 = 1 * 10^{5}程度で計算できそうです。

T=1000なので、毎回与えられる度に計算をしても間に合いそうではありますが、
サイコロの種類は限られているので、それぞれに対してテーブルをメモしておけばより速く計算できます。

最終的な答えは、それぞれの試行でこのテーブルを参照し、H-Z以上のマスを合計してゆけば確率が算出されます。
なお、H-Zが0より小さくなったり、400より大きくなったりするので、適当にmin/maxを取る必要があり要注意です。

コード

class DiceTable {
public:
    const int MAX_N = 21;
    const int MAX_C = MAX_N * 20 + 10;

    map<int, vvd> diceTable;

    DiceTable() {
        vi t = {4, 6, 8, 10, 12, 20};
        rep(i, t.size())
            prepare(t[i]);
    }

    void prepare(int dice) {
        vvd prop(MAX_N, vd(MAX_C, 0.0));
        prop[0][0] = 1.0;

        double one_p = 1.0 / dice;

        rep(i, MAX_N - 1) {
            rep(j, MAX_C) {
                REP(v, 1, dice + 1) {
                    if (prop[i][j] != 0.0 && j + v < MAX_C)
                        prop[i+1][j + v] += prop[i][j] * one_p;
                }
            }
        }

        diceTable[dice] = prop;
    }

    double calc(int dice, int num, int base) {
        double res = 0.0;
        vvd& dt = diceTable[dice];
        REP(i, max(0,base), MAX_C)
            res += dt[num][i];
        return res;
    }
};

double solve() {
    int H, S;
    cin >> H >> S;

    DiceTable dt;
    double ans = 0.0;

    rep(i, S) {
        string s;
        cin >> s;

        stringstream ss, ss2, ss3;
        int x = 0, y = 0, z = 0;
        rep(j, s.size()) {
            if(s[j] == 'd')
                break;
            ss << s[j];
        }
        ss >> x;

        REP(j, ss.str().size()+1, s.size()) {
            if(s[j] == '-' || s[j] == '+')
                break;
            ss2 << s[j];
        }
        ss2 >> y;

        REP(j, ss.str().size() + ss2.str().size() + 1, s.size())
            ss3 << s[j];
        if(!ss3.str().empty())
            ss3 >> z;

        double res = dt.calc(y, x, H - z);
        chmax(ans, res);
    }

    return ans;
}

int main() {
    int T;
    cin >> T;
    rep(__t, T) {
        cout << "Case #" << __t + 1 << ": ";
        cout << solve() << endl;
    }

    return 0;
}

感想

シンプルなDPでした。
DP部分より数値をパースする所の方が面倒です。

Facebook Hacker Cup 2017 Qualification Round - Lazy Loading

競プロ

問題

Lazy Loading | Facebook Hacker Cup 2017 Qualification Round

考察

一番上の重さだけが関係あり、他は個数しか見られません。
そのため、「一番上に手持ちの一番重たいもの」を使い、残りは個数だけ見て、「軽いものから順番に」使って50ポンドを超えたら止めればよいです。

このような処理は事前にソートしておいて、dequeに詰めると楽ちんです。

コード

int solve() {
    int N;
    cin >> N;

    vi W(N);
    rep(i, N)
        cin >> W[i];

    sort(all(W), greater<int>());
    deque<int> deq;
    rep(i, N)
        deq.push_back(W[i]);

    int ans = 0;
    while(!deq.empty()) {
        int f = deq.front();
        deq.pop_front();

        int rem = (int)ceil(50.0 / f);
        if(deq.size() < rem - 1)
            break;

        ans++;

        rep(i, rem-1) {
            deq.pop_back();
        }
    }

    return ans;
}

int main() {
    int T;
    cin >> T;
    rep(__t, T) {
        cout << "Case #" << __t + 1 << ": ";
        cout << solve() << endl;
    }

    return 0;
}

感想

Aより簡単に見えるので何とも不安になる問題でした。

Facebook Hacker Cup 2017 Qualification Round - Progress Pie

競プロ

問題

https://www.facebook.com/hackercup/problem/1254819954559001/

考察

基本的には角度を取って比較すれば良さそうに見えます。
0°の線を基準とした角度で図りますが、180°を超えると厄介なので素直に分けて考えます。
また、0°の線を挟んで反対側にPと点がある場合は、先に処理をしておくと楽になりそうです。

p進んだ時に描く円周上の点をPとします(最初は(50,100))。

Pと点が同じ側であれば、余弦定理を使うことで簡単にコサインが算出されるため、その大小を比較すれば良さそうです。


\displaystyle cosA = \frac{b^{2} + c^{2} - a^{2}}{2bc}

処理と例外

まず、中心が(50, 50)だと面倒なので、それぞれ-50をして中心が(0,0)になるようにします。
次に、中心からの距離が50より大きければ必ず円の外で白なので、これは先に処理します。

また、後の処理を簡単にするため、一色に定まったり判定が微妙になりそうな線上のケースを除外します。
誤差はある程度許容されるはずですが、怪しいところは削っておきます。

  • p==0の場合) 必ず白
  • p==100の場合) (距離の判定は事前にしているので)必ず黒
  • x==0 && y>=0の場合) (p!=0なので)必ず黒
  • x==0 && y<=0の場合) (距離の判定は事前にしているので)p >= 50かどうかでどちらかに決まる

さらに、反対側にある場合を処理します。

  • x>=0 && p>=50の場合) (距離の判定は事前にしているので)必ず黒
  • x<=0 && p<=50の場合) 必ず白

ここまでやると、あとは0°の直線を挟んで同じ側にある場合のみ処理すればよいです。

これはPと点のそれぞれでコサインの値を算出し、p<=50ならPの方が小さければ黒(先に行っている)、p>=50ならその逆になります。

コード

bool sovle() {
    int p, _x, _y;
    cin >> p >> _x >> _y;

    int x = _x - 50;
    int y = _y - 50;

    int dist = (x*x + y*y);
    if(dist > 50*50)
        return false;

    if(p == 0)
        return false;
    if(p == 100)
        return true;

    if(x == 0 && y >= 0)
        return true;
    if(x == 0 && y <= 0)
        return p >= 50;

    if(x >= 0 && p >= 50)
        return true;
    if(x <= 0 && p <= 50)
        return false;

    int dy = abs(y-50);
    int a2 = (x*x) + (dy*dy);
    double cosA = (double)(50*50 + dist - a2) / (2.0*50*sqrt(dist));

    double degP = 360.0 * p / 100;
    double cosP = cos ( degP * M_PI / 180.0 );

    if(p <= 50)
        return cosP <= cosA;
    else
        return cosA <= cosP;
}

int main() {
    int T;
    cin >> T;
    rep(__t, T) {
        cout << "Case #" << __t + 1 << ": ";
        if(sovle())
            cout << "black" << endl;
        else
            cout << "white" << endl;
    }

    return 0;
}

感想

どこまで例外処理をしたらいいかがイマイチわからなくて、考え漏れがありそうななんだか厄介な問題でした。
コーナーケースがどっちになるか分かりにくくて辛いです。

「How Google Works」 感想

感想

こちらも話題になっていたので読みました。

How Google Works (ハウ・グーグル・ワークス)  ―私たちの働き方とマネジメント

How Google Works (ハウ・グーグル・ワークス) ―私たちの働き方とマネジメント

総評

+2: 超オススメ!

「Team Geek」をチームビルディングの本とするなら、こちらは経営者のための組織(会社)ビルディングの本と言えるかもしれません。
イノベーション」と付けられている章は最後の1つだけですが、本全体で「いかにイノベーションを起こすか」ということについて触れられているかと思います。

こう書くと対象読者がかなり限定されそうですが、単純に読み物として面白いのでオススメです。
特にエンジニアだと面白いと感じるのではないでしょうか。

細々とした感想

スマート・クリエイティブ

「スマート・クリエイティブ」という胡散臭い単語が頻出しますが、読んでいくと確かに適切な単語だと感じました。
頭に思い浮かぶ「優秀だと思った人」には、この単語がバッチリ当てはまります。
なんて便利な言葉。

イノベーションを起こすには

イノベーションという言葉が広く使われるようになり、様々な会社、様々なチームで取り組みが行われてきたかと思います。
中にはイノベーション部隊的なものがいる会社もあるとか。
本書では、「原始スープを用意して発生を待つ」という手法に基づいています。
要は、適切な環境(人、文化、場所、システム...)を用意すれば、自ずと発生するものだとしています。
勿論容易なことでは無いですが、結局は最も効率の良い方法に思います。

技術的アイデア

技術的アイデアにより圧倒的に使いやすかったりコストが下がったりすると、マーケティングに苦労せずとも勝手に広まっていくくらい強い商品になる、と述べられています。
いわゆる「イノベーティブな」製品です(よく「フォードの速い馬」が例えとして出てくるやつです)。
そうそう生まれないそんな製品ですが、現代では特に組み合わせによって生まれる、とあります。
多様性の確保が、いい製品を生み出す観点でも重要だという1つの例と言えるでしょう。

まとめ

社内の話や回想、有名人がちょいちょい出てきたりと、読み物としても面白いです。
特にビジネスに興味がなくても、一読することをおすすめします。