Google Code Jam 2018 Round 1A
作成日：2018.04.14
カテゴリー：競プロ 参戦記録
目次
コンテスト後(結果)
79点(AbC)、ペナルティータイム$1:23:19$の$545$位。
2,3問目でそれぞれ1WA。3問目はただの誤読なのでもったいなかった。
2問目のHiddenでWAになったのは、二分探索の最大値が小さすぎたせいで非常にもったいない。
尤も、round2に進めたので関係はないのだが。
各問題の(軽い)解説
Waffle Choppers(9+16)
問題文
縦方向にだけ切ることを考えると、切った後にできる欠片にあるチョコレートの数はそれぞれ等しくなければならない。
このことから切る位置は、可能であれば多くの場合一意に定まる。
一意に定まらない場合というのは1個もチョコレートがない列がある時だが、このような列はなくても答えに影響しないので実質的に一意であると言える。
横方向についても同じであるから、後は各欠片のチョコレートの数が等しいことを調べれば良い。
計算量はテストケース1つにつき$O(RC)$であるから十分高速である。
Bit Party(11+21)
問題文
求める答えは$0 \leq N_i \leq M_i$、$\sum{N_i} = B$、$N_i > 0$となる$i$の数は$R$以下という条件の下で、$min(max(S_i N_i + P_i))$である。
最大値の最小値を求めるためには二分探索が使えることが多いので、それを使うために答えが$x$になり得るかを判定する問題を考える。
これは各レジが時間$x$で処理できる商品の数$min(M_i,max(0,(x-P_i)/S_i))$のうち、大きいものから$R$個取ったものの和が$B$を超えているかで判定できる。
よって二分探索のための判定問題を$O(C \: log \: C)$で解けるので、元の問題も十分高速に解くことができる。
ここで二分探索の範囲の最大値は$10^{18} + 10^9$以上にしなければならない。
Edgy Baking(14+29)
問題文
1つもクッキーを切らない時の外周の長さの総和$S$は$S = 2\sum{(W_i+H_i)}$である。
またクッキーの切断した長さの総和を$x$とすると、外周の長さの総和は$2x$だけ増加する。
各クッキーにおいて切断できる長さは、条件から長くない方の辺の長さ以上対角線の長さ以下、すなわち$min(W_i,H_i)$以上$\sqrt{W_i^2+H_i^2}$以下である。
求めるのは$P$を超えない外周の長さとしてあり得る最大値である。
これは容量$P-S$の箱に容積$2min(W_i,H_i)$、価値$2 \sqrt{W_i^2+H_i^2}$のものを詰めるナップサック問題に帰着できる。
容積は整数であるから、容積をキーとして持つ計算量$O(N^2 \: max(max(W_i),max(H_i)))$のDPでこのナップサック問題を解くことができる。
元の問題に対する答えは、価値の最大値を$v$として$min(P,S+v)$である。
＜(古い記事) Topcoder Marathon Match 99 最終結果
(新しい記事)＞