問題 Editorial 問題 飲料メーカーがキャンペーン中。 ジュースのボトル1つと引き換えに、nつの異なるコードのうちランダムな1つが等確率で得られる。 kつの異なるコードを得たい。 それが達成されるのに必要なボトルの数の期待値を求めよ 1 ≦ k ≦ n ≦ 10^18…

問題 Editorial 問題 (問題の肝の部分のみ) width*heightの長方形の中にx*yの長方形が回転してでも入るかどうかを判定せよ 全ての数値は整数, [1,1000] 解答 回転後の幅と高さは(x cosθ + y sinθ, x sinθ + y cosθ)。 それを適当にいろんな感じで二分探索し…

問題 Editorial 問題 平面上に一本の道がある。これは終点が次の始点となる有向線分(roadX,roadY)をつなげた形で、交差・接触はしない。 この道の始点から終点までを最小時間で移動したい。 道にそって走る時は単位距離に対して単位時間かかる。ただし道の向…

問題 Editorial 問題 ある性質をもって走る犬がいる。 木にぶつかるまでの間、点(0, 0)を中心とした円周上を時計回りに走る 木にぶつかった場合、上記の動きができるようになる位置まで、木にそって反時計回りに走る 犬が点(startx, starty)から走り始める時…