第2問

2012×2012の正方形格子の各マスに、0以上1以下の実数を入れる。格子を、格子の辺に平行な線で二つの空でない長方形のマス集合に分割する。どの分割でも少なくとも一方の長方形内の数の和が1以下であるとする。全ての数の和の最大値を求めよ。

ステップ 2/5: 行区間和を定義する

R(x,y)=\sum_{i=x}^{y}\sum_j r_{i,j},\quad R(x,y)=0\text{ if }x>y.

詳しい解説

R(x,y)をx行からy行までの和とする。n=2012とし、R(1,a-1)≤1となる最大のaを選び、続いてR(c+1,n)≤1となる最小のcを選ぶ。