日本情報オリンピック 第 4 回女性部門 (JOIG 2023/2024) 本選

2024 年 1 月 21 日 (オンライン開催)

6

感染シミュレーション (Infection Simulation)

解説作成者：米田優峻

小課題 1 (累計 2 点)
制約：Q ≤ 5，すべての客が時刻 0 に来店し，時刻 10 に退店する。
この小課題では，もし感染力 x が 10 以下であれば全員に感染し，そうでなければ最初に感染していた 1人しか感染しません。したがって， x ≤ 10 であれば N を，そうでなければ 1 を出力するプログラムを作成
すると，正解を出すことができます。

小課題 2 (累計 5 点)
制約：Q ≤ 5，すべての客が時刻 0 に来店する。
まず，最初に感染した客の退店時刻が感染力 x より小さい場合，伝染が起こる前にその客が帰ってしまいます。そのため，最終的な感染者数は 1 人となります。
そうでない場合，退店時刻が x かそれ以降である客が全員感染します。そのため，最終的な感染者数は

Ri ≥ x を満たす i (1 ≤ i ≤ N) の個数となります。単純に for 文を使って個数を計算すると，計算量は O(NQ)となり，Q ≤ 5 という制約下では実行時間制限に間に合います。

(1) 最初の感染者の退店時刻が感染力 𝒙 より早い
010

感染力
2030

(2) 最初の感染者の退店時刻が感染力 𝒙 かそれ以降
40

0

最初の感染者

10

感染力
2030

40

最初の感染者

伝染は起こらず
1 人しか感染しない

問題 6- 1 / 8

伝染が起こり退店時刻が 𝒙 以上の客が全員感染

日本情報オリンピック 第 4 回女性部門 (JOIG 2023/2024) 本選

2024 年 1 月 21 日 (オンライン開催)

小課題 3 (累計 11 点)
制約：すべての客が時刻 0 に来店する。
小課題 2 の解法では，Ri ≥ x を満たす i の個数を求める際に単純な for 文を使ったため，計算量が O(NQ)となりました。本小課題の制約は N, Q ≤ 100 000 であるため，残念ながらこの解法では TLE となります。
しかし，Ri をソートして二分探索をすることを考えてみましょう。すると，計算量が O((N + Q) log N) に削減され，正解を出すことができます。

小課題 4 (累計 21 点)
制約：N ≤ 500，Q ≤ 5，時刻は 500 以下
下図のように，時刻 1 ごとに「感染時間の累計」を更新していくシミュレーションを実装すると，この小課題に正解します。自然に実装した場合，時刻の最大値を T とするとき，計算量は O(NQT ) となります。

1

感染力が 2 のとき最終的に何人感染するか？
青字は感染時間の累計0

累計 -213

客2

累計 累計 2
累計 1
累計 0345

5 時刻客2客2

累計 2客3

累計 1客4234客2

65 時刻

問題 6- 2 / 8

5 時刻

客1
感染

客2
客3

客40

累計 1
客4

4

時刻 4～5
感染者はいないので累計に +1 しない

累計 2

客3

3

累計 0

累計 -

客1

累計 0

2

1

累計 0
客4

1

0

累計 2
客3

0

時刻 1～2
感染者はいるので今いる客の累計を +1 する

5 時刻

時刻 3～4
感染者はいないので累計に +1 しない

累計 -

客1

43

累計 -

累計 0

時刻 2～3
感染者はいるので今いる客の累計を +1 する
23

客1

累計 0
客4

累計 0

2

1

累計 1

客3

1

0
累計 -

累計 00

時刻 0～1
感染者はいるので今いる客の累計を +1 する

5 時刻

客1

累計 0

44

2

累計 0

2

1

3

4

客1
客2

客3
客45 時刻日本情報オリンピック 第 4 回女性部門 (JOIG 2023/2024) 本選

2024 年 1 月 21 日 (オンライン開催)

小課題 5 (累計 32 点)
制約：N ≤ 500，Q ≤ 5
この小課題では，時刻の最大値が 109 まであり得るため，小課題 4 のような「時刻 1 ごとにシミュレーションする解法」は通用しません。
そこで，「来店時刻／退店時刻として出てこない時刻を飛ばしてシミュレーションする」という発想を使うと，計算回数を削減することができます。(このような発想は座標圧縮と呼ばれています)
たとえば客が 4 人おり，それぞれの客が店にいる時刻が 10〜40，20〜80，45〜60，70〜95 であったとします。このとき，小課題 4 の解法では時刻 10, 11, 12, 13, · · · , 95 のように時刻 1 ごとにシミュレーションを行いました。しかし，時刻 10, 20, 40, 45, 60, 70, 80, 95 のみを考え，間の時刻を飛ばしてシミュレーションするという方法を使うと，計算回数が削減されます。イメージ図を以下に示します。
なお，「来店時刻／退店時刻として出てくる時刻」としては 2N 個あるため，計算量は 2N × N × Q = O(N 2 Q)となります。

