Facebook Hacker Cup 2017 Qualification Round 参加日記

○○×で予選通過。R1は時間的に参加できるかどうか微妙だ。

Progress Pie
進捗パイチャートと点Xがあたえられたとき、Xがチャートの色付き部分に入っているかどうかを判定する。
点の位置とチャートの進捗p(%)を0%からの角度に変換して求めた。

public static bool GetAns(int p, int x, int y)
{
    x -= 50;
    y -= 50;

    // 特殊なケース
    if (x == 0 && y == 0) return p > 0;
    if (p == 0) return false;

    // 中心から遠すぎる
    if (x * x + y * y > 2500) return false;

    var theta = Math.PI * 2 * (p / 100.0);

    // 垂直線(0%線)と中心-点Xの角度を求め、象限ごとに処理する
    var pt = new Pt(x, y);
    var theta_pt = Math.Asin(pt.Cross(_zero) / (pt.Norm() * _zero.Norm()));
    if (x < 0 && y < 0) //3rd
    {
        theta_pt = Math.PI - theta_pt;
    }
    else if (x < 0) //4th
    {
        theta_pt = Math.PI * 2 + theta_pt;
    }
    else if (y < 0) //2nd
    {
        theta_pt = Math.PI - theta_pt;
    }

    return theta_pt <= theta;
}

Lazy Loading
重さの異なるN個の荷物を、なるべく多くの回数で運ぶ。ただし一回50ポンド以上は運ばなければならない。また、まとめて運んでいる荷物は、その中で一番重い荷物x個数でトータルの重さと嘘をつくことができる。
残っている荷物で最も重いものを1つと、軽いほうから50ポンドと虚偽できるまで運ぶのを繰り返せばよい。

public static int GetAns(List<int> w)
{
    var ret = 0;

    while (w.Count() > 0)
    {
        w.Sort();
        if (w.Count() * w[w.Count() - 1] < 50) break;
        w = w.Skip((int)Math.Ceiling((double)50 / (double)w[w.Count() - 1]) - 1).ToList();
        w.Remove(w.Last());
        ret++;
    }

    return ret;
}

Fighting the Zombie
部分的には、Y面のサイコロをN回振ったとき、その合計がある数N以上になる確率を求める問題になる。
dp[i, j]をi回振って合計がjになる確率と定義すれば、
dp[i + 1, j + 1] += dp[i, j] / N
dp[i + 1, j + 2] += dp[i, j] / N
...
dp[i + 1, j + N] += dp[i, j] / N
と更新して最終的な確率がすべて求められる。
（実装は省略）