以下是来自日本的原始新闻PDF,已完整保存和染色。




可复制的 PDF 提取文本
The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
JOI Open Contest
June 16, 2024
examination2
試験2 (Examination 2)
JOI 君の通うIOI 高校では,近いうちに定期試験が行われる予定である.試験では,IOI 高校が独自に
ルールを定めたIOI 関数の値を正しく計算できるかどうかが問われる.IOI 関数とは以下の6 種類のいずれ
かのルールにより得られる文字列のことであり,1 以上109 以下の整数にTrue またはFalse の真偽値を対
応させる.
1. a を1 以上109 以下の整数として,[a] はIOI 関数である(ただし,a はa を十進表記して得られる
文字列とする).このIOI 関数はa 以上の整数にTrue を,a 未満の整数にFalse を対応させる.
2. f をIOI 関数として,(f) はIOI 関数である.このIOI 関数はf がTrue に対応させる整数にTrue
を,f がFalse に対応させる整数にFalse を対応させる.
3. f をIOI 関数として,!f はIOI 関数である.このIOI 関数はf がTrue に対応させる整数にFalse
を,f がFalse に対応させる整数にTrue を対応させる.
4. f, g をIOI 関数として,f&g はIOI 関数である.このIOI 関数はf, g の両方がTrue に対応させる整
数にTrue を,そうでない整数にFalse を対応させる.
5. f, g をIOI 関数として,fˆg はIOI 関数である.このIOI 関数はf, g のちょうど一方がTrue に対応
させる整数にTrue を,そうでない整数にFalse を対応させる.
6. f, g をIOI 関数として,f|g はIOI 関数である.このIOI 関数はf, g の少なくとも一方がTrue に対
応させる整数にTrue を,そうでない整数にFalse を対応させる.
あるIOI 関数が複数のルールから得られる場合,より番号の大きいルールによりIOI 関数が対応させる真
偽値を定めるものとする.例えば[1]&[2]|[3] の場合にはf = [1]&[2], g = [3] に対してルール6 が適
用される(f = [1], g = [2]|[3] に対してルール4 が適用されるのではない).さらに,ルール4, 5, 6 につ
いては,よりf が長くなるようにルールが適用される.例えば[4]ˆ[5]ˆ[6] の場合にはf = [4]ˆ[5], g =
[6] に対してルール5 が適用される(f = [4], g = [5]ˆ[6] に対してルール5 が適用されるのではない).
JOI 君は試験勉強として,長さがN であるIOI 関数S を用意し,Q 個の整数X1, X2, . . . , XQ についてこ
の関数が対応させる真偽値を求める練習をしようと考えている.そこで,IOI 関数の扱いに長けているあな
たに模範解答を作るよう頼んできた.
N, Q, S およびX1, X2, . . . , XQ が与えられるので,X1, X2, . . . , XQ について,JOI 君の用意したIOI 関数が
対応させる真偽値を求めるプログラムを作成せよ.
試験2– 1 / 4
The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
JOI Open Contest
June 16, 2024
examination2
入力
入力は以下の形式で標準入力から与えられる.
N Q
S
X1
X2
...
XQ
出力
標準出力にQ 行出力せよ.i 行目(1 ≦i ≦Q) には,JOI 君の用意したIOI 関数が整数Xi に対応させる真
偽値を出力せよ.
制約
• 1 ≦N ≦1 000 000.
• 1 ≦Q ≦200 000.
• S は長さN のIOI 関数である.
• 1 ≦Xi ≦109 (1 ≦i ≦Q).
• N, Q およびXi (1 ≦i ≦Q) はすべて整数である.
小課題
1. (5 点) S は&, | を含まない.
2. (20 点) Q = 1.
3. (10 点) N ≦10 000.
4. (6 点) S は!, ˆ を含まない.
5. (12 点) S が得られる過程でルール4 またはルール6 が適用されたとき,f, g のうち少なくとも一方
はルール1 によって得られるIOI 関数であった.
6. (20 点) N ≦400 000.
7. (27 点) 追加の制約はない.
試験2– 2 / 4
The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
JOI Open Contest
June 16, 2024
examination2
入出力例
入力例1 出力例1
15 5 True
(![2]|[3])&![4] False
1 True
2 False
3 False
4
5
問題文中のルールによりS が得られる過程で現れるIOI 関数のうち一部について,それが各Xi (1 ≦i ≦Q)
に対応させる真偽値を求めると,次の表のようになる.
Xi ![2] [3] ![2]|[3] ![4] (![2]|[3])&![4]
1 True False True True True
2 False False False True False
3 False True True True True
4 False True True False False
5 False True True False False
この入力例は小課題3, 6, 7 の制約を満たす.
入力例2 出力例2
20 4 True
(!![23])ˆ((([116]))) False
54 False
1 True
200
89
この入力例は小課題1, 3, 5, 6, 7 の制約を満たす.
試験2– 3 / 4
The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
JOI Open Contest
June 16, 2024
examination2
入力例3 出力例3
32 4 True
[2]|[5]&[1]|(([1000000000])|[7]) True
4 True
10 False
6
1
この入力例は小課題3, 4, 6, 7 の制約を満たす.
試験2– 4 / 4