The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle

最後の戦い (The Last Battle)

JOI 放送局が開催する人気バラエティ番組 JOICup は，いよいよ最終ラウンドを迎えることになった．最終ラウンドでは「メッセンジャーゲーム」が行われ，予選を勝ち抜いた Anna と Bruno の 2 人からなるチームのみが出場する．
メッセンジャーゲームは，8 行 8 列のマス目を介して情報を伝えるゲームである．マス目の各行には 0 から 7 までの行番号が，各列には 0 から 7 までの列番号が付けられている．
メッセンジャーゲームでは，Anna と Bruno が別の部屋に隔離された状態で Q 回のチャレンジが行われる．i 回目 (1 ≦ i ≦ Q) のチャレンジは次のように進行する．

1. Anna は司会のビ太郎から，3 つの整数 Xi , Yi , Ni (0 ≦ Xi ≦ 7，0 ≦ Yi ≦ 7，1 ≦ Ni ≦ 43) および ‘A’ と‘B’ からなる Ni 文字の文字列 S i が書かれたカードと，すべてのマスが白で塗られた 8 行 8 列のマス目を受け取る．

2. Anna は，行番号が Xi でなく列番号が Yi でない 49 個のマスについて，各マスを青か赤で塗る．
3. Anna はマス目を司会のビ太郎に渡す．
4. ビ太郎は，行番号が Xi または列番号が Yi である 15 個のマスについて，各マスを青か赤で塗る．この操作は Anna や Bruno から見えない場所で行われる．

5. Bruno は司会のビ太郎から，整数 Ni のみが書かれたカードとマス目を受け取る．
6. Bruno はある文字列を紙に書く．書いた文字列が S i と一致していれば，Anna と Bruno の勝利となる．
チャレンジの進行については，以下の図も参照せよ．

①カードとマス目を渡す②個のマスを塗る

ビ太郎④個のマスを塗る③マス目を渡す⑥文字列を紙に書く⑤カードとマス目を渡す

Anna と Bruno が「メッセンジャーゲーム」で勝利するための戦略を実装せよ．なお，この課題の採点方法については，採点基準の項を参照すること．

最後の戦い– 1 / 7

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle

実装の詳細
あなたは 2 つのファイルを提出しなければならない．

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

• void Anna(int X, int Y, int N, std::string S)
この関数は合計 Q 回呼び出される．i 回目 (1 ≦ i ≦ Q) の呼び出しは，ゲームにおける i 回目のチャレンジの手順 1.，手順 2.，手順 3. に相当する．

◦ 引数 X は，i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた整数 Xi である．
◦ 引数 Y は，i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた整数 Yi である．
◦ 引数 N は，i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた整数 Ni である．
◦ 引数 S は，i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた文字列 S i である．
関数 Anna の 1 回の呼び出しについて，以下の関数を，行番号が Xi でなく列番号が Yi でない 49 個のマスそれぞれについて 1 回ずつ，合計 49 回呼び出さなければならない．

⋆ void Paint(int a, int b, int c)⋄ 引数 a, b は，行番号が a で列番号が b のマスに色を塗ることを表す．ここで，0 ≦ a ≦ 7,0 ≦ b ≦ 7，a , X，b , Y を満たさなければならない．これが満たされない場合，不正解 [1]と判定される．

⋄ 引数 c は，c = 0 のとき青，c = 1 のとき赤で塗ることを表す．ここで，0 ≦ c ≦ 1 を満たさなければならない．これが満たされない場合，不正解 [2] と判定される．

⋄ 関数 Paint を同じ (a, b) で 2 回呼び出した場合，不正解 [3] と判定される．
⋄ 関数 Anna の実行の終了時に関数 Paint の呼び出し回数が 49 回でなかった場合，不正解[4] と判定される．

最後の戦い– 2 / 7

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle
2 つ目のファイルは Bruno.cpp という名前である．このファイルは Bruno の戦略を実装したファイルであり，以下の関数を実装していなければならない．また，#include プリプロセッサ指令によって Bruno.hを読み込むこと．

• std::string Bruno(int N, std::vector<std::vector<int>> T)
この関数は Anna がマス目を塗り終わるたびに 1 回，合計で Q 回呼び出される．i 回目 (1 ≦ i ≦ Q)の呼び出しは，ゲームにおける i 回目のチャレンジの手順 5.，手順 6. に相当する．

◦ 引数 N は，i 回目のチャレンジの手順 5. で Bruno が受け取るカードに書かれた整数 Ni である．
◦ 引数 T は，i 回目のチャレンジの手順 5. で Bruno が受け取るマス目の各マスの色を表す 8 × 8 の2 次元配列である．行番号が a (0 ≦ a ≦ 7) で列番号が b (0 ≦ b ≦ 7) のマスの色は，T[a][b] = 0であれば青，T[a][b] = 1 であれば赤である．

◦ 戻り値は，Bruno が紙に書く文字列である．
◦ 戻り値が 44 文字以上の文字列である場合，不正解 [5] と判定される．
◦ 戻り値に ‘A’ と ‘B’ 以外の文字が含まれている場合，不正解 [6] と判定される．

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

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

