- A1. Heidi Learns Hashing (Easy)
- A2. Heidi Learns Hashing (Medium)
- A3. Heidi Learns Hashing (Hard)
- B1. The Doctor Meets Vader (Easy)
- B2. The Doctor Meets Vader (Medium)
- B3. The Doctor Meets Vader (Hard)
- C1. Heidi and the Turing Test (Easy)
- C2. Heidi and the Turing Test (Medium)
- C3. Heidi and the Turing Test (Hard)
- D1. Parallel Universes (Easy)
- D2. Parallel Universes (Hard)
- E1. Daleks’ Invasion (easy)
- E2. Daleks’ Invasion (medium)
- E3. Daleks’ Invasion (hard)
A1. Heidi Learns Hashing (Easy)
$x^2<r$ となる範囲で $x$ を全探索できます．
A2. Heidi Learns Hashing (Medium)
$k$ を固定したときの判定を考えます．$i,i+k,\ldots$ 番目をもとに戻るまで並べたときの文字列を考えたとき，それの総和が偶数というのが条件になります．特に判定は $\gcd(n,k)$ だけに依存するため，約数の場合をすべて調べておけばよいです．
A3. Heidi Learns Hashing (Hard)
多項式 $f$ が与えられるので，素数 $p$ と値 $r$ であって $f(r)\equiv 0\pmod{p}$ となるものを見つけよということです．$p$ を固定したとき，すべての $r$ に対する評価が multipoint evaluation でできます（$r$ を等比数列に並べておけば $O((n+p)\log (n+p))$ 時間です．）．
いろいろランダム生成されていることから，$p$ を固定すると解は確率 $1/e$ 程度で見つかります．よって $O(1)$ 個の $p$ を試せば出てくると期待できます．
これでも良かったかも
B1. The Doctor Meets Vader (Easy)
単純なソート，二分探索，累積和．
B2. The Doctor Meets Vader (Medium)
攻撃可能というペアの最大マッチングを求めれば答を計算できます．
B3. The Doctor Meets Vader (Hard)
各 spaceship の価値を計算しておきます．base の町ごとに適当な二分探索を行えば $O(n^3+(b+sn)\log b)$ 程度の計算量でできます．
あとは何もかもが $s$ 頂点の最小カットで書けます．特に，使用する・しないを 0, 1 で表すと，制約になっている $k$ ペアについて，$(0,1)$ や $(1,0)$ が禁止されますが，これは容量無限大の辺で表せます．
見かけ上頂点数・辺数は $O(s)$ になりますが，このうち $O(k)$ 個を除けば source, sink の片方だけと繋がっているだけなのでフローの計算量は $O(k^2)$ でおさえられています．
C1. Heidi and the Turing Test (Easy)
左辺・下辺上の点があるとしてよいです．すると左下の点を全探索できます．
正方形は極小としてよく，すると右辺または上辺上に点があるため一辺の長さも全探索できます．
C2. Heidi and the Turing Test (Medium)
いわゆる $45$ 度回転で正方形を軸に平行にしておきます．正方形がたくさん与えられて，その交わり枚数の最大値を求める問題です．適当に座圧します（正方形は長方形になります）．
$y$ をインクリメントしながら答を計算することを考えると，区間加算と全体最大値に帰着できます．よって遅延セグメント木で解けます．
C3. Heidi and the Turing Test (Hard)
かなり何度も嘘や誤差で落とされました．ちょっと生成が面倒だったのでさぼろうと思ってたんだけど，結局問題文を読みながらランダム生成を実装して戦略を改善していく必要がありました．
最終的に実装したのは以下の通り．
- 点が円上にあるとは，距離 $[0.88r, 1.12r]$ のところにあることとして定義．
- 候補となる円を $500$ 個作る．単に $3$ 点を乱択して外接円をとる．ただし面積が小さい三角形はノイズの影響が大きそうなので避けた．点の $N$ 個以上が円上にあれば採用．
- 適当な方法で $4$ つとる．最初の円と $2$ 番目の円はループして，$3$ 番目と $4$ 番目は，まだ被覆できていない点を最も多く含むものを貪欲に，とした（bitset 使用）．$4$ 枚で 85% 以上の点を被覆できれいれば合格．
- $4$ つの円をもとに，点を分類．複数の円上にあるやつは無視．
- 各円に対して精度を上げる．$3$ 点の外心を計算することをたくさん繰り返して平均をとる．
- $4$ つの円で 95% の点を被覆できていたら答えを出力．そうでなければすべてをやりなおす．
結局，最後の項目を入れたら AC になったので，それ以外は全然利いていない可能性もあります．
例えば「85% を被覆していたら答えを出力」だと違う円を拾ってしまって AC にならなかったりするみたいです．
解説は k-means 的な方法のようですが，それも少し工夫が要るようです．
D1. Parallel Universes (Easy)
長さと自分の位置だけを持てば高速にシミュレーションできます．
D2. Parallel Universes (Hard)
左右にある星の個数を $a,b$ として，その状態からスタートしたときの最終状態の長さの期待値を ANS[a][b] とします．$O(M^2)$ 個の ANS[a][b] に対する連立方程式ができて，自明解法の計算量は $O(M^6)$ です．
しかし，$i\geq 2$ とするとき，ANS テーブルの $i$ 行目は $i-1$ 行目までの線形結合で書けます．これを得るには，状態 $(i-1,b)$ からの遷移を考えればよいです．
すると，何もかもを ANS[1][b] の線形結合で表せて，解くべき連立方程式の大きさを $O(M)$ にすることができます．これで $O(M^3)$ 時間で解くことができます．
連立方程式の det が $0$ にならないことは示していませんが，$250$ 通り全探索することで（成り立つならば）証明できるはず．
E1. Daleks’ Invasion (easy)
二分探索して，素直に MST を計算します．毎回重みでソートしても TL におさまりました．
E2. Daleks’ Invasion (medium)
MST を作ったあと，使われなかった辺について，MST と置き換えられる辺，つまり MST におけるパス上の辺における最大重みのものを求めます．
E3. Daleks’ Invasion (hard)
MST 上の辺についての答を求めます．他の辺と置き換えられてしまうパターンを考えます．MST 外の辺について，パス上に chmin する形でできます．
