JMO 2019
問題 2

$0,1,\dots,n-1$ が $n$ 個ずつ書き込むとしてよい．$k$ 行目に書き込まれた $0$ 以外の数の個数を $a_k$ としたとき，その行による点数の寄与は高々 $(n-a_k)+\lfloor a_k/2\rfloor$ であるので，全ての行による点数への寄与 $L$ は

$$L\leq \sum_{k=1}^{n}\left((n-a_k)+\lfloor a_k/2\rfloor\right)\leq \sum_{k=1}^n\left(n-\dfrac{a_k}{2}\right)=\dfrac{n^2+n}{2}$$

と評価できる．全ての列による点数への寄与 $R$ についても同様に $R\leq \dfrac{n^2+n}{2}$ と抑えられるので，点数の総和は高々 $n^2+n$ である．また，$i$ を $n$ 個斜めに書き込んでいくことを $i=0,1,n-1,2,n-2,\dots$ の順で行えば点数 $n^2+n$ が実現できるので，これが求める最大値である．