第4問

n×n の町の家を (i,j) で番号付けし、(1,1) を左上とする。時刻0に (1,c) が燃え、c≤n/2 とする。各単位時間に消防士はまだ燃えていない家を1軒守り、その後、区間開始時に燃えていた各家から、守られていない隣接家へ火が広がる。守った家は常に守られる。救える家の最大数を求めよ。隣接とは、一方の座標だけが1異なることをいう。

ステップ 6/6: 構成と上界を一致させる

前のステップ次のステップ

\left[n^2-\frac{n(n-1)}2-c(n-c+1)\right]+\frac{n(n-1)}2=n^2+c^2-nc-c

詳しい解説

対角線戦略は n−1 より上のレベルの全家を救い、帰納法は低いレベルで可能な最大値を与える。2つの寄与を足すと n の平方+c の平方−nc−c となるので、これが最大値である。