第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)

4庭園 2 (Garden 2)

解説作成者：米田優峻

小課題 1 (累計 4 点)
N = 3 の場合，花の植え方としては以下の 10 通りがあり，そのうち (1)〜(9) までの 9 通りはどんな入力の場合でも選択することができます*1 。しかし，(10) は区画 (1, 2)，区画 (2, 1)，区画 (2, 3)，区画 (3, 2) の色がすべて同じでなければ選択できません。
したがって，A1,2 = A2,1 = A2,3 = A3,2 のとき答えは 5 本，そうでないとき答えは 1 本となります。if 文などの条件分岐を使うと簡単に実装することができます。

(1) 大きさ 0(1) 中心 (1, 1)(2) 大きさ 0(1) 中心 (1, 2)(3) 大きさ 0(1) 中心 (1, 3)(4) 大きさ 0(1) 中心 (2, 1)(5) 大きさ 0(1) 中心 (2, 2)(6) 大きさ 0(1) 中心 (2, 3)(7) 大きさ 0(1) 中心 (3, 1)(8) 大きさ 0(1) 中心 (3, 2)(9) 大きさ 0(1) 中心 (3, 3)(10) 大きさ 1(10) 中心 (2, 2)(次ページへ続く)*1 たとえばパターン (1) の場合，色 A1,1 の花を区画 (1, 1) に植えればよいです。

問題 4- 1 / 8第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)

小課題 2 の前にまず，本問題では最大何本の花を植えられるかを出力しなければなりません。しかし，大きさ r が決まってしまえば，植える花の数は 2r2 + 2r + 1 本と自動的に決まります。そのため，最大で大きさいくつにできるかが分かれば，答えも分かります。そのため以降の解説では，大きさの最大値を求めることを考えます。

5本

大きさ1

全く同じ問題最大で何本植えられる？

最大で大きさいくつ？

小課題 2 (累計 17 点)
この小課題は，中心の区画 (x, y) を全探索して，それぞれの区画に対して「達成できる大きさ r の最大値rmax 」を計算することで解けます。
しかし，達成できる大きさの最大値 rmax はどうやって計算すれば良いのでしょうか。例として，庭園の大きさが 5 × 5 であり，中心が区画 (3, 3) の場合を考えてみましょう。以下のようになります。

• |x′ − 3| + |y′ − 3| = 1 を満たす区画 (x′ , y′ ) について，色 A x′ ,y′ が同じでなければ，rmax = 0• |x′ − 3| + |y′ − 3| = 2 を満たす区画 (x′ , y′ ) について，色 A x′ ,y′ が同じでなければ，rmax = 1• そうでなければ，rmax = 2

中心(3, 3)

水色の区画の𝑨𝒙,𝒚 はすべて同じ色か？

緑色の区画の𝑨𝒙,𝒚 はすべて同じ色か？

Yes

No

大きさの最大値は 0

No

大きさの最大値は 1

問題 4- 2 / 8

Yes

大きさの最大値は 2

第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)

中心が区画 (3, 3) ではない場合も，同じような方法で rmax を計算することができます。具体的には，中心が (x, y) のときの |x′ − x| + |y′ − y| の値を 距離 と呼ぶとき，以下のようになります。

• 距離が 1 の区画 (x′ , y′ ) について，色 A x′ ,y′ が同じでなければ，rmax = 0• 距離が 2 の区画 (x′ , y′ ) について，色 A x′ ,y′ が同じでなければ，rmax = 1• 距離が 3 の区画 (x′ , y′ ) について，色 A x′ ,y′ が同じでなければ，rmax = 2• 以下同様これを自然に実装すると rmax を求めるのに計算量 O(N 2 ) を要し，中心のパターン数が O(N 2 ) 通りである
ため，全体の計算量が O(N 4 ) になりますが，N ≤ 50 という制約下では十分高速に動作します。

