Territory(縄張り) - joi2009-day3 解説

筆者: snuke

犬の散歩の経路から、テリトリーの大きさを求める問題。

入力 05, 06 をビジュアライズしてみると面白い。

説明のため、犬の歩数を M としておく。

O(M^2)解法

シミュレーションをすればよい。

少し具体的に説明すると、ジョイ君通ったところを２次元配列に壁として書き込み、ペイントツールの要領で外側の部分を塗りつぶし、塗られていない場所の数を数えれば良い。

内側と外側が入り組んでいるので、まずは外周だけを摘出して境界をはっきりさせよう。

そのためには下図中央のように、必ず外周になる場所(例えば最も左上の点)から右手法の要領で壁を辿っていけばよい。

5,6の部分のように、同じ線を二回辿ることもあることに注意する。(表と裏を一回ずつなぞると考えると良い。)

外周さえ摘出してしまえば、後は各行について面積を求めていけば良い。

上図のように、ある行の縦方向の壁を取り出してみると

外 | 内 | 外 | 内 | 外 ( ‘|’ は壁を表している)

のように外側の部分と内側の部分が交互になるように仕切られていることが分かる。

３つ目の図の太線で表された部分は２つの壁が幅 0 でとなり合っていることに注意してほしい。

実装する時には、縦向きの壁のみを y 座標 → x 座標の順でソートしておき、「偶数番目の壁の x 座標 – 奇数番目の壁の x 座標」を足し合わせていくと良い。

あと注意しなければいけないのは、外周部を摘出するときに「スタート地点に戻ってきたら終了」という周回判定をすると、上図３つ目の例などで誤った判定をしてしまうという点だろう。

「地点だけではなく、向きも考慮する」や「同じ辺を使ったら終了( A→B と B←A は区別する)」などの判定法にしなければならない。

この問題は、IOIクロアチア大会の「洪水(FLOOD)」という問題に類似している。

この問題のようにIOIの過去問に似た問題が出題されることはしばしばあるので、JOIの対策としてIOIの過去問を解いておくことは有効であると思われる。