はまやんはまやんはまやん

hamayanhamayan's blog

Facebook Hacker Cup 2017 Round 2 問題

読解に苦しむ日本人のための記事。
なんでこんなに問題が読みにくいし、長いのか。
解説はこっち
http://hamayanhamayan.hatenablog.jp/entry/2017/01/23/014451

12: Subtle Sabotage

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

N行M列の盤面がある。
左上端がスタートで右下端がゴールとする。
この盤面にK×Kのブロックを重ならないように配置する。
スタートからゴールまでこのブロックを上手く配置することで最短距離がN+M-2より大きくなるようにする。
必要なブロックの最小個数は?

1 <= テストケース数 <= 10^4
1 <= N,M,K <= 8*10^5

22: Big Top

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

N本のポールをx軸に順番に立てることを考える。
i本目のポールはx = X[i]に高さH[i]である。
ポールを立てると(X[i] - H[i],0)と(X[i], H[i])と(X[i] + H[i], 0)の三角形ができる。
i本目までのポールを立てた後の面積をS[i]とするとき、そのS[i]の総和を答えよ。

ポールの座標と高さは以下の式で決定する。

X[i] = ((AX * X[i - 1] + BX) % CX) + 1
H[i] = ((AH * H[i - 1] + BH) % CH) + 1
(X[i]は全てバラバラの数値になることが保証される)

制限は多いので本文参照

29: Fighting all the Zombies

https://www.facebook.com/hackercup/problem/1726375930948061/
1~Nレベルの杖が1つずつあり、それぞれ同じレベルのゾンビを倒せる魔法が1つずつ備わっている。
iレベルの杖ではi-1~i+1レベルのゾンビを倒せる魔法が取得できる。
洞穴には1~Nレベルのゾンビが1匹ずついる。
この洞穴へM回行って、N本の杖を1本ずつ使って全てのゾンビを倒す。
i回目に洞窟に入る前にW[i]レベルの杖にS[i]個のZ[i]レベルのゾンビが倒せる魔法が追加される。
i回目に洞窟でゾンビを倒す時の杖と倒されるゾンビの組合せをそれぞれ求め、その総和をmod10^9+7で答えよ。

W[i],S[i],Z[i]の更新式は以下の通り。

W[i] = ((AW * W[i - 1] + BW) % N) + 1
D[i] = (AD * D[i - 1] + BD) % 3
Z[i] = max(1, min(N, W[i] + D[i] - 1))
S[i] = ((AS * S[i - 1] + BS) % 10^9) + 1

制限は多いので本文参照

37: Rain Over New York