Round 3

予想通り落っこち。しかも最下位だった。チャレンジ一つ成功させるのは必須だったので、仕方ないっちゃ仕方ない。

250

木が何本か植えられている状況で、木を矩形のフェンスで囲むことを考える。木を切ることで作れるフェンスの長さと、木の位置が与えらえるので、切る必要のある最小の木の本数を答えよ、という問題。

矩形の4点を出てくる座標から決めて、外側のは無条件に切り取り、内部のはたくさんフェンスが作れるのを必要なだけ切り取る。残った中で最小のものが正解。全部ダメなら一本だけ残す。

一本だけ残すなんて考えてなかった。

500

選挙で、各地域が順番に選挙される。遊説できる地点数が指定されており、途中経過を見た上で遊説するかどうか決定できる。遊説すると得票できる確率が変動する。各地域では指定された票をすべて取るか全く取れないかのいずれか。この状況で過半数を取れる最大の確率を答えよ、という問題。

おとなしくDPしましょう。探索＋枝狩りだと1,2,4,8,...というケースでお亡くなりになるそうで。

1000

何通りかの可能な動きができる石がある。循環しているNマスのうち、印のないところに石を置き、印のないところをたどって移動する。たどったマスは印がつく。最初の位置に戻ったら石を除去する。これを繰り返してNマスすべてに印をつけるのに必要な最小石数を答えよ、という問題。

塗りつぶし可能なパターンを全列挙したら終わらないだろうなぁ、という感じ。実際には移動できる最大の大きさが6なので、近隣6マスずつくらいしか考慮しなければ高速にできるのかも知れない。