AtCoder Grand Contest 016 C: +/- Rectangle
H行W列の整数値のテーブルで、h行w列の部分区画の和はすべて負、かつテーブル全部の要素の和が正であるようなテーブルは存在するか？するなら具体例を示せ。
具体的な構成を色々試すと、右下の角1マスだけ負、それ以外は正であるようなテーブルを作ることで作れそうである。この時、hがHの約数、かつwがWの約数であると、テーブルをすべて部分区画でダブりなく敷き詰めることができるため、絶対に全区画の和は負になってしまう。それ以外の場合で具体的に構成してみる。
ある数Vを仮定して、右下の角が -V*(w*h - 1) - 1, それ以外のマスがVであるようなh x wの部分区画を考えると、この範囲での合計は-1であり、負になる。これを横方向にw+1, w+2, と伸ばしていった時、範囲内の合計が最も小さいものはw+1のときであり、具体的にはV*h -1になる。一番右上からh x wの区画が合計N個あった時、上のようなとり方をするとその合計値は-Nとなる。これがV*h - 1の値より絶対値で小さければ、全体の合計値は必ず正となる。ここではWもHも500以下であるため、例えばV=1000とすることで目的のテーブルが構成できる。O(WH)。
この手の発想力が求められる問題は結構苦手かもしれない。
