Facebook Hacker Cup 2017 (Round1) - 日々ｄｒｄｒする人のメモ

1/15の3時から1/16の3時まで行われていたFHCのRound1に参加した。
とりあえず90 pointsとれたので通過。

10 points: Pie Progress

毎日異なる ${M}$ 個のパイを売る店がある。そして、同日に買ったパイの数だけコストがかかる( ${p}$ pies買えば ${p^2}$ かかる)。その中で、 ${N}$ 日間毎日パイを食べるためのコストを最小にするという問題。

いろいろ考えて、Segment木で殴れば良さそうという結論になって殴ったら死んだ。
(出力結果に0があってあっ...(察し)という感じになってた)

35 points必要だったので、この問題を落とすとやばいかも、みたいな感じで他3問を解くことにした。

25 points: Fighting the Zombies

specialist spell-castersがいて、二次元平面上の任意の実数の半径 ${r}$ 内(境界含む)のゾンビを移動できるspellと一辺 ${R}$ の正方形の内側(境界含む)のゾンビを撃退できるspellを使える。これらのspellを一回使って撃退できるゾンビを最大化する問題。

最初は愚直に3点から円を求めて計算しようと思ったけど、精度含めて計算面倒くさそうと思っていろいろ考察してた。2,3時間くらいで解けた。

円の半径や座標は任意の実数という点を踏まえ考察していくと、一辺 ${R}$ の２つの正方形で包含できるゾンビの数を最大化する問題として考えられることに気がついた。
例えば、２つの正方形が重なっていない場合は、片方の正方形を包含して、もう片方の正方形が外側にあるような円が存在する。また、２つの正方形が重なっている場合は、円が２つの正方形の辺の交点を通るように考えれば、正方形上のゾンビを全て正方形上に移動することができる。

二次元区間 ${[X_i, X_i + R] \times [Y_j, Y_j + R] \hspace{5mm} (1 \le i, j \le N)}$ が包含するゾンビの座標の集合をsetで前もって計算しておけば、 ${O(N^4)}$ で計算できる。

25 points: Manic Moving

${N}$ の街、 ${M}$ の道路がある地域で、 ${K}$ 個の物をある場所からある場所まで( ${i}$ 番目の物は ${S_i}$ から ${D_i}$ まで)運ぶという問題。制約として、 ${K}$ 個の物を順番に届けること、一度に持てる物は２個まで( ${i}$ 番目の物と ${(i+1)}$ 番目のもの)がある。この時、距離のコストの最小を求める問題。

方針がすぐ思いついて解けた。
方針は、Warshall-Floyd法を使って街間の距離を計算しておき、 ${(i+1)}$ 番目の物を持って ${D_i}$ に到着するかしないかでコストが最小となるように計算を進めていく感じ。

${D_i}$ において、 ${(i+1)}$ 番目の物を持たない状態での最小コストを ${P_i}$ 、持った状態での最小コストを ${Q_i \hspace{5mm} (i < N)}$ とする。この時、 ${P_0 = 0, Q_0 = \infty, D_0 = 1}$ である。
また、 ${C(i, j)}$ を ${i}$ と ${j}$ の間の最短コストとする。このとき、
${ \begin{align} P_i & = & \min(P_{i-1} + C(D_{i-1}, S_i) + C(S_i, D_i),\\ & & Q_{i-1} + C(D_{i-1}, D_i)) \\ Q_i & = & \min(P_{i-1} + C(D_{i-1}, S_i) + C(S_i, S_{i+1}) + C(S_{i+1}, D_i),\\ & & Q_{i-1} + C(D_{i-1}, S_{i+1}) + C(S_{i+1}, D_i)) \end{align} }$
この時の ${P_N}$ が答え。計算量は ${O(N^3 + K)}$ 。

40 points: Beach Unbrellas

ビーチで1mごとに ${M}$ 箇所傘を立てられる場所がある。そこに ${N}$ グループがいて、各々半径 ${R_i}$ mの傘を立てようとしている。傘どうしがかぶらないように立てた時、何通りの立て方があるのかを ${10^9 + 7}$ で割って出力する問題。

この問題は頑張って計算した。計算の仕方でハマって5時間くらいかかった。
この時、 ${(M-1)}$ mの区間からはみ出る傘が存在しない場合、片方はみ出る場合、両方はみ出る場合にわけて計算した。

以下で出てくる ${{}_NP_K}$ は以下のように定義する。
${ {}_NP_K = \left\{ \begin{align} N \cdot (N-1) \cdot \ldots \cdot (N-K+1) & \hspace{5mm} & (N \ge K) \\ 0 & & (otherwise) \end{align} \right. }$

(i) はみ出る傘が存在しない場合

各傘を、 ${(M-1)}$ mの区間にはみ出ないように配置できる場合、被らないように立てられる候補は $(M - 1 - 2 \sum_i R_i + N)$ 箇所ある。これを ${C}$ とする。

この候補に ${N}$ 個の傘を立てる全ての通りを考えればよいので ${{}_CP_N}$ で計算できる。

(ii) 片方はみ出す場合

各傘 ${i}$ について考えていく。ここで、半径 ${R_i}$ のうち ${j}$ はみ出すとする。 ${(1 \le j \le R_i)}$
この時の通り数は、 ${{}_{C+j-1}P_{N-1}}$ で計算できる。対照の場合も考え、全ての場合は以下のように計算できる。
${ \begin{align} 2 \sum_i \sum_{j=1}^{R_i} {}_{C+j-1}P_{N-1} & = & 2 \sum_i {}_{C}P_{N-1} + \ldots + {}_{C+R_i-1}P_{N-1} \\ & = & 2 \sum_i S_1(R_i) \end{align} }$
前もって累積和 $S_1(k) = \sum_{j=1}^{k} {}_{C+j-1}P_{N-1} \hspace{5mm} (1 \le k \le \max_i R_i)$ を計算しておけば ${O(N)}$ で計算できる。

(iii) 両方はみ出す場合

２つの傘 ${i, j}$ について考えていく。ここで、半径 ${R_i}$ のうち ${p}$ 、半径 ${R_j}$ のうち ${q}$ はみ出すとする。 ${(1 \le p, q \le R_i)}$
この時の通り数は、 ${{}_{C+p+q-2}P_{N-2}}$ で計算できる。よって、全ての場合は以下のように計算できる。
${ \begin{align} \sum_i \sum_{j \neq i} \sum_{p=1}^{R_i} \sum_{q=1}^{R_j} {}_{C+p+q-2}P_{N-2} & = & \sum_i \sum_{j \neq i} \sum_{p=1}^{R_i} {}_{C+p-1}P_{N-2} + \ldots + {}_{C+p+R_j-2}P_{N-2} \\ & = & \sum_i \sum_{j \neq i} \sum_{p=1}^{R_i} S_2(p + R_j) - S_2(p) \\ & = & \sum_i \sum_{j \neq i} \sum_{p=1}^{R_i} S_2(p + R_j) - \sum_{p=1}^{R_i} S_2(p) \\ & = & \sum_i \sum_{j \neq i} (S_{S_2}(R_i + R_j) - S_{S_2}(R_j)) - S_{S_2}(R_i) \end{align} }$
前もって累積和 $S_2(k) = \sum_{j=1}^{k} {}_{C+j-2}P_{N-2} \hspace{5mm} (1 \le k \le 2 \max_i R_i)$ を計算し、その累積和 $S_{S_2}(k) = \sum_{j=1}^{k} S_2(k) \hspace{5mm} (1 \le k \le 2 \max_i R_i)$ を計算しておけば ${O(N^2)}$ で計算できる。