JOI 2019/2020 二次予選過去問

A - ポスター (Poster)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 君は文化祭でのクラスの出し物を宣伝するため，ポスターを作った．そのポスターは N 行 N 列のマス目の形をしており，各マスは赤，緑，青のいずれかの色で塗られている．ポスターの上から i 行目，左から j 列目 (1 \leqq i \leqq N，1 \leqq j \leqq N) にあるマスの色は，S_{i,j}=R のとき赤色，S_{i,j}=G のとき緑色，S_{i,j}=B のとき青色である．

しかし，このポスターにクラスのみんなは満足してはくれなかった．話し合いの結果，マス目の形は変えずに色の配置を変えることで，新しいポスターを作ることに決まった．新しいポスターの上から i 行目，左から j 列目 (1 \leqq i \leqq N，1 \leqq j \leqq N) にあるマスの色は，T_{i,j}=R のとき赤色，T_{i,j}=G のとき緑色，T_{i,j}=B のとき青色となるようにする．

JOI 君は今あるポスターに以下のいずれかの作業を繰り返し行うことで，新しいポスターを作ることにした．

マスを一つ選び，そのマスの色を好きな色に塗りなおす．
ポスター全体を 90^{\circ} 時計回りに回転させる．このとき，もともと上から i 行目，左から j 列目 (1 \leqq i \leqq N，1 \leqq j \leqq N) にあるマスは，上から j 行目，左から N-i+1 列目にあるマスに移動する．
ポスター全体を 90^{\circ} 反時計回りに回転させる．このとき，もともと上から i 行目，左から j 列目 (1 \leqq i \leqq N，1 \leqq j \leqq N) にあるマスは，上から N-j+1 行目，左から i 列目にあるマスに移動する．

JOI 君はどの作業をするにも 1 分かかる．JOI 君が作ったポスター，新しく作るポスターの情報が与えられたとき，JOI 君が新しいポスターを作るのに最短で何分かかるかを求めるプログラムを作成せよ．

制約

1 \leqq N \leqq 500．
S_{i,j} は R，G，B のいずれかである．
T_{i,j} は R，G，B のいずれかである．

入力

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

N
S_{1,1} \cdots S_{1,N}
\vdots
S_{N,1} \cdots S_{N,N}
T_{1,1} \cdots T_{1,N}
\vdots
T_{N,1} \cdots T_{N,N}

出力

新しいポスターを作るのに最短で何分かかるかを 1 行で出力せよ．

入力例 1

3
RRR
GGG
BBB
RRR
RRR
RRR

出力例 1

2 行目と 3 行目にあるマス目をすべて赤色に塗りかえればよい．これには 6 分かかる．

入力例 2

3
RRR
GGG
BBB
RGB
RGB
RGB

出力例 2

ポスター全体を 90^{\circ} 反時計回りに回転させればよい．これには 1 分かかる．

入力例 3

6
RRRBBB
RRRBBB
RRRBBB
GGGRRG
GGGRRG
GGGBBR
RRRGGG
RRRGGG
RRRGGG
BBBRRB
BBBRRB
BBBGGR

出力例 3

B - いちご (Strawberry)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

Just Oishi Ichigo 農園 (以下 JOI 農園) は東西に細長いことで有名ないちご農園であり，その入り口は農園の最も西にある．以下では，入り口から東に k メートル進んだ場所を地点 k と呼ぶことにする．

JOI 農園内には N 個のいちごがなっている．それぞれ 1 から N の番号がつけられている．どのいちごも時刻 0 までは青い．いちご i (1 \leqq i \leqq N) は地点 A_i に実をつけており，時刻 T_i になると熟し赤い状態になる．

いちごは青い状態では収穫できない．つまり，いちご i は時刻 T_i となるまで収穫できない．あなたは時刻 0 に地点 0 にある農園の入り口から出発して，最大秒速 1 メートルで東西方向に移動しながらいちごを収穫する．いちごを収穫するのにかかる時間は無視できるとする．

