ABC 170 の感想
D - Not Divisible
素因数分解系は、ρ法で殴る癖がついてしまいました。
計算量は \( O(NA^{\frac{1}{4}}) \) です。
ρ法を使った \( O(n^{\frac{1}{4}}) \) の素因数分解
E - Smart Infants
heapq （priority queue） を20万本（各幼稚園用）＋1本（全体用）持ちます。
方針：
- 各幼稚園について、その園の幼児のレートを heapq で管理します
- 転園があると、元の園から削除し、新しい園に追加します。削除は普通の heapq ではできないので遅延削除します
- 全体の heapq も更新（古いデータは削除、新しいデータは追加）します。ここでも削除は遅延削除します。
「遅延削除」は、各幼稚園のものは、幼児ごとのデータを管理しておいて、一番上のデータが幼児ごとのデータと整合的でなければ削除するのを繰り返します。
F - Pond Skater
方針：
- 変則 BFS
- 上下・左右のどちらに動けるかを指定して queue に入れる
- 具体的には、横に動くときは、1 ～ K-1 マス目までは縦限定、Kマス目は両方動けるように指定すればよい。
これで \( O(HW) \) で間に合います・・・
と思ったら計算量違う気がしてきました。嘘解法っぽいですね。。
