183.1

250

テニスのポイント取得者がサーバかレシーバで与えられるので、最初のセットのスコアを答えよという問題。

適当にサーバを交代させつつ計算すればおしまい。

675

N点が与えられるのでそれを内包する最小の円の半径を求めよという問題。

N点のうちの任意の3点について内包する最小の円が、他のすべての点を内包すればそれを答えれば良い。外接円の中心を適当な精度で計算して、内包判定を適当な精度でやる。外接円の中心は直線の交点を求めるライブラリがあれば求まる。(直接求めることも可能だろうけれど。)

取り敢えず直線の交点を求めるクラスをライブラリに追加。いつかちゃんと整理する。ソース汚いし、精度がしっかりしてないし。分数クラスと併合して使うのがいいのかも知れない。

900

文字列が与えられるので、180度回転させた時に同じ文字列になるようなものを作る。ある文字を別の文字にするにはアルファベット間の距離だけコストが必要で、Aの前とZの後に空文字があるとみなす。(これを利用して文字を消すことができる。)最小コストの文字列のうち、最長のものでアルファベット順で最初のものを答えよという問題。

両脇から順に処理していけばそれでおしまい。処理のパターンは3通りで、頭の文字を消す、後ろの文字を消す、文字を消さないで残っている文字の両端を回転後にマッチする最小コストのものに変える。処理が残っている文字列と、その時点でのコストで枝をかれば、速度的には十分らしい。