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

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

解説

すべての交差点に住んでるの近くに住んでいる住民が1人の場合，Hが奇数の時は北から(H+1)/2番目の道路，Hが偶数の時は北からH/2番目か(H+2)/2番目の道路を東西方向の幹線道路とし，Wが奇数の時は西から(W+1)/2番目の道路，Wが偶数の時は西からW/2番目か(W+2)/2番目の道路を南北方向の幹線道路とすると，10点を得ることができる．

これ以外の場合について考える．

東西方向の幹線道路と南北方向の幹線道路の選び方は，合わせてH×W通りある．
また，幹線道路を北からx(1≦x≦H)番目の道路と西からy(1≦y≦W)番目の道路に決めたとき，交差点(i,j)(1≦i≦H, 1≦j≦W)から幹線道路への距離は|i-x|と|j-y|の小さいほうとなる． H×W通りの幹線道路の組み合わせを試し，各組合せごとに距離の総和を計算すると，O((H W)^2)となり，満点を得ることができる．