小課題 3 (累計 34 点)
小課題 2 では，rmax を計算するのに O(N 2 ) を要しました。しかし，この計算を O(N) にしなければ，小課
題 3 の N ≤ 800 という制約下で通すことはできません。一体どうすれば良いのでしょうか。

rmax の値を計算するには，中心からの距離が i である区画の色がすべて同じかどうかを，i = 1, 2, 3, . . . について判定する必要がありました。つまり下図のような区画の色がすべて同じかどうかを，i = 1, 2, 3, . . .
について判定する必要がありました。
ここで中心からの距離が i である区画は最大 O(N) 個存在するため，愚直に実装すると各 i について計算量 O(N)，全体で O(N 2 ) かかります。

(1) i = 2 の例

(2) i = 3 の例

(3) i = 4 の例

(次ページへ続く)問題 4- 3 / 8第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)

しかし，累積和を使うと各 i に対する計算量が O(1) になります。まず，赤/黄/青それぞれについて，A x,yがその色である個数を右上方向に累積和を取ります。赤の場合の例を下図に示します。(たとえば上から 4行目の斜めは左から順に青・赤・赤・黄となっているため，累積和は 0, 1, 2, 2 となります)
赤黄黄黄赤

赤

青

1002113青青

赤青

黄赤

青

0020031黄赤

青

黄青

青

赤0100211青青黄赤黄青

青0002102黄黄青

黄青赤

黄0011021青黄赤

青

黄赤

青

0110110赤

青

黄赤

青

青

赤

1001001

右上方向に
累積和 (赤)次に，同じような累積和を右下方向にも取ります。すると，下図のようにして次の値を計算量 O(1) で求めることができるため，各 i に対して「色がすべて同じかどうか」を O(1) で判定できます。

• 中心からの距離が i である区画の中で，A x,y が赤であるような区画の個数• 中心からの距離が i である区画の中で，A x,y が黄であるような区画の個数• 中心からの距離が i である区画の中で，A x,y が青であるような区画の個数
したがって，rmax の計算にかかる時間が O(N) に減り，全体で計算量 O(N 3 ) となって小課題 3 に通ります。

右上方向の累積和
右下方向の累積和

右上方向の累積和問題 4- 4 / 8

右下方向の累積和第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)

小課題 4 (累計 48 点)
この小課題では，A x,y が赤以外の色であるような区画が高々 5 個しか存在しません。そのため，中心 (x, y)を決めて大きさ r をだんだん増やしていったとき，基本的には初めて赤以外の区画とぶつかったタイミングで植えられなくなります。たとえば下図左側の場合，大きさが 4 のときに初めて赤以外の区画とぶつかるた
め，大きさ 3 までしか植えることができません。
したがって，rmax の値は中心から最も近い「赤以外の区画」までの距離に 1 を引いた値となります。この性質を使うと，愚直に実装しても 5N 2 回程度の計算で答えが出るため，小課題 4 に通ります。
ただし，大きさ 1 の場合は下図右側のように，赤以外の区画とぶつかっても植えられるケースが存在します。場合分けをする必要があることに注意してください。

大きさ 4 で初めてぶつかる

中心 (5, 5)

大きさ 1 でぶつかるが植えられる

小課題 5 (累計 64 点)
この小課題では，どの 2 × 2 の範囲にも赤の区画が 3 つ以上存在します。そのため，小課題 4 と同様，rmaxの値は「中心から最も近い赤以外の区画までの距離*2 」に 1 を引いた値となります。
しかし小課題 4 とは違って，A x,y が赤以外の色であるような区画がたくさん (具体的には N 2 /4 個程度) あるため，自然に実装すると TLE になってしまいます。
そこで各区画を頂点，上下左右に隣り合う区画を辺とした重み無しグラフを考えます。すると，「中心から最も近い赤以外の区画までの距離」は，「グラフで赤以外の頂点から出発した時の最短経路の長さ」と同じなので，最短経路長さえ分かれば答えが求まります。(次ページの図を参照)*2 ただし，自分自身の区画は含めないものとします。

問題 4- 5 / 8

