第4問

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

ステップ 2/6: 戦略で救われる家を数える

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

2[(n-1)+(n-2)+\cdots+(n-c)]+(n-2c)(n-c)=n^2+c^2-nc-c

詳しい解説

列 c からの距離が 0,1,...,c−1 の各対称な2列では、戦略は n−1,n−2,...,n−c 軒を救う。残り n−2c 列では各 n−c 軒を救う。合計は n の平方+c の平方−nc−c となる。