237.1

250

高々三つの矩形のいずれかに含まれる領域の面積を求めよ、という問題。

出てくる座標が各軸6個なので、36個の領域に分けて含まれるかどうか計算するだけ。三つなので、共通の領域についてカウント回数から帳尻を合わせることも可能だけれど、面倒さはさほど変わらない気がする。

600

矩形を同じ面積のN個の矩形に切ることを考える。N-1回だけ任意の矩形に対して二つに切るような切り方のみ許される。切った後にできるN個の矩形の中で一番縦横比が大きいものの最小値を答えよ、という問題。

Nは高々10なので、全通り探索すればおしまい。長辺と短辺が与えられると、その時の分割個数が分かり、一番縦横比が大きいものの最小値をメモしておけば良い。探索は、A対N-Aに切るというのを任意のAについて、長辺と短辺両方について試すだけ。doubleでやるとうまくいかない可能性がありそうなので、分数クラスを作成してやったところ、問題なく終了した。

900

入口と出口のある部屋に、入口から入射した光が出口から出るように鏡を配置するとき、必要な最小個数を求めよ、という問題。

光の現在位置と向きについてBFS(鏡を置く数でダイクストラ)するだけ。(最初から置かれている鏡を使って遠回りする方が、鏡を置くよりも得するケースがあるので、コストが同じものが先に探索されるようにする。)

サンプルがかなりのケースを網羅しているので、それに従って実装すれば良い。