Fences 解説
問題概要
問題概要
問題概要
問題概要
はじめに
• この問題は「幾何」問題です • 幾何問題を解くにあたっては,必要な知識がいくつ かあるので,去年の講義スライドなどを参考にして ください https://www.ioi-jp.org/camp/2017/2017-sp_camp-hide.pdf柵の置かれ方のパターン
本質的にはそんなに多くないので全部場合分けす る うまく回転,反転さ せると,これらのう ちのどれかになる場合分けの例
牧草地の左上の角は無視して, 左下 -> 柵 -> 右上 という感じで結ぶ
場合分けの例
例外的?なパターン
牧草地の囲い方
牧草地を囲う閉じた折れ線
in in
out out
最短経路で考えるべき点
最短経路は折れ線になるが,その途中で折れる点 としては「牧草地の四隅」以外は考えなくてよい