第21回日本情報オリンピック　二次予選

2022年2月5日
情報オリンピック日本委員会

解説

解説担当：星井智仁

以下，JOI 国の南端，東端にも境界線を引くものとして考える．

西から 1 本目の南北方向と並行な境界線を西から i マス目の東側に引き，北から 1 本目の東西方向と並行な境界線を北から j マス目の南側に引くことを考える．すると，残りの境界線の引き方は一意に定まる，もしくは達成不可能である．

従って，各 (i,j) の組について (i,j) = (H,W) の場合を除いて，達成可能かを判定すれば良い．

(i,j) の組が HW - 1 通り，各判定は二次元累積和などを用いれば O(HW) で可能であるため，計算量 O(H²W²) でこの問題を解くことができる．