tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

JMC2016-2017 問題4

余談: タイトルバーには JMC2015-2016 と書かれています。

明日はJOIの予選だそうで、今日はその模擬予選というのをやっていたようです。皆さん満足いく準備はできましたか?明日の予選では実力を発揮できそうですか?

IOI2012に参加した僕からの一言アドバイスです。

「15:23以前に問題4に何の疑いもなく解答を提出して満点を取った人は反省してください。」

以下、詳細を説明していきます。

問題の概要

二次元フィールドの一部が赤く、残りが白く塗られているので日本国旗を作りたい。塗り替える個数の最小値を求めよ。

以下のようなものが日本国旗に当てはまります。

  • 日本国旗のように真ん中が丸いもの
  • 真っ白
  • イングランドの国旗の周りを白く囲ったもの(!)

想定している定義は、IOI2012のCityの55点解法と同じく、赤いマスが行、列ごとに一つの連結成分になっていることのようです。

当初の問題文にあった定義

連結性がおかしくて正しくない例の図Dまで条件を満たすことになっていました。これは日本語のミスなので気にしないことにします。

Challenge Phase 第1問

  • 国旗に垂直な直線と水平な直線について線対称となっている.
  • 任意の赤のマスから, 他の赤のマスへ, 辺を共有している赤のマスを辿ってたどり着くことが出来る.また, 赤のマスによって囲まれる白のマスは存在しない.
  • 1 ≦ i ≦ H / 2 - 1 を満たす整数 i について, 国旗の i 行目に含まれている赤のマスの個数は, 国旗の i + 1 行目に含まれている赤のマスの個数以下である.
  • 国旗の 1 行目, 1 列目, H 行目, および W 列目に赤のマスが含まれない.

さっき書いた意図に反するケースを見つけてください。見つかりましたか?

答えです。白い文字で書きました。


8 8
WWWWWWWW
WRWWWWRW
WRRWWRRW
WWRRRRWW
WWRRRRWW
WRRWWRRW
WRWWWWRW
WWWWWWWW

要は、アラバマの州旗を白く囲んだものまで条件を満たしてしまうことになりました。これだけなら容易に変なケースは作り放題です。

ということで以下のような修正が加わりました。

Challenge Phase 第2問

  • 国旗に垂直な直線と水平な直線について線対称となっている.
  • 任意の赤のマスから, 他の赤のマスへ, 辺を共有している赤のマスを辿ってたどり着くことが出来る.また, 赤のマスによって囲まれる白のマスは存在しない.
  • 1 ≦ i ≦ H / 2 - 1 を満たす整数 i について, 国旗の i 行目に含まれている赤のマスの個数は, 国旗の i + 1 行目に含まれている赤のマスの個数以下である.
  • 1 ≦ i ≦ W / 2 - 1 を満たす整数 i について, 国旗の i 列目に含まれている赤のマスの個数は, 国旗の i + 1 列目に含まれている赤のマスの個数以下である.
  • 国旗の 1 行目, 1 列目, H 行目, および W 列目に赤のマスが含まれない.

一見、これで正しそうに見えます。それでは運営の意図に反するケースを作ってください。こっちは少し難しいです。

答えです。やっぱり白く書いておきました。


16 14
WWWWWWWWWWWWWW
WWWWRRWWRRWWWW
WWWWRRWWRRWWWW
WWWWRRRRRRWWWW
WRRWWWRRWWWRRW
WWRRWWRRWWRRWW
WWRRWWRRWWRRWW
WWWRRRRRRRRWWW
WWWRRRRRRRRWWW
WWRRWWRRWWRRWW
WWRRWWRRWWRRWW
WRRWWWRRWWWRRW
WWWWRRRRRRWWWW
WWWWRRWWRRWWWW
WWWWRRWWRRWWWW
WWWWWWWWWWWWWW

最終的に

下のような条件になりました。これなら正しいと思います。

  • 国旗に垂直な直線と水平な直線について線対称となっている.
  • 任意の赤のマスから, 他の赤のマスへ, 辺を共有している赤のマスを辿ってたどり着くことが出来る.また, 赤のマスによって囲まれる白のマスは存在しない.
  • 1 ≦ i ≦ H / 2 - 1 を満たす整数 i について, 国旗の i 行目に含まれている赤のマスの個数は, 国旗の i + 1 行目に含まれている赤のマスの個数以下である.
  • 各行について, 赤マスは一つのまとまりとなって配置されている. すなわち, ある行に赤マスがあるのであれば, その行の赤マスがある左端の列を L 列目, 右端の列を R 列目として, L ≦ i ≦ R を満たすすべての i について, i 列目は赤マスとなっている.
  • 国旗の 1 行目, 1 列目, H 行目, および W 列目に赤のマスが含まれない.

まとめ

定義が難しそうな問題はちゃんと定義から変なものが構成できないかどうか証明して確認しよう!