第4問

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

ステップ 1/6: 防御戦略を示す

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

(2,c),(2,c+1),(3,c-1),(3,c+2),\ldots,(c+1,1),(c+1,2c),(c+1,2c+1),\ldots,(c+1,n)

詳しい解説

i=2,...,c+1 について (i,c+2-i),(i,c+i-1) を順に守り、その後 j=2c+1,...,n の (c+1,j) を守る。列挙した家は守る時点でまだ燃えていない。これは公式解答の対角線戦略である。