いちご農園についての情報が与えられるので，すべてのいちごを赤い状態で収穫したあと入り口に帰ってくるまでにかかる時間の最小値を求めるプログラムを作成せよ．

制約

1 \leqq N \leqq 100\,000．
0 \leqq A_i \leqq 1\,000\,000\,000 (=10^9) (1 \leqq i \leqq N)．
0 \leqq T_i \leqq 1\,000\,000\,000 (=10^9) (1 \leqq i \leqq N)．
入力される値はすべて整数である．

入力

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

N
A_1 T_1
A_2 T_2
\vdots
A_N T_N

出力

すべてのいちごを赤い状態で収穫したあと入り口に帰ってくるまでにかかる時間の最小値を 1 行に出力せよ．

入力例 1

出力例 1

はじめの 10 秒かけて地点 10 まで移動すると，その道中でいちご 2, 4, 5, 7, 8, 9, 10 をこの順に収穫することができる．その後 10 秒かけて地点 0 まで戻ると，その道中でいちご 6, 3, 1 をこの順に収穫することができる．これで 10 個すべてのいちごを赤い状態で収穫することができる．

入力例 2

出力例 2

以下のように移動すると 450 秒ですべてのいちごを赤い状態で収穫できる．

45 秒かけて地点 45 まで移動する．このとき時刻 45 なのでいちご 10 を収穫できる．収穫後 45 秒かけて地点 0 まで移動する．
その後，40 秒かけて地点 40 まで移動する．このとき時刻 130 なのでいちご 9 を収穫できる．収穫後 40 秒かけて地点 0 まで移動する．
その後，35 秒かけて地点 35 まで移動する．このとき時刻 205 なのでいちご 8 を収穫できる．収穫後 35 秒かけて地点 0 まで移動する．
その後，30 秒かけて地点 30 まで移動する．このとき時刻 270 なのでいちご 7 を収穫できる．収穫後 30 秒かけて地点 0 まで移動する．
その後，25 秒かけて地点 25 まで移動する．このとき時刻 325 なのでいちご 6 を収穫できる．収穫後 25 秒かけて地点 0 まで移動する．
その後，20 秒かけて地点 20 まで移動する．このとき時刻 370 なのでいちご 5 を収穫できる．収穫後 20 秒かけて地点 0 まで移動する．
その後，15 秒かけて地点 15 まで移動する．このとき時刻 405 なのでいちご 4 を収穫できる．収穫後 15 秒かけて地点 0 まで移動する．
その後，10 秒かけて地点 10 まで移動する．このとき時刻 430 なのでいちご 3 を収穫できる．収穫後 10 秒かけて地点 0 まで移動する．
その後，5 秒かけて地点 5 まで移動する．このとき時刻 445 なのでいちご 2 を収穫できる．収穫後 5 秒かけて地点 0 まで移動する．
ちょうど時刻 450 に地点 0 に到達するので，いちご 1 を収穫できる．すべてのいちごを収穫すると同時に地点 0 に到着した．

入力例 3

出力例 3

C - 桁和 (Digit Sum)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 君は初めに 1 以上 N 以下のある整数を持っていた．JOI 君は以下の操作を 0 回以上行ったところ，持っている整数が N になった．

持っている整数を十進法で表したときの各桁の和を，持っている整数に足す．

N が与えられるので，JOI 君が初めに持っていた可能性のある整数の個数を求めるプログラムを作成せよ．

制約

1 \leqq N \leqq 1\,000\,000．
N は整数である．

入力

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

出力

JOI 君が初めに持っていた可能性のある整数の個数を 1 行で出力せよ．

入力例 1

出力例 1

例えば JOI 君が初めに整数 5 を持っており，3 回操作を行った場合 5 \rightarrow 10 \rightarrow 11 \rightarrow 13 と変化する．JOI 君が初めに持っていた可能性のある整数は 5,10,11,13 の 4 個のみである．

入力例 2

出力例 2

入力例 3

出力例 3