最後の戦い– 3 / 7

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle

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

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

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

Q
X1 Y1 N1 S 1
X2 Y2 N2 S 2..
.
XQ YQ NQ S Q

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

• 正解の場合，L∗ の値が “Accepted: 28” のように出力される．L∗ の値については採点基準の項を参照せよ．

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

最後の戦い– 4 / 7

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle
採点プログラムのサンプルにおいては，それぞれのチャレンジでビ太郎が各マスを塗る色が，実行ごとに結果が変わらない疑似乱数を用いて無作為に選ばれる．シードの値を変更したい場合は，./grader 2023のように 1 個目の引数に整数値を与えて実行せよ．

制約• 1 ≦ Q ≦ 20 000．
• 0 ≦ Xi ≦ 7 (1 ≦ i ≦ Q)．
• 0 ≦ Yi ≦ 7 (1 ≦ i ≦ Q)．
• 1 ≦ Ni ≦ 43 (1 ≦ i ≦ Q)．
• Q, Xi , Yi , Ni は整数である．
• S i (1 ≦ i ≦ Q) は ‘A’ と ‘B’ からなる Ni 文字の文字列である．

採点基準
この課題のテストケースの中で，1 つでも不正解 [1] 〜 [6]（実装の詳細を参照）と判定されたものや，実行時エラー（実行時間制限超過，メモリ制限違反，異常終了など）と判定されたものがあった場合，他のテストケースでどのチャレンジに勝利したかにかかわらず無条件で 0 点となる．
そうでない場合，この課題のすべてのテストケースに対する以下の値の最小値を L∗ とするとき，下表のように得点が与えられる．

• Ni ≦ L を満たすすべてのチャレンジについて勝利したような最大の整数 L．ただし，テストケース内のすべてのチャレンジに勝利した場合は L = 43 とする．

L∗0

1

2

34567891011121314

得点

058101113141618

192122242627L∗

15161718

1920212223242526

2728

29

得点

2930

32

3435

37

38

40424345

4648

5051

L∗

30

313233

3435

36

37

38

39

40

41

42

43

得点

53

54

56

57

5960

62

65

68

71

747784100

最後の戦い– 5 / 7

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle

やりとりの例
採点プログラムのサンプルが読み込む入力の例と，それに対応する関数の呼び出しの例を以下に示す．ただし，関数 Bruno の呼び出しにおける引数 T は省略されている．
入力例 1関数の呼び出しの例

Anna の呼び出し
2

Anna(0, 0, 1, "B")0 0 1 B

Paint(1, 1, 0)

5 7 8 AAAABBBBPaint(1, 2, 1)...

Bruno の呼び出し

Bruno の戻り値

Paint(7, 7, 1)
Bruno(1, ...)
"B"
Anna(5, 7, 8, "AAAABBBB")
Paint(0, 0, 1)
Paint(0, 1, 1)...
Paint(7, 6, 0)
Bruno(8, ...)"AAAABBBB"
この入力例は Q (= 2) 回のチャレンジからなる．

• 1 回目のチャレンジでは X1 = 0，Y1 = 0，N1 = 1，S 1 = “B” であるため，Anna は行番号が 0 でなく列番号が 0 でない 49 個のマスに色を塗らなければならない．

• 2 回目のチャレンジでは X2 = 5，Y2 = 7，N2 = 8，S 2 = “AAAABBBB” であるため，Anna は行番号が5 でなく列番号が 7 でない 49 個のマスに色を塗らなければならない．
たとえば，1 回目のチャレンジで Paint(0, 2, 1) を呼び出した場合，行番号が 0 のマスを指定しているため 不正解 [1] となることに注意せよ．

最後の戦い– 6 / 7

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 4 – The Last Battle
また，採点プログラムのサンプルが読み込む入力のもう 1 つの例を以下に示す．
入力例 230
3 1 1 A1 4 1 A6 6 2 AA1 1 2 BB3 1 3 BAB
7 4 3 AAB
6 4 4 BAAB6 7 4 BABA
3 3 5 BABBA
1 5 5 ABBBA
4 3 6 ABBBBB
2 1 6 ABAAAA
6 0 7 AAABABA
6 6 7 BBABBAA
0 4 8 AABAABAB
2 1 8 AABBBBBA
2 0 9 BABABBAAA
1 5 9 BBAAABABB
6 7 10 BAAABAAABB
1 7 10 BBBBBBBABA
2 6 12 AABAABABABAB
3 4 15 BBAABAAAABABAAB
5 6 18 BAAAABBABABBBABBAB
7 0 22 BABBAABAAABBABBBBBBABA
2 0 26 AAAABBABBAAAAABABABBAABAAA
0 7 30 AAABBBAAABAABBBBAABBAAABBBABBB
2 7 34 BABAABBAABABBABAABBABBABAABBBBABBB
2 5 38 BBBBAABAABAABABABBBBBAAABBABAAABAAABBB
5 2 41 AABABBAAABBABAAAABBABABBAAAAAABBABBABBABA
1 0 43 AABBABBBBABABBBABBBBAAAAAABABAAABBBAABBAAAB

最後の戦い– 7 / 7