The 4th Japanese Olympiad in Informatics for Girls (JOIG 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Tricolor Lights

三色灯 (Tricolor Lights)

賭け事の達人である Anna と Bruno の 2 人組は，ディーラーのディ太郎を相手にゲームで勝負することとなった．
ゲーム中，Anna と Bruno は別々の部屋に隔離され，ディ太郎を介してのみやりとりができる．
このゲームでは横一列に並んだ N 個のライトを用いる．これらのライトには左から順に 1 から N までの番号が付けられている．これらのライトは赤，緑，青のうち，いずれかの色に点灯させることができる．

Anna は，ゲーム開始時にこれらのライトそれぞれについて赤，緑，青のいずれかの色に点灯させる．また，ディ太郎により，それぞれのライトについて 1 つの禁止色が定められており，これは長さ N の文字列 Sによって表される．S の i 文字目 (1 ≦ i ≦ N) を S i とすると，ライト i の禁止色は，S i が ‘R’ のとき赤，‘G’のとき緑，‘B’ のとき青である．Anna はライト i をそのライトの禁止色に点灯させることができない．例えば，S 1 が ‘R’ であるならば，Anna はライト 1 について，緑か青のいずれかの色に点灯させなければならな
い．ディ太郎がそれぞれのライトについて定めた禁止色の情報は，Anna には伝えられるが，Bruno には伝えられない．

Anna はそれぞれのライトを点灯させたのち，1 ≦ l ≦ min(N, 130) を満たす整数 l を選び，ディ太郎に伝える．ディ太郎は，Bruno にライトの個数 N と，Anna が選んだ整数 l を伝える．その後，Q 回のラウンドを行う． j 回目 (1 ≦ j ≦ Q) のラウンドは，以下のように進行する．

1. ディ太郎は 1 以上 N − l + 1 以下の整数 a j を選び，ライト a j , a j + 1, . . . , a j + l − 1 について点灯している色の並びを Bruno に見せる．

2. Bruno は，見せられた色の並びをもとに，1 つの整数をディ太郎に伝える．この整数が a j と一致す
れば，このラウンドで Anna と Bruno は勝利する．
ただし，ディ太郎は，Anna が点灯させたライトの色の並びや整数 l に応じて， a1 , a2 , . . . , aQ の選び方を変える可能性がある．

Anna と Bruno が Q 回すべてのラウンドで勝利するための戦略を実装したプログラムを作成せよ．

三色灯– 1 / 6

The 4th Japanese Olympiad in Informatics for Girls (JOIG 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Tricolor Lights実装の詳細
あなたは 2 つのファイルを提出しなければならない．

1 つ目のファイルは Anna.cpp という名前である．このファイルは Anna の戦略を実装したファイルであり，以下の関数を実装していなければならない．また，#include プリプロセッサ指令によって Anna.h を読み込むこと．

• std::pair<std::string, int> anna(int N, std::string S)
この関数は，最初に 1 回だけ呼び出される．

◦ 引数 N は，ライトの個数を表す整数 N である．
◦ 引数 S は，ディ太郎が定めた禁止色を表す長さ N の文字列 S である．
◦ 戻り値は，Anna がそれぞれのライトに点灯させる色を表す長さ N の文字列 t，整数 l のペアである．t の i 文字目 (1 ≦ i ≦ N) を ti とすると，Anna が i 番目のランプを色 ti に点灯させることを意味する．ti は，‘R’ のとき赤，‘G’ のとき緑，‘B’ のとき青を意味する．

◦ 文字列 t の長さは N でなければならない．これが満たされない場合，不正解 [1] と判定される．
◦ 文字列 t の各文字は ‘R’ または ‘G’ または ‘B’ でなければならない．これが満たされない場合，不正解 [2] と判定される．

◦ 文字列 t の i 文字目 (1 ≦ i ≦ N) は S の i 文字目と異ならなければならない．これが満たされない場合，不正解 [3] と判定される．

◦ l は 1 以上 min(N, 130) 以下でなければならない．これが満たされない場合，不正解 [4] と判定される．

2 つ目のファイルは Bruno.cpp という名前である．このファイルは Bruno の戦略を実装したファイルであり，以下の関数を実装していなければならない．また，#include プリプロセッサ指令によって Bruno.hを読み込むこと．

• void init(int N, int l)
この関数は，最初に 1 回だけ呼び出される．

◦ 引数 N は，ライトの個数を表す整数 N である．
◦ 引数 l は，Anna が指定した整数 l である．
• int bruno(std::string u)
この関数は，関数 init が呼び出された後に，合計で Q 回呼び出される． j 回目 (1 ≦ j ≦ Q) の呼び出しは，ゲームにおける j 回目のラウンドの手順 1. および手順 2. に相当する．

◦ 引数 u は ‘R’, ‘G’, ‘B’ からなる長さ l の文字列で，ライト a j , a j + 1, . . . , a j + l − 1 に点灯している色の並びを表す．u の k 文字目 (1 ≦ k ≦ l) を uk とすると，Anna が a j + k − 1 番目のランプに点三色灯– 2 / 6

The 4th Japanese Olympiad in Informatics for Girls (JOIG 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Tricolor Lights
灯させた色は，uk が ‘R’ のとき赤，‘G’ のとき緑，‘B’ のとき青である．

◦ 戻り値は，Bruno が答える整数である．
◦ 戻り値は，a j と一致していなければならない．これが満たされない場合，不正解 [5] と判定される．

重要な注意• 内部での使用のために他の関数を実装したり，グローバル変数を宣言するのは自由である．ただし，提出された 2 つのプログラムは，採点プログラムとまとめてリンクされて 1 つの実行ファイルになるので，各ファイル内のすべてのグローバル変数と内部関数を無名名前空間内で宣言して，他のファイルとの干渉を避ける必要がある．採点時には，このプログラムは Anna 側，Bruno 側として 2 個のプロセスとして実行されるので，Anna 側と Bruno 側でプログラム中のグローバル変数を共有することはできない．

• あなたの提出したプログラムは，標準入力・標準出力，あるいは他のファイルといかなる方法でもやりとりしてはならない．ただし，標準エラー出力にデバッグ情報等を出力することは許される．

コンパイル・実行の方法
作成したプログラムをテストするための，採点プログラムのサンプルが，コンテストサイトからダウンロードできるアーカイブの中に含まれている．このアーカイブには，提出しなければならないファイルのサンプルも含まれている．
採点プログラムのサンプルは 1 つのファイルからなる．そのファイルは grader.cpp である．作成したプログラムをテストするには，grader.cpp，Anna.cpp，Bruno.cpp，Anna.h，Bruno.h を同じディレクトリに置き，次のようにコマンドを実行する．なお，アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい．

g++ -std=gnu++20 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
コンパイルが成功すれば，grader という実行ファイルが生成される．
実際の採点プログラムは，採点プログラムのサンプルとは異なることに注意すること．採点プログラムのサンプルは単一のプロセスとして起動する．このプログラムは，標準入力から入力を読み込み，標準出力に結果を出力する．

三色灯– 3 / 6

The 4th Japanese Olympiad in Informatics for Girls (JOIG 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Tricolor Lights

採点プログラムのサンプルの入力
採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む．

NSQ
a1 a2 · · · aQ
採点プログラムのサンプルは，実際の採点プログラムと異なり，初めから固定された答えを持つ必要がある．a j (1 ≦ j ≦ Q) は，ディ太郎が j 回目のラウンドで選ぶ整数 a j を表す．あなたが書いたプログラムにおいて Anna が選んだ整数 l に対して，1 ≦ a j ≦ N − l + 1 を満たさなければならない．

採点プログラムのサンプルの出力
採点プログラムのサンプルは標準出力へ以下の情報を出力する（引用符は実際には出力されない）．

• 正解の場合，Anna が選んだ整数 l が “Accepted: 130” のように出力される．
• 不正解の場合，不正解の種類が “Wrong Answer [1]” のように出力される．
実行するプログラムが複数の不正解の条件を満たした場合，表示される不正解の種類はそれらのうち 1 つのみである．

採点に関する注意
実際の採点プログラムは，Anna が点灯させたライトの色の並びや選んだ整数 l に応じて a1 , a2 , . . . , aQ を定める．特に，Bruno が答えた整数によって a1 , a2 , . . . , aQ の値を変えることはない．

制約• 1 ≦ N ≦ 500 000．
• 1 ≦ Q ≦ 10 000．
• S は ‘R’,‘G’,‘B’ からなる長さ N の文字列である．
• N, Q は整数である．

三色灯– 4 / 6The 4th Japanese Olympiad in Informatics for Girls (JOIG 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Tricolor Lights

採点に関する注意
特定のテストケースについて，実際の採点プログラムは適応的 (adaptive) である．これは，採点プログラ
ムは Anna が点灯させたライトの色の並びや選んだ整数 l に応じて a1 , a2 , . . . , aQ の選び方を変える可能性があることを意味する．

小課題
1. (10 点) N ≦ 131．
2. (10 点) N ≦ 250．
3. (10 点) N ≦ 380．
4. (20 点) N ≦ 7 000．
5. (50 点) 追加の制約はない．この小課題では，以下に従い得点が決定される．
• この小課題のすべてのテストケースにおける，Anna が選んだ整数 l の最大値を l∗ とする．
• このとき，小課題の得点は以下のように決定される．
l∗ の値

得点61 < l∗ ≦ 13015 点∗

41 < l ≦ 6125 点

34 < l∗ ≦ 4130 + 2 × (41 − l∗ ) 点

28 < l∗ ≦ 34

44 + 1 × (34 − l∗ ) 点l∗ ≦ 2850 点

三色灯– 5 / 6

The 4th Japanese Olympiad in Informatics for Girls (JOIG 2023/2024)
Spring Training/Qualifying Trial
March 20–24, 2024 (Komaba, Tokyo)
Contest 1 – Tricolor Lights

やりとりの例
採点プログラムのサンプルが読み込む入力の例と，それに対応する関数の呼び出しの例を以下に示す．
入力例 1関数の呼び出しの例
呼び出し

戻り値

8anna(8, "RGGBRBBG")("BBRGBGRR", 5)

RGGBRBBG

init(8, 5)

2bruno("RGBGR")

33 1

bruno("BBRGB")

1

このやりとりの例において，Anna はライトの個数 N = 8，禁止色を表す文字列 S = "RGGBRBBG" を受け取り，それぞれのライトに点灯させる色を表す文字列 t として "BBRGBGRR" ，整数 l として 5 を指定し，ディ太郎に伝える．その後，ディ太郎は Bruno に整数 N = 8, l = 5 を伝える．

1 回目のラウンドでは，ディ太郎は a1 = 3 としている．Bruno はライト 3, 4, 5, 6, 7 に点灯している色の並びを表す文字列 u = "RGBGR" を受け取り，a1 である 3 を答える．
入力例 1 はすべての小課題の制約を満たす．コンテストサイトからダウンロードできるファイルのうち，sample-01-in.txt は入力例 1 に対応する．

三色灯– 6 / 6