以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Security Gate
防犯ゲート(Security Gate)
あなたはJust Odd Inventions 社を知っているだろうか?この会社の業務は「ただ奇妙な発明(just odd
inventions)」をすることである.ここでは略してJOI 社と呼ぶ.
JOI 社は機密情報の流出を防ぐべく,出入り口に防犯ゲートを設置している.会社に出入りする際は必
ずこの防犯ゲートを通る必要がある.また,一度に2 人以上の人がこのゲートを通ることはできない.
この防犯ゲートは,人がゲートを通るたびに,会社に人が入った,または出た,という情報を記録して
いる.今,JOI 社の社員であるIOI 君の前には,ある1 日の防犯ゲートの記録がある.この記録は文字列
S で表される.S のi 文字目が‘(’ であるときは,i 番目に人がゲートを通った際,その人が会社に入った
ことを意味する.また,S のi 文字目が‘)’ であるときは,i 番目に人がゲートを通った際,その人が会社
から出たことを意味する.またIOI 君は,この日の始まりと終わりには,JOI 社内に誰もいなかったこと
を知っている.ここで,‘(’ と‘)’ のみからなる文字列であっても,記録としてはありえないものがある点
に注意せよ.例えば,())( や(() という記録は,JOI 社内にいる人数が負になったり,一日の終わりにま
だJOI 社内に人がいることになったりするので,ありえない.
IOI 君が記録を確認した次の瞬間,JOI 社内に蔓延しているコンピュータウィルスによって,文字列S が
変化してしまった.IOI 君は調査の結果,文字列S が次のような過程で変化したと予想した.
• まず,S のある連続する区間の文字が,すべて次のように変化した.その区間に含まれる文字全てに
ついて,その文字が‘(’ ならば‘)’ に変化し,‘)’ ならば‘(’ に変化した.変化後の文字列をS ′ とす
る.なお,変化した区間の長さが0 であること,つまり,S = S ′ であることもありうる.
• 次に,S ′ の0 個以上の文字が‘x’ に変化した.変化後の文字列をS ′′ とする.
IOI 君はS の情報を覚えていないため,S ′′ からS を復元しようと考えている.そのためにIOI 君はま
ず,S ′ としてあり得るものが何通りあるかを調べることにした.(IOI 君が何通りあるかを調べるのは,S
ではなくS ′ であることに注意せよ.)
課題
文字列S ′′ が与えられたとき,S ′ としてあり得るものの個数を,1 000 000 007 で割った余りを求めよ.
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数N が書かれている.これは,変化後の文字列S ′′ の長さがN であることを表す.
• 2 行目には長さN の文字列S ′′ が書かれている.各文字は‘(’,‘)’,もしくは‘x’ のいずれかである.
これは,変化後の文字列がS ′′ であることを表す.
防犯ゲート– 1 / 3
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Security Gate
出力
S ′ としてあり得るものの個数を,1 000 000 007 で割った余りを出力せよ.もし,S ′ としてあり得るもの
がない場合は,0 を出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 1 ≦N ≦300.
小課題
この課題では小課題は全部で5 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [4 点]
• N ≦100.
• S ′′ 中の‘x’ の個数は4 個以下である.
小課題2 [8 点]
• N ≦100.
• S ′′ 中の‘x’ の個数は12 個以下である.
小課題3 [18 点]
• N ≦100.
• S ′′ 中の‘x’ の個数は20 個以下である.
小課題4 [43 点]
• N ≦100.
小課題5 [27 点]
追加の制限はない.
防犯ゲート– 2 / 3
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 3 – Security Gate
入出力例
入力例1 出力例1
4 3
x))x
入力例1 では,S ′ = )))( とすると,S としてありうるものが存在しないため,不適である.
以下の3 通りの文字列は,S ′ である可能性がある.
• S ′ = ())(.例えば,S = ()() とすればよい.
• S ′ = ())).例えば,S = ()() とすればよい.
• S ′ = )))).例えば,S = (()) とすればよい.
S ′ としてあり得るものはこれらのみなので,3 を出力する.
入力例2 出力例2
10 45
xx(xx()x(x
入力例3 出力例3
5 0
x))x(
入力例4 出力例4
10 684
xxxxxxxxxx
防犯ゲート– 3 / 3