D - テンキー (Tenkey)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 君はテンキーを 1 つ持っている．このテンキーには 0 から 9 までの数字が印字されているキーが以下の図のように配置されている． 2 が印字されたキーの下，および 3 が印字されたキーの下にはキーは存在しないことに注意せよ．

テンキーの配置

またこのテンキーには，テンキーに配置されているキーのうち 1 つのキーを指し示すカーソルが存在している．カーソルは最初 0 が印字されているキーを指し示している．

JOI 君は 1 回の操作で次のうちのいずれかを選んで行うことができる：

カーソルを，現在カーソルが指し示しているキーと上下左右に隣接しているキーに移動させる．ただし，キーが存在しない場所にカーソルを移動させることはできない．
キーを押す．すなわち，カーソルが指し示しているキーに印字されている数字を入力する．この際，以前の操作によってすでに数字が入力されていた場合，すでに入力されていた数字のすぐ右に新たな数字が入力される．

いま，JOI 君はこのテンキーを使って， M で割った余りが R であるような正の整数を入力したいと考えている．テンキーの操作には時間がかかるので，なるべく少ない操作回数で入力したい．

M と R が与えられるので，JOI 君が行う必要のある操作の回数の最小値を求めるプログラムを作成せよ．

制約

2 \leqq M \leqq 100\,000．
1 \leqq R < M．
入力される値はすべて整数である．

小課題

(30 点) M = 100\,000．
(70 点) 追加の制限はない．

入力

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

M R

出力

M で割った余りが R であるような正の整数を入力するために必要な操作の回数の最小値を 1 行で出力せよ．

入力例 1

100000 13

出力例 1

この例では，以下の 5 回の操作を行うことによって 13 を入力することが可能である． 4 回以下の操作によって条件を満たす整数を入力することは不可能であるので， 5 を出力する．

カーソルを上に移動させる．カーソルが指し示すキーは 1 となる．
キーを押す． 1 が入力される．
カーソルを右に移動させる．カーソルが指し示すキーは 2 となる．
カーソルを右に移動させる．カーソルが指し示すキーは 3 となる．
キーを押す． 3 が新たに入力され，これまでに入力された数字は 13 となる．

入力例 2

4 3

出力例 2

この例では，3 回の操作を行うことによって 11 を入力することが可能である．3 を入力するには 4 回以上の操作を行わなければならず，最適ではないことに注意せよ．

E - じゃんけん式 (Rock-Scissors-Paper Expression)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

この問題では，じゃんけんの手「グー」「チョキ」「パー」をそれぞれ \mathrm{R}, \mathrm{S}, \mathrm{P} で表す．\mathrm{R} は \mathrm{S} に勝ち，\mathrm{S} は \mathrm{P} に勝ち，\mathrm{P} は \mathrm{R} に勝つ．

x, y をじゃんけんの手とするとき，x + y,\, x - y,\, x \ast y を以下のように定める (これらは通常の意味での足し算・引き算・掛け算ではない)：

x + y は，x \ne y のとき x と y のうち勝つ方とし，x = y のとき x とする．
x - y は，x \ne y のとき x と y のうち負ける方とし，x = y のとき x とする．
x \ast y は，x \ne y のとき \mathrm{R}, \mathrm{S}, \mathrm{P} のうち x でも y でもないものとし，x = y のとき x とする．

じゃんけんの手と +, -, \ast と括弧からなる式は，以下のように計算する：

括弧の中は先に計算する．例えば，\mathrm{R} \ast (\mathrm{P} + \mathrm{S}) = \mathrm{R} \ast \mathrm{S} = \mathrm{P} である．
括弧の深さが同じ部分については，
- +, - より \ast の方を優先して計算する．例えば，\mathrm{R} - \mathrm{P} \ast \mathrm{S} = \mathrm{R} - (\mathrm{P} \ast \mathrm{S}) = \mathrm{R} - \mathrm{R} = \mathrm{R} である．
- 同じ優先順位のもの (+ どうし，- どうし，+ と -，\ast どうし) については，左から順番に計算する．例えば，\mathrm{R} - \mathrm{P} + \mathrm{S} = (\mathrm{R} - \mathrm{P}) + \mathrm{S} = \mathrm{R} + \mathrm{S} = \mathrm{R} である．

