- A1. Death Stars (easy)
- A2. Death Stars (medium)
- A3. Death Stars (hard)
- B1. Maximum Control (easy)
- B2. Maximum Control (medium)
- C1. Encryption (easy)
- C2. Encryption (medium)
- C3. Encryption (hard)
- D1. Hyperspace Jump (easy)
- D2. Hyperspace Jump (hard)
- E1. Guard Duty (easy)
- E2. Guard Duty (medium)
- E3. Guard Duty (hard)
- F1. Lightsabers (easy)
- F2. Lightsabers (medium)
- F3. Lightsabers (hard)
A1. Death Stars (easy)
回転や対象移動などをして一致を確認します．$8$ 通りやることになります．
A2. Death Stars (medium)
Rolling Hash によりすべての $M\times M$ 領域をハッシュすればよいです．
A3. Death Stars (hard)
点群を $A, B$ とします．
基本方針として，$\mathrm{dist}(A[i_1],A[i_2])\approx \mathrm{dist}(B[j_1],B[j_2])$ となる $4$ つ組を見つけて，$(i_1,j_1), (i_2,j_2)$ を含む解を作れるか調べる．ということをしました．
このような $(i_1,i_2,j_1,j_2)$ はお誕生日攻撃の要領で $O(N)$ 時間程度で見つかることは分かります．このような $4$ つ組を固定し，それらが重なるようにして KD tree で最近傍探索という要領です．
$N=1000$ 程度ならばこれでよいのですが，$N$ が最大の場合には，座標範囲と小数第 $2$ 位までに丸められてしまっている関係から，解にならない $4$ つ組が大量に出てきてしまいます．そこで，よりうまく $(i_1,i_2,j_1,j_2)$ をとる必要があります．
点群 $A$ の凸包をとります．これは制約の範囲でランダム生成すると，$20$ から $30$ 頂点程度になることが実験的に分かります．このうち $2/3$ 程度はもとの点群から来ているはずです．逆に，もとの点群の凸包の点が十分な確率で点群 $A$ の凸包に現れることが分かります．
そこで $(i_1,i_2,j_1,j_2)$ をそれぞれの点群の凸包を候補として調べることで AC が得られました．（AC が得られる確率などは検証していません．）
B1. Maximum Control (easy)
次数 $1$ の点を数えるだけです．
B2. Maximum Control (medium)
$K\geq 2$ のとき中心を含むことは証明できます．中心を根付き木として，各頂点からは最も深い方向への辺から順に優先的に使うことも証明できます．よって適当な貪欲法により最適解が作られます．
別の問題で詳細に解説したので詳しくはそちらをご覧ください：https://maspypy.com/zeptolab-code-rush-2015
C1. Encryption (easy)
単に全部の場合を計算できます．
C2. Encryption (medium)
C3. Encryption (hard)
C2 が minimize, C3 が maximize ですがほぼ同じ問題です．
$\mathrm{newdp}[R] \leftarrow \mathrm{dp}[L] + \mathrm{value}[L,R)$ というタイプの dp 遷移を $K$ 回繰り返します．
$S$ を累積和 $\bmod{p}$ とすれば，$S[L]\leq S[R]$ ならば $\dp[L]+S[R]-S[L]$，そうでなければ $\dp[L]+S[R]-S[L]+p$ というような値が欲しいことになります．
$a=S[L]$ のときの $\dp[L]-S[L]$ の最大値（最小値）を持つようにすればよいです．以下の提出ではセグメント木を使っていますが単に長さ $p$ の配列でもよいという制約だと思います．
- C2: https://codeforces.com/contest/958/submission/325943876
- C3: https://codeforces.com/contest/958/submission/239395830
D1. Hyperspace Jump (easy)
構文解析したあと既約分数になおします．
D2. Hyperspace Jump (hard)
適当な mod をとって解空間をハッシュします．すべての小行列式の det よりも大きな mod をとれば決定的なはず．
E1. Guard Duty (easy)
$R=B$ が必要ですが，実は十分にもなります．E3 を参照してください．
E2. Guard Duty (medium)
有名問題です．
次の問題の解説を参照するとよいです：https://atcoder.jp/contests/joisc2018/tasks/joisc2018_j
E3. Guard Duty (hard)
凸包をとって，凸包上の連続する $2$ 点が結べるならば結んで削除します．
凸包が単色のときが問題です．この場合，$x$ についてソートすると「赤 … 赤」のようになっていますが，これをどこかで二分して，それぞれで赤青が同数であるようにできます．これで再帰的に解きます．最悪ケースがあるかはわかりませんが上界としては $O(n^2\log n)$ 時間かけています．
F1. Lightsabers (easy)
区間を全探索してチェックすればよいです．
F2. Lightsabers (medium)
尺取法をつかって，$L$ に対して必要数あるような最小の $R$ を求めます．
F3. Lightsabers (hard)
$(1+x+\cdots+x^n)$ の形の多項式の総積です．
