Google code jam 2018 Round 1C 2018
Updated:
Google code jam 2018 Round 1C 2018
Solutions
A Whole New Word
結論から言うとこれは DFS を途中で打ち切る問題である。制約条件がポイントである。
仮に全ての word を列挙できたとすると非常に簡単な問題である。しかし実際は最大 $26^{10}$ 程度の word を列挙できない。そこで重要なのが制約である。 $N \leq 2000$ であるから、 $N + 1$ 個の word を列挙できればその中に必ず制約を充たすものがあり、この程度なら愚直に DFS で構成できる。構成できなかったら答えは - であり、構成できたら直ちに DFS を打ち切って出力する。 GCJ はテストケースごとにプログラムを終了できないから実装が少し複雑になる。
Lollipop Shop
乱択(？)とリアクティブ形式の融合問題。
顧客の好きな味も予めわからず、味の市場調査データも予めわからないので、有効な戦略は次のものにほとんど限られるだろう。すなわち、顧客から好きな味のリストを受け取ったら、売れ残っていて、かつその顧客が好きな味なもののうち、過去の顧客の好きな味リストのうち最も不人気だったものを売ると。これできちんと最高数の 9 割捌けるというのだからむしろ不思議である。少し工夫するだけで売り上げって改善するのかなーと思った。
Ant Stack
次の ABC が始まるまで休憩したかったので Small だけ解いた。
この問題はどうやらアリが積み重なるらしいので、条件を充たす積み重なったアリたちを「アリタワー」と呼ぶことにする。
Small の解法
普通に DP すればよろしい。
$DP[i] =$ 合計の重さ $i$ で条件を充たすアリタワーを構成するアリの数の最大値
として、 $i$ の順番に $j$ が大きい方 ( $0 \leq j \leq 6 W_i$ )から順に $DP[j + W[i]] \gets \max(DP[j + W[i]], DP[j] + 1)$ で更新していく。アリは自重の $6$ 倍まで自分の上の小アリタワーの重さを耐えることができるという。 $W_i \leq 1000$ ゆえに、自重も考慮しても int DP[7010]; で足りることに注意。これを $100$ 回回す程度で済むのだから、十分間に合う。
要するにこの問題は変則ナップザック問題のようなもので、普通に weakly NP-hard なので動的計画法で捌けるというわけである。ただし Large を見る限り実際は P なのだろう。
Large の解法
Analysis を読んだ。全然難しくなかった。
$DP[i] = i$ 匹で構成可能なアリタワーの最小の重さ
とする。そもそもアリタワーを自由に構成していいよと言われたときにアリはせいぜい 200 匹までなので、 index は $K = 200$ まであれば十分足りる。あとは遷移をする。 $i = 0, \dots, N-1$ に対し、 $j = 199, \dots, 1$ に対し、 $DP[j-1] \leq 6W_i$ ならば $DP[j] \gets \min(DP[j], DP[j-1] + W_i)$ とする。 $O(NK)$ である。遷移がかなり単純なので $N \leq 10^5$ でも十分間に合う。
ポイント
「DP は同じ状態を区別しない」という定跡からこの問題を振り返ると、上に積み重なったアリの個数だけ区別すればあとは合計の重さだけ管理すればその他の要素は無視できる、ということになる。これに気づけばどちらかの解法は取れる。
その中でも、後者を取るための定跡としては、 DP において、重さは index に持つより値に持つべきである。
Others
もしかして通過したかな。その場合、人生で初めて GCJ Round 1 通過したことになる。 ABC が始まるまで休憩します。
Large の judge も終わり、順位が確定したようだ。私は 461 位で通過したようだ。やったー！
通過していても Round 2 は参加できません。深夜なので。ドクターストップがかかっているので無理です。