JOIG 2021 過去問

A - 金平糖 (Konpeito)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 高校の生徒である葵と凛は，教師の理恵先生と一緒に 3 人で金平糖を同じ数だけ食べることにした．

いま，葵は A 粒，凛は B 粒，理恵先生は C 粒の金平糖を食べた．3 人が食べた金平糖の個数を等しくするには，最小で合計いくつの金平糖を追加で食べる必要があるだろうか．

3 人が食べた金平糖の個数 A, B, C が与えられたとき，追加で食べる金平糖の個数の最小値を求めるプログラムを作成せよ．

制約

1 \leqq A \leqq 100．
1 \leqq B \leqq 100．
1 \leqq C \leqq 100．
入力される値はすべて整数である．

小課題

(40 点) A < B < C．
(60 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解となる．

各提出の得点は，提出されたソースコードが正解した小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力

入力は以下の形式で標準入力から与えられる．

A B C

出力

標準出力に，追加で食べる金平糖の個数の最小値を 1 行で出力せよ．

入力例 1

4 6 9

出力例 1

葵は 4 粒，凛は 6 粒，理恵先生は 9 粒の金平糖を食べた．

葵が 5 粒の，凛が 3 粒の金平糖を追加で食べれば，3 人が食べた金平糖の個数はともに 9 個となる．このとき，追加で食べた金平糖は合計 8 粒である．

8 粒よりも少ない量を追加で食べて個数を等しくすることは不可能であるため，8 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 2

35 35 35

出力例 2

金平糖を追加で食べる必要がないため，0 を出力する．

この入力例は小課題 2 の制約のみを満たす．

B - 巻物 (Scroll)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 高校の生徒である葵は，図書室で巻物を見つけた．この巻物には長さ N の文字列 S が書かれており，文字列 S の各文字は j，o，i，J，O，I のいずれかである．

この巻物は持ち出しが禁じられているため，葵は文字列 S をすべて書き写すことにした．葵が記した文字列は T である．

しかし，葵は誤って前から K 番目 (1 \leqq K \leqq N) 以降の文字（K 番目の文字を含む）の大文字と小文字を逆に記してしまった．すなわち，1 \leqq i \leqq K-1 のとき，S の i 番目の文字と T の i 番目の文字は等しく，K \leqq i \leqq N のとき，S の i 番目の文字が大文字であれば T の i 番目の文字は小文字であり，S の i 番目の文字が小文字であれば T の i 番目の文字は大文字である．

文字列 T とその長さ N，値 K が与えられたとき，巻物に書かれていた文字列 S を復元するプログラムを作成せよ．

制約

1 \leqq K \leqq N \leqq 100．
T は長さ N の文字列である．
T の各文字は j，o，i，J，O，I のいずれかである．
N, K は整数である．

小課題

(30 点) N = 1，K = 1．
(70 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解となる．

各提出の得点は，提出されたソースコードが正解した小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力

入力は以下の形式で標準入力から与えられる．

N K
T

出力

標準出力に，巻物に書かれていた文字列 S を 1 行で出力せよ．

入力例 1

3 2
Joi

出力例 1

JOI

葵は文字列 JOI の 2 番目の文字 O を o に，3 番目の文字 I を i に書き間違えたため，文字列 Joi と記した．したがって，書き間違える前の文字列 JOI を出力する．

入力例 2

1 1
O

出力例 2

この入力例は小課題 1 の制約を満たす．

入力例 3

6 3
JoIOji

出力例 3

JoioJI

C - イルミネーション 2 (Illumination 2)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 高校の生徒である葵は，文化祭で廊下に電飾を飾ることにした．

電飾は，N 個の電球を東西方向に一列に並べて作る．電球には西側から順に 1 から N までの番号が付けられている．各電球にはオンとオフの 2 つの状態があり，はじめ電球はすべてオフの状態である．

葵が目標とする電飾の模様は数列 A_1, A_2, \ldots, A_N で表され，A_i = 1 のときは電球 i をオンに，A_i = 0 のときはオフにしたい．葵はできるだけ短い時間でこの模様にしようと考えた．

葵は最初に次の操作を 1 回だけ行うことができるが，行わなくてもよい．

西側の端から連続した区間の電球をオンにする．すなわち， 1 以上 N 以下の整数 r を 1 つ選び，電球 1, 2, \ldots , r をオンにする．

この操作を行うのにかかる時間は無視できる．

その後，次の操作を何回でも行うことができる．

電球を 1 つ選び，その電球の状態を変更する (オンならばオフに，オフならばオンにする)．

この操作を行うには 1 回につき 1 分かかる．

電球の個数，目標とする電飾の模様が与えられたとき，葵が目標の模様にするのに最短で何分かかるかを求めるプログラムを作成せよ．

制約

1 \leqq N \leqq 200\,000．
A_i は 0 か 1 のいずれかである (1 \leqq i \leqq N)．
入力される値はすべて整数である．

小課題

(45 点) N \leqq 2\,000．
(55 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解となる．

各提出の得点は，提出されたソースコードが正解した小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 \cdots A_N

出力

標準出力に，目標の模様にするのに最短で何分かかるかを 1 行で出力せよ．

入力例 1

6
0 1 1 0 0 1

出力例 1

例えば，葵は最初に r = 3 を選び，電球 1, 2, 3 をオンにする．この操作にかかる時間は 0 分である．その後，電球 1 をオンからオフに，電球 6 をオフからオンに状態を変更する．この操作にはそれぞれ 1 分ずつ合計で 2 分かかる．2 分未満で目標の模様にすることはできないので，2 を出力する．

入力例 2

4
0 0 0 1

出力例 2

この入力例では，葵は最初の操作は行わない．その後，電球 4 をオフからオンに状態を変更する．この操作には 1 分かかり，1 分未満で目標の模様にすることはできないので，1 を出力する．

入力例 3

4
1 1 1 1

出力例 3

この入力例では，葵は最初に r = 4 を選び電球 1, 2, 3, 4 をオンにすることで，目標の模様にすることができる．この操作にかかる時間は 0 分であるので，0 を出力する．

入力例 4

15
1 0 0 0 0 1 1 1 0 1 0 0 1 0 1

出力例 4

D - 展覧会 2 (Exhibition 2)

Time Limit: 1 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 美術館には，東西方向にまっすぐに伸びる廊下に N 枚の絵が飾られており，1 から N までの番号が付けられている．絵 i (1 \leqq i \leqq N) は廊下の西端から X_i メートルの位置に飾られており，その価値は V_i である．

この美術館では明日から「エゴイ展」が開催される予定であり，非常に多くの来客が見込まれている．「エゴイ展」では M 枚の絵を展示する予定である．

2 つの絵が近い位置に展示されていると見づらいので，以下の条件を満たすように N-M 枚の絵を取り外し，廊下に M 枚の絵だけを残すことにした．

どの 2 つの絵についても，位置が D メートル以上離れているようにする．

展示されている M 枚の絵の価値の最小値を，「エゴイ展」の華やかさとする．あなたは，廊下に残す M 枚の絵をうまく選ぶことで，「エゴイ展」の華やかさをできるだけ大きくしたい．

N 枚の絵の情報と廊下に残す絵の枚数が与えられたとき，条件を満たすような絵の残し方が存在するか判定し，もし存在する場合は，「エゴイ展」の華やかさの最大値を求めるプログラムを作成せよ．

制約

1 \leqq N \leqq 100\,000．
1 \leqq M \leqq N．
1 \leqq D \leqq 1\,000\,000\,000．
1 \leqq X_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
X_i \neq X_j (1 \leqq i < j \leqq N)．
1 \leqq V_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N)．
入力される値はすべて整数である．

小課題

(3 点) M = 1．
(12 点) M = N．
(19 点) N \leqq 15．
(17 点) N \leqq 1\,000，V_i \leqq 2 (1 \leqq i \leqq N)．
(22 点) N \leqq 1\,000．
(27 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解となる．

各提出の得点は，提出されたソースコードが正解した小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力

入力は以下の形式で標準入力から与えられる．

N M D
X_1 V_1
X_2 V_2
\vdots
X_N V_N

出力

条件を満たすような絵の残し方が存在しない場合，標準出力に -1 を 1 行で出力せよ．

条件を満たすような絵の残し方が存在する場合，標準出力に，「エゴイ展」の華やかさの最大値を 1 行で出力せよ．

入力例 1

出力例 1

絵 3 のみを残した場合，「エゴイ展」の華やかさは 500 となる．華やかさを 500 より大きくすることはできないため，500 を出力する．

この入力例は小課題 1, 3, 5, 6 の制約を満たす．

入力例 2

出力例 2

すべての絵を残すことができ，「エゴイ展」の華やかさは 115 となる．

この入力例は小課題 2, 3, 5, 6 の制約を満たす．

入力例 3

出力例 3

-1

どの 2 つの絵の間も 14 メートル以上離れているように絵を残すことはできない．したがって，－1 を出力する．

この入力例は小課題 2, 3, 5, 6 の制約を満たす．

入力例 4

出力例 4

この入力例は小課題 3, 4, 5, 6 の制約を満たす．

入力例 5

出力例 5

この入力例は小課題 3, 5, 6 の制約を満たす．

E - パレード (Parade)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 王国では，JOIG の開催を記念して鼓笛隊のパレードを行うことになった．

JOI 王国には N 個の都市があり，1 から N までの番号が付けられている．また，鼓笛隊が通行可能な一方通行の道が M 本あり，1 から M までの番号が付けられている．道 i (1 \leqq i \leqq M) は都市 A_i から都市 B_i へ向かう一方通行の道であり，長さは C_i である．

パレードでは，鼓笛隊は次の条件を満たすように移動しなければならない．

都市 1 を出発し，何本かの道を進行方向に進むことを繰り返して都市 N へ向かう．
鼓笛隊が通る道の長さの総和は L 以下である．

JOI 王国の女王であるあなたは，この条件を満たす鼓笛隊の移動経路が無いかもしれないことに気が付いた．そこで，パレードを行うために，パレード当日に 0 本以上の道の進行方向を反転させることにした．

混乱を避けるため，なるべく進行方向を反転させる道の本数は少なくしたい．

JOI 王国の都市と道の情報と，整数 L が与えられたとき，いくつかの道の進行方向を反転させることでパレードを行うことができるかを判定し，もし行うことができる場合はパレードを行うために必要な進行方向を反転させる道の本数の最小値を出力せよ．

制約

2 \leqq N \leqq 1\,000．
0 \leqq M \leqq 1\,000．
1 \leqq L \leqq 1\,000\,000\,000．
1 \leqq A_i \leqq N (1 \leqq i \leqq M)．
1 \leqq B_i \leqq N (1 \leqq i \leqq M)．
A_i \neq B_i (1 \leqq i \leqq M)．
(A_i, B_i) \neq (A_j, B_j) (1 \leqq i < j \leqq M)．
1 \leqq C_i \leqq 1\,000\,000 (1 \leqq i \leqq M)．
入力される値はすべて整数である．

小課題

(7 点) M = N - 1，(A_i, B_i) = (i, i + 1) または (A_i, B_i) = (i + 1, i) (1 \leqq i \leqq M)．
(14 点) M は偶数，A_{2i - 1} = B_{2i}，A_{2i} = B_{2i - 1}，C_{2i - 1} = C_{2i} (1 \leqq i \leqq \frac M 2)．
(18 点) N \leqq 15，M \leqq 15．
(20 点) C_i = 1 (1\leqq i \leqq M)，L = 1\,000\,000\,000．
(20 点) C_i = 1 (1\leqq i \leqq M)．
(21 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解となる．

各提出の得点は，提出されたソースコードが正解した小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力

入力は以下の形式で標準入力から与えられる．

N M L
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

出力

標準出力に，パレードを行うために必要な進行方向を反転させる道の本数の最小値を 1 行で出力せよ．ただし，どのように道の進行方向を反転させてもパレードを行うことができない場合は，-1 を出力せよ．

入力例 1

3 2 5
2 1 2
2 3 3

出力例 1

道 1 の進行方向を反転させると，パレードを行うことができる．

これが最小値であるため，1 を出力する．

この入力例は小課題 1,3,6 の制約を満たす．

入力例 2

3 1 10
2 1 5

出力例 2

-1

どのように道の進行方向を反転させてもパレードを行うことができないため，-1 を出力する．

この入力例は小課題 3,6 の制約を満たす．

入力例 3

出力例 3

この入力例は小課題 2,3,6 の制約を満たす．

入力例 4

5 6 1000000000
5 2 1
2 3 1
3 4 1
4 2 1
2 1 1
1 3 1

出力例 4

この入力例は小課題 3,4,5,6 の制約を満たす．

入力例 5

6 15 777777
1 3 497295
4 1 422722
4 5 607164
2 3 135688
5 2 995652
5 1 670296
3 1 138860
4 6 736614
6 3 620085
2 1 796353
6 4 949756
4 2 750680
6 5 591550
5 3 229431
3 2 668173

出力例 5

この入力例は小課題 3,6 の制約を満たす．

F - デジタルアート (Digital Art)

Time Limit: 1 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 高校の生徒である葵はデジタルアート制作が趣味であり，今日も新しい画像を作った．

この画像のサイズは，縦 H ピクセル，横 W ピクセルであり，H \times W のマス目のような形で表される．ここで，上から i 行目 (1 \leqq i \leqq H)，左から j 列目 (1 \leqq j \leqq W) のピクセルを (i, j) で表す．各ピクセルは 1 つの色で塗られている．各色には 1 から 256 までの番号が付けられており，ピクセル (i, j) の色の番号は A_{i, j} である．

葵はこの画像を同級生である凛に見せたが，凛は「画像に使われている色の種類が多すぎる」という理由で気に入らなかった．そこで葵は，以下のように画像内のある領域を隠して，見える色の種類をできるだけ少なくできないかと考えた．

葵は S 個以下のピクセルを選んで隠す．
ただし，隠すピクセルの領域は 1 つの長方形で表されなければならない．

画像のデータと，隠すピクセルの個数の上限 S が与えられたとき，画像内のある領域を隠したときに見える色の種類の数としてありうる最小の値を求めるプログラムを作成せよ．

制約

1 \leqq H \leqq 1\,000．
1 \leqq W \leqq 1\,000．
1 \leqq S \leqq HW．
1 \leqq A_{i, j} \leqq 256 (1 \leqq i \leqq H，1 \leqq j \leqq W)．
入力される値はすべて整数である．

小課題

(8 点) H = 1，W \leqq 10．
(10 点) H \leqq 10，W \leqq 10．
(5 点) S = 1．
(6 点) A_{i, j} \leqq 2 (1 \leqq i \leqq H，1 \leqq j \leqq W)．
(5 点) A_{i, j} \leqq 4 (1 \leqq i \leqq H，1 \leqq j \leqq W)．
(13 点) A_{i, j} \leqq 15 (1 \leqq i \leqq H，1 \leqq j \leqq W)．
(13 点) A_{i, j} \leqq 30 (1 \leqq i \leqq H，1 \leqq j \leqq W)．
(15 点) A_{i, j} \leqq 70 (1 \leqq i \leqq H，1 \leqq j \leqq W)．
(25 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解となる．

各提出の得点は，提出されたソースコードが正解した小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力

入力は以下の形式で標準入力から与えられる．

H W S
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}

出力

標準出力に，画像内のある領域を隠したときに見える色の種類の数としてありうる最小の値を 1 行で出力せよ．

特に，見えるピクセルが一つもない状態にできる場合は 0 と出力せよ．

入力例 1

1 10 7
5 1 2 5 2 2 5 6 6 5

出力例 1

例えば，左から数えて 2 番目から 8 番目までのピクセルを隠すと，番号 5, 6 の色だけが見え，その種類の数は 2 となる．この場合，隠すピクセルは 7 個となり，条件を満たす．また，葵は見える色を 1 種類以下にすることはできない．よって 2 を出力する．

この入力例は小課題 1, 2, 6, 7, 8, 9 の制約を満たす．

入力例 2

10 10 45
1 1 1 1 1 1 1 1 1 1
1 1 1 2 2 3 3 1 1 1
1 1 2 1 2 3 1 3 1 1
1 2 1 2 6 6 3 1 3 1
1 2 2 6 1 1 6 3 3 1
1 4 4 6 1 1 6 5 5 1
1 4 1 4 6 6 5 1 5 1
1 1 4 1 4 5 1 5 1 1
1 1 1 4 4 5 5 1 1 1
1 1 1 1 1 1 1 1 1 1

出力例 2

例えば，左上をピクセル (2, 1)，右下をピクセル (7, 7) とする長方形領域を隠すと，番号 1, 3, 4, 5 の色だけが見え，その種類の数は 4 となる．この場合，隠すピクセルは 42 個となり，条件を満たす．

この説明を図で表すと，以下のようになる．

この入力例は小課題 2, 6, 7, 8, 9 の制約を満たす．

入力例 3

5 10 1
2 3 5 7 1 1 1 3 1 7
1 9 2 3 2 9 3 1 3 7
4 1 4 3 4 7 5 3 5 9
6 1 6 7 7 1 7 3 7 9
8 3 8 9 9 7 2 3 5 7

出力例 3

隠すピクセルを S = 1 個以下にするという条件の下では，葵は番号 1, 2, 3, \ldots, 9 の 9 種類の色が見えるようにしかできない．よって 9 を出力する．

この入力例は小課題 2, 3, 6, 7, 8, 9 の制約を満たす．

入力例 4

9 6 54
1 1 1 1 1 3
6 14 14 3 3 12
9 13 1 10 3 3
9 13 5 5 3 3
6 13 10 3 7 3
2 5 8 5 3 3
6 5 5 3 15 3
6 5 10 5 3 3
2 2 5 7 3 3

出力例 4

54 個すべてのピクセルを隠して，見えるピクセルが一つもないようにできる．よって 0 を出力する．

この入力例は小課題 2, 6, 7, 8, 9 の制約を満たす．

入力例 5

8 10 59
3 3 3 3 3 3 3 3 2 3
3 1 3 3 3 3 3 2 3 3
3 3 1 4 3 4 2 3 3 3
3 3 3 1 4 2 4 3 3 3
3 3 3 4 1 4 2 3 3 3
3 3 3 1 4 3 4 2 3 3
3 3 1 3 3 3 3 3 2 3
3 1 3 3 3 3 3 3 3 3

出力例 5

例えば，左上をピクセル (3, 1)，右下をピクセル (10, 7) とする長方形領域を隠すと，番号 1, 3 の色だけが見え，その種類の数は 2 となる．この場合，隠すピクセルは 56 個となり，条件を満たす．

この説明を図で表すと，以下のようになる．

この入力例は小課題 2, 5, 6, 7, 8, 9 の制約を満たす．