D問題
幾何計算。arctanとかPIのC++での使い方をググるのに時間を食う。
E問題
Kのオーダーが大きすぎるので「Kを分配する」考え方ができない。
全体の方針を考えていたら時間が足りなくなったが、「最小値としてXを達成可能か」を判定すれば、Xがある値より大きければ可能、それより小さければ不可能という一方向性が成り立つため、二分探索ができることに思い当たった。
実践で二分探索を発想できたのは初なので大きな成果と思いたい。
残りはXを与えられたときの判定をO(N)で行えばよい。
Fは降順ソート、Aは昇順ソートする。
Y = sum(A)-K から、A[i]の各要素の値を超えない範囲、かつF[i]*A[i]がXを超えない範囲でB[i]に分配していき、Yを0にすることができたら達成可能、できなかったら達成不可能。
これで通った。 あとは時間内にやるだけ。