JOI さんはあるじゃんけんの式を持っていたが，その式の中の \mathrm{R}, \mathrm{S}, \mathrm{P} の一部が見えなくなってしまった．見えなくなってしまった部分が ? で表された長さ N の文字列 E が与えられる．JOI さんは，見えなくなってしまった部分のそれぞれに \mathrm{R}, \mathrm{S}, \mathrm{P} のいずれかを割り当てる方法であって，式の計算結果が A になるものが何通りあるかを知りたい．その数は非常に大きくなる可能性があるので，1\,000\,000\,007 で割った余りを求めたい．

本問で用いられる文法は，BNF (バッカス・ナウア記法) を用いて以下のように表される．じゃんけんの式の一部が見えなくなってしまったものは <expression> である．

<expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= "R" | "S" | "P" | "?" | "(" <expression> ")"

これは例えば，ある文字列が <expression> であるとは，「<term> である」または「<expression> である文字列，+，<term> である文字列，をこの順に連結させたもの」または「<expression> である文字列，-，<term> である文字列，をこの順に連結させたもの」であることである，というように再帰的に定義されることを意味する．

<expression> である文字列 E と計算結果 A が与えられるので，? に \mathrm{R}, \mathrm{S}, \mathrm{P} のいずれかを割り当てる方法であって式の計算結果が A になるものの個数を 1\,000\,000\,007 で割った余りを求めるプログラムを作成せよ．

制約

1 \leqq N \leqq 200\,000．
E は長さ N の文字列である．
E は問題文で定められた <expression> である．
A は R または S または P である．

小課題

(20 点) N \leqq 15．
(20 点) N \leqq 200．
(60 点) 追加の制約はない．

入力

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

N
E
A

出力

標準出力に，? に \mathrm{R}, \mathrm{S}, \mathrm{P} のいずれかを割り当てる方法であって式の計算結果が A になるものの個数を 1\,000\,000\,007 で割った余りを 1 行で出力せよ．

入力例 1

11
S+?-(R+?)*P
S

出力例 1

2 箇所の ? に \mathrm{R}, \mathrm{S}, \mathrm{P} のいずれかを割り当てて計算結果を \mathrm{S} にする方法は，以下の 6 通りがある：

\mathrm{S} + \mathrm{R} - (\mathrm{R} + \mathrm{R}) \ast \mathrm{P}
\mathrm{S} + \mathrm{R} - (\mathrm{R} + \mathrm{S}) \ast \mathrm{P}
\mathrm{S} + \mathrm{S} - (\mathrm{R} + \mathrm{R}) \ast \mathrm{P}
\mathrm{S} + \mathrm{S} - (\mathrm{R} + \mathrm{S}) \ast \mathrm{P}
\mathrm{S} + \mathrm{P} - (\mathrm{R} + \mathrm{R}) \ast \mathrm{P}
\mathrm{S} + \mathrm{P} - (\mathrm{R} + \mathrm{S}) \ast \mathrm{P}

入力例 2

15
?+?-?*?+?-?*?+?
R

出力例 2

入力例 3

13
(((((R)))))+?
P

出力例 3

入力例 4

1
P
S

出力例 4

入力例 5

27
R+((?+S-?*P+?)-P*?+S-?)*R+?
P

出力例 5

入力例 6

83
((R+?)*(?+?))*((?+?)*(?+?))*((?+?)*(?+?))-((S+?)*(?+?))*((?+?)*(?+?))*((?+?)*(?+?))
P

出力例 6

460353133

条件を満たす割り当て方は 10\,460\,353\,203 通りあるため，それを 1\,000\,000\,007 で割った余りである 460\,353\,133 を出力する．