第16回日本情報オリンピック　予選３

2016年12月11日
情報オリンピック日本委員会

解説

休憩スペースの置き方として考えられるものすべてに対し，休憩スペースが機材の置かれたマスと重ならないかどうか調べ，そのような置き方が何通りかあるかを出力すれば良い．

休憩スペースの置き方は，縦向きと横向きが考えられるため，それぞれ別に試す必要がある． また，休憩スペースがマス目からはみだしてはいけないことにも注意が必要である．

休憩スペースの置き方は O(NM) 通りあり，それぞれに対して休憩スペースの D マスすべてが機材の置かれたマスと重ならないかどうか調べる必要があるため，計算量は O(NMD) となる．

なお，各マスについて，「そのマスから上方向および左方向に，選手が競技を行わないマスがそれぞれ何マス連続しているか」を計算することで，計算量 O(NM) で正解を得ることも可能である．