第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)

最も近い距離同じ

最短経路長01 2 3 4

それでは，最短経路長はどうやって求めれば良いのでしょうか。出発地点が 1 つの場合は，まず出発地点をキューに入れてから幅優先探索をすれば良いですが，今回は出発地点 (赤以外の区画) がたくさんあるので，何か工夫が必要だと思うかもしれません。
しかし，出発地点が 1 つの場合と同様，単純にすべての出発地点をキューに入れてから幅優先探索をしても，計算量 O(N 2 ) で各頂点への最短経路長が求まります*3 。なお，本小課題では中心以外に青や黄の花を植えることはありませんが，中心が青や黄になるケースもあるので，場合分けに注意してください。

小課題 6 (満点)
まず，中心を区画 (x, y) と決めたときに，大きさ r を達成できるための必要十分条件は，以下の図に書かれている 4 つの条件をすべて満たすことです。

条件1

条件3

この区画の色※ はこの区画の色※ はすべて左上の区画と同じすべて左下の区画と同じ

条件2

条件4

この区画の色※ はすべて右下の区画と同じ

この区画の色※ はすべて右上の区画と同じ
y-ryy-r※ここでの「色」は 𝑨𝒙,𝒚 のことを指す*3 このようになる理由は，もし出発地点が複数でも，各頂点がキューに 1 回ずつしか入らないからです。

問題 4- 6 / 8

第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)

したがって，中心を区画 (x, y) と決めたときに達成できる最大の大きさ rmax は，下図の値 1，値 2，値 3，
値 4，および max(x − 1, y − 1, N − x, N − y)*4 の最小値となります。

値1

値3

この範囲の区画の中で左下と色が異なるものにおける中心からの距離の最小値

この範囲の区画の中で左上と色が異なるものにおける中心からの距離の最小値

中心値4

値2

この範囲の区画の中で右上と色が異なるものにおける中心からの距離の最小値

この範囲の区画の中で右下と色が異なるものにおける中心からの距離の最小値

それでは，値 1，値 2，値 3，値 4 はどうやって求めれば良いのでしょうか。実は動的計画法を使えば簡単です。たとえば値 1 の場合，以下のような式になります。

• dp[0][ j] = 0• dp[i][0] = 0• Ai, j = Ai+1, j−1 の場合，dp[i][ j] = min(dp[i − 1][ j], dp[i][ j − 1]) + 1• Ai, j , Ai+1, j−1 の場合，dp[i][ j] = 0• 中心が (x, y) のときの値 1 は dp[x − 1][y] に相当
動的計画法の計算の例を下図に示します。(右の図では，Ai, j = Ai+1, j−1 の区画を濃い色で示しています)

赤黄黄黄赤赤青0000000青青赤青黄赤青0012300黄赤青黄青青赤0023000青

青

黄赤

黄

青

青

0030120黄黄青

黄青

赤黄0000200青

黄赤

青

黄赤

青

0000001

赤青

黄赤

青

青

赤

0000000

値 1 の計算*4 x, y は r + 1 ≤ x ≤ N − r ，r + 1 ≤ y ≤ N − r を満たすように選ぶ必要があるので，たとえば全部 A x,y が同じであるようなケース

でも，r ≤ max(x − 1, y − 1, N − x, N − y) を満たす必要があることに注意してください。

問題 4- 7 / 8

第 23 回日本情報オリンピック (JOI 2023/2024) 二次予選

2023 年 12 月 10 日 (オンライン開催)

以上のことを行うと，値 1，値 2，値 3，値 4 の計算を O(N 2 ) 時間，各中心に対する rmax の値の計算をO(1) 時間で行うことができるため，全体で計算量 O(N 2 ) で本問題を解くことができました。
なお，この問題は実装がやや複雑ですが，情報オリンピックでは過去にも複雑な実装の問題が何問か出題されているので，来年以降チャンスのある選手はぜひ実装力もつけておきましょう。

(解説は以上です)

問題 4- 8 / 8