小課題 4 の解法 (感染力 15 の場合)
時刻 10～11

時刻 11～12

時刻 12～13

累計 -

累計 -

累計 -

客1
客2

累計 0

客2
客3

累計 0
客4

累計 0

客1

累計 0

客3

累計 0
客4

累計 0

客2

累計 0

客3

累計 0

客1

客4

累計 0

小課題 5 の解法 (感染力 15 の場合)
時刻 10～20

時刻 20～40

累計 -

累計 -

累計 0
累計 0
累計 0

客1
客2

累計 20

客3

累計 0
客4

時刻 40～45

客1

感染客2

累計 20

客3

累計 0
客4

累計 0

問題 6- 3 / 8

累計 -累計 0客1
客2客3客4日本情報オリンピック 第 4 回女性部門 (JOIG 2023/2024) 本選

2024 年 1 月 21 日 (オンライン開催)

小課題 6 (累計 48 点)
制約：Q ≤ 5
それでは，先程説明した愚直シミュレーションを何とかして高速化することはできないのでしょうか。まず重要な考察として，一度感染者がいなくなったら，もう二度と感染は起こりません。
そのため，感染力が x であるとき，もし客 i が感染するならば，その感染時刻 Ii は必ず (最初の感染者の来店時刻と Li の大きい方) + x となります。たとえば下図の例で感染力が 15 である場合，I2 = 20 + 15 = 35，

I3 = 45 + 15 = 60，I4 = 70 + 15 = 85 となります。
したがって，現在の感染者数を表す変数 NumInfections を管理し，来店時刻 Li ，退店時刻 Ri ，感染時刻

Ii の 3N 個の時刻のみを考えたシミュレーションをすると*1 ，計算量 O(N log N) で答えを出すことができます。詳しい実装は JOI のホームページに掲載されている実装例を参照してください。

0客1客2
客310102030

最初の感染者
2040506070809010040
感染するなら時刻 35458060 感染するなら時刻 6070

客495
感染するなら時刻 85(次ページへ続く)*1 小課題 5 で，来店時刻 Li ，退店時刻 Ri の 2N 個の時刻のみを考えたシミュレーションを行ったことを思い出しましょう。

問題 6- 4 / 8

日本情報オリンピック 第 4 回女性部門 (JOIG 2023/2024) 本選

2024 年 1 月 21 日 (オンライン開催)

小課題 7, 8 (累計 75 点)
制約：L1 ≤ L2 ≤ · · · , LN , R1 ≤ R2 ≤ · · · ≤ RN , Pi = 1。なお，ここでは最初の感染者である客 1 の来店時刻が一番早いという前提で話を進める。
ここまでは，シミュレーションの高速化という方針で解説を行いました。しかし，ここからは少し考え方を変えて，感染者が店から消える時刻に着目してみましょう*2 。まず，感染者が店から消える時刻は，以下の条件を満たす時刻 R j の最小値となります。*3• 客 j の退店時刻 R j が終わった時点で，次のような客が店にいない。
• 来店時刻が R j − x かそれより前である。
例として，入力例 1 (下図) の場合を考えてみましょう。まず時刻 R1 = 40 が終わった時点では，来店時刻が 40 − 15 = 25 かそれより前の客が店にいるので，時刻 40 では感染者が消えません。続いて時刻 R2 = 60が終わった時点でも，来店時刻が 60 − 15 = 45 かそれより前の客が店にいるので，時刻 60 では感染者が消えません。しかし時刻 R3 = 80 が終わった時点では，来店時刻が 80 − 15 = 65 かそれより前の客が店にいません。よって時刻 80 に店から感染者が消えます。

0客1
客210102030

最初の感染者

506070809010040802045

客3客440

この時点で
時刻 25 以前に来店した客はいる

この時点で
時刻 45 以前に来店した客はいる

この時点で
時刻 65 以前に来店した客はいない→ここで途切れる

607095*2 小課題 6 で，一度感染者が店にいなくなったら，もう二度と感染が起こらないという考察がありました。そのため，感染者が消える時刻が計算できれば，この問題はほぼ解けたも同然です。
*3 もちろん，「最初の感染者の退店時刻かそれより後」の中での最小値を指しています。

問題 6- 5 / 8

日本情報オリンピック 第 4 回女性部門 (JOIG 2023/2024) 本選

2024 年 1 月 21 日 (オンライン開催)

したがって，各 j = 1, 2, · · · , N について，時刻 R j が終わった時点で店にいる客における来店時刻の最小値をを S j とするとき，感染力が x のシナリオにおける「感染者が消える時刻」は次式で表されます。

• R j − S j < x となる最小の R j
そこで S 1 , S 2 , · · · , S N の値は，ソートを利用することで計算量 O(N log N) で求めることができます。また，R j − S j < x となる最小の x の値についても，• R j の小さい順に見ていったときに R j − S j の最小値を更新する位置を前計算しておけば，二分探索によって計算量 O(log N) で求めることができます (下図参照)。以上で「感染者が消える時刻」を高速に計算することが出来ました。

0客1客21010203040605070809010040

最初の感染者802045

客36070客4
Rj - Sj = 25(最小値を更新)

Rj - Sj = 40(最小値を更新せず)

95

Rj - Sj = 10(最小値を更新)

Rj - Sj = 0(最小値を更新)

最後に，本題である「何人感染するかの計算」に戻ります。感染力が x，感染が止まる時刻を t とすると
き，客 i が感染する条件は以下の式で表されます。

• 来店時刻 Li が t − x かそれ以前• 店にいた時間 Ri − Li が x 以上である*4
したがって，感染者数の計算は「二次元平面上の座標 (L1 , R1 − L1 ), · · · , (LN , RN − LN ) に点があるとき，ある長方形領域に何個の点があるかを求める」という典型問題と等価です。そしてこの典型問題は平面走査+ セグメント木により O((N + Q) log N) 時間で解けるため，小課題 8 に正解することができます。
*4 もちろん，最初の感染者である客 1 の来店時刻が一番早いとは限らない場合，小課題 9 の解説に書かれている通り，さらに「退店時刻 Ri が (客 1 の来店時刻) + x かそれ以降」という条件が必要になります。しかし，本小課題では Pi = 1 であり，客 1 が一番早く来る仮定をおいても良いため，この条件を考える必要はありません。

問題 6- 6 / 8

日本情報オリンピック 第 4 回女性部門 (JOIG 2023/2024) 本選

2024 年 1 月 21 日 (オンライン開催)

小課題 9, 10 (累計 100 点)
制約：追加の制約はない
まずは「感染者が消える時刻」について考えましょう。小課題 8 と同様に各客 j (1 ≤ j ≤ N) に対して S jを定義したとき，感染者が消える時刻は次のようになります。

• R j ≥ (最初の感染者の退店時刻) を満たす中における，R j − S j < x となる最小の R j
小課題 8 と比べて「R j ≥ (最初の感染者の退店時刻)」という条件が新たに追加されているため，小課題 8のように最小値の更新位置を前計算する方法では解くことができません。しかし，RMQ*5 上で二分探索をすると，各シナリオについて O(log2 N) 時間で答えを出すことができます。
＊＊＊
問題は何人が感染するかです。感染力が x，感染が止まる時刻を t，最初の感染者の来店時刻を a とする
とき，客 i が感染する条件は以下の式で表されます。小課題 8 と比べて 2 つ目の条件が増えています。

• 来店時刻 Li が t − x かそれ以前• 退店時刻 Ri が a + x かそれ以降• 店にいた時間 Ri − Li が x 以上である
したがって，二次元平面上に点 (L1 , R1 ), (L2 , R2 ), · · · , (LN , RN ) をプロットしたとき，感染者数は下図のような領域に含まれる点の数と同じになります。

Riの値

直線 Ri – Li = xa+x
Li の値
t-x

*5 Range Minimum Query の略。セグメント木の一種。知らない方は Google 検索を試してみよ。

問題 6- 7 / 8

日本情報オリンピック 第 4 回女性部門 (JOIG 2023/2024) 本選

2024 年 1 月 21 日 (オンライン開催)

それでは，このような点の数はどうやって求めれば良いのでしょうか。まず，全体の領域は下図の領域(1), (2), (3) を使って，(1) - (2) - (3) という形で表すことができます。また，領域 (1) にある点の数は，Ri − Liを小さい順にソートして二分探索することで簡単に計算できます。

全体領域3

領域1
領域2

問題は領域 (2) にある点の数ですが，下図のように横軸を Ri − Li ，縦軸を Ri とした座標系に変換すると，長方形領域内に何個の点が含まれるかを求める問題に帰着されます。したがって，小課題 8 のように平面走
査 + セグメント木を使うと，各シナリオにつき O(log N) で計算できます。領域 (3) も同様です。
以上の考察を使うと，各シナリオにつき計算量 O(log N) で感染者数を計算することができます。これでようやく，最後の小課題を解くことができました。

Riの値
a+x

直線 Ri – Li = x(L3, R3)(L2, R2)

座標変換

Riの値

a+x

(L1, R1)(L3, R3)

直線 Ri – Li = x(L2, R2)(L1, R1)

Ri - Li の値

Li の値

総評
この問題はかなり多くの考察ステップを必要とする難易度の高い問題です。これを解かれた方はヨーロッパ女子情報オリンピック (EGOI) で優勝を狙える実力がありますので，ぜひ自信を持っていただければと思います。

問題 6- 8 / 8