MathLabs

第4問

n×n の町の家を (i,j) で番号付けし、(1,1) を左上とする。時刻0に (1,c) が燃え、c≤n/2 とする。各単位時間に消防士はまだ燃えていない家を1軒守り、その後、区間開始時に燃えていた各家から、守られていない隣接家へ火が広がる。守った家は常に守られる。救える家の最大数を求めよ。隣接とは、一方の座標だけが1異なることをいう。
ステップ 5/6: 上界を数える
∑t=1n−1s(t)≤∑t=1n−1t,∣{ℓ>n−1}∣=n2−n(n−1)2−c(n−c+1)\sum_{t=1}^{n-1}s(t)\le\sum_{t=1}^{n-1}t,\quad |\{\ell>n-1\}|=n^2-\frac{n(n-1)}2-c(n-c+1)
詳しい解説

したがって n−1 以下のレベルで救える家は 1 から n−1 までの和以下である。これらのレベルの格子点を直接数えると n(n−1)/2+c(n−c+1) 軒で、残りのレベルには n の平方からこれを引いた軒数がある。