J - 最後の戦い (The Last Battle) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

Submission on AtCoder

Distributed Files

Your program must include Anna.h and Bruno.h, and implement all functions in one file. Do NOT share global variables.

You can submit only C++ source code.

Score: 100 points

Problem Statement

JOICup is a popular television variety program held by JOI broadcast station. Now JOICup becomes the final round. In the final round, the “messenger game” will be played. Only one team which passed the first round will play the game. The team consists of two players, Anna and Bruno.

In the messenger game, the players send information using a grid of 8 \times 8 cells. The rows of the grid are numbered from 0 to 7, and the columns of the grid are numbered from 0 to 7.

In the messenger game, Anna and Bruno are isolated in different rooms. They will play Q challenges. The i-th challenge (1 \le i \le Q) proceeds as follows.

  1. Bitaro, the moderator of the game, gives a card and a grid of 8 \times 8 cells to Anna. On the card, three integers X_i, Y_i, N_i (0 \le X_i \le 7, 0 \le Y_i \le 7, 1 \le N_i \le 43) and a string S_i of length N_i consisting of A and B are written. All of the cells in the grid are white.
  2. Anna paints each of the 49 cells whose row is different from X_i and column is different from Y_i. The color of each cell is either blue or red.
  3. Anna gives the grid of cells to Bitaro, the moderator of the game.
  4. Bitaro paints each of the 15 cells whose row is equal to X_i or column is equal to Y_i. The color of each cell is either blue or red. This process is done in a room which is not seen by Anna nor Bruno.
  5. Bitaro, the moderator of the game, gives a card and the grid of cells to Bruno. Only the integer N_i is written on the card.
  6. Bruno writes a string on a paper. If it coincides with S_i, Anna and Bruno win the game.

The challenges proceed as in the following figure.

The challenge: Anna, Bitaro and Bruno exchange cards and the grid of cells

Write programs which implement the strategies of Anna and Bruno to win the “messenger game.” For the grading of this task, see Grading.


Implementation Details

You need to submit two files.

The first file is Anna.cpp. It should implement Anna's strategy. It should implement the following functions. The program should include Anna.h using the preprocessing directive #include.

  • void Anna(int X, int Y, int N, std::string S)

    This function is called Q times. The i-th call (1 \le i \le Q) corresponds to the procedures 1., 2., 3. of the i-th challenge of the game.

    • The parameter X is the integer X_i written on the card given to Anna in the procedure 1. of the i-th challenge.
    • The parameter Y is the integer Y_i written on the card given to Anna in the procedure 1. of the i-th challenge.
    • The parameter N is the integer N_i written on the card given to Anna in the procedure 1. of the i-th challenge.
    • The parameter S is the string S_i written on the card given to Anna in the procedure 1. of the i-th challenge.

    For each function call to Anna, the following function should be called 49 times in total. The following function should be called once for each of the 49 cells whose row is different from X_i and column is different from Y_i.

    • void Paint(int a, int b, int c)

      • The parameters a, b mean Anna paints the cell whose row is a and column is b. Here the conditions 0 \le a \le 7, 0 \le b \le 7, a \neq X, b \neq Y should be satisfied. If this condition is not satisfied, your program is judged as Wrong Answer [1].
      • The parameter c means the color painted by Anna is blue if c = 0, and red if c = 1. Here, 0 \le c \le 1 should be satisfied. If this condition is not satisfied, your program is judged as Wrong Answer [2].
      • If the function Paint is called with the same parameters (a, b) more than once, your program is judged as Wrong Answer [3].
      • When the function Anna terminates, if the number of function calls to Paint is different from 49, your program is judged as Wrong Answer [4].

The second file is Bruno.cpp. It should implement Bruno's strategy. It should implement the following function. The program should include Bruno.h using the preprocessing directive #include.

  • std::string Bruno(int N, std::vector<std::vector<int>> T)

    This function is called every time when Anna finishes painting the grid. This function is called Q times in total. The i-th call (1 \le i \le Q) corresponds to the procedures 5., 6. of the i-th challenge of the game.

    • The parameter N is the integer N_i written on the card given to Bruno in the procedure 5. of the i-th challenge.
    • The parameter T is a two-dimensional array of size 8 \times 8 corresponding to the grid of cells given to Bruno in the procedure 5. of the i-th challenge. The color of the cell whose row is a (0 \le a \le 7) and column is b (0 \le b \le 7) is blue if T[a][b] = 0, and red if T[a][b] = 1.
    • The return value is the string written by Bruno on a paper.
    • If the return value is a string of length 44 or more, your program is judged as Wrong Answer [5].
    • Each character of the return value should be either A or B. If this condition is not satisfied, your program is judged as Wrong Answer [6].

Important Notices

  • Your program can implement other functions for internal use, or use global variables. Submitted files will be compiled with the grader, and become a single executable file. All global variables and internal functions should be declared in an unnamed namespace to avoid confliction with other files. When it is graded, it will be executed as two processes of Anna and Bruno. The process of Anna and the process of Bruno cannot share global variables.
  • Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.

Compilation and Test Run

You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.

The sample grader is the file grader.cpp. In order to test your program, put grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h in the same directory, and run the following command to compile your programs. Instead, you may run compile.sh contained in the archive file.

g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

When the compilation succeeds, the executable file grader is generated.

Note that the actual grader is different from the sample grader. In particular, Bitaro does not necessarily choose the colors to paint the cells randomly. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.

Input for the Sample Grader

The sample grader reads the following data from the standard input.

Q
X_1 Y_1 N_1 S_1
X_2 Y_2 N_2 S_2
\vdots
X_Q Y_Q N_Q S_Q

Output of the Sample Grader

The sample grader outputs the following information to the standard output (quotes for clarity).

  • If your program is judged as correct, it writes the value of L^{\ast} as Accepted: 28. For the value of L^{\ast}, see Grading.
  • If your program is judged as any type of Wrong Answer, the sample grader writes its type as Wrong Answer [1].

If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them.

In the sample grader, the colors chosen by Bitaro for challenges are randomly determined by pseudorandom numbers whose results do not change for different executions. In order to change the seed of pseudorandom numbers, run the sample grader with the first integer argument as follows.

./grader 2023

Constraints

  • 1 \le Q \le 20\,000.
  • 0 \le X_i \le 7 (1 \le i \le Q).
  • 0 \le Y_i \le 7 (1 \le i \le Q).
  • 1 \le N_i \le 43 (1 \le i \le Q).
  • Q, X_i, Y_i, N_i are integers.
  • S_i (1 \le i \le Q) is a string of length N_i consisting of A and B.

Grading

If your program is judged as any type of Wrong Answer [1]–[6] (see Implementation Details) or any type of runtime errors (TLE (Time Limit Exceeded), MLE (Memory Limit Exceeded), Abnormal End, etc.) in any of the test cases, your score is 0 point regardless of whether your program wins challenges in other test cases.

Otherwise, let L^{\ast} be the minimum of the following values for all test cases of this task. Your score is calculated as in the following table.

  • The maximum value of L such that Anna and Bruno win all the challenges satisfying N_i \le L. However, if they win all the challenges in the test cases, we set L = 43.
L^{\ast} 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
Score 0 5 8 10 11 13 14 16 18 19 21 22 24 26 27 29 30 32 34 35 37 38 40 42 43 45 46 48 50 51 53 54 56 57 59 60 62 65 68 71 74 77 84 100

Sample Communication

Here is a sample input for the sample grader and corresponding function calls. The parameters T for the function calls to Bruno are omitted.

Sample Input 1

2
0 0 1 B
5 7 8 AAAABBBB

Sample Function Calls

Function call to Anna Function call to Bruno Return value of Bruno
Anna(0, 0, 1, "B")
Paint(1, 1, 0)
Paint(1, 2, 1)
\ldots
Paint(7, 7, 1)
Bruno(1, ...)
"B"
Anna(5, 7, 8, "AAAABBBB")
Paint(0, 0, 1)
Paint(0, 1, 1)
\ldots
Paint(7, 6, 0)
Bruno(8, ...)
"AAAABBBB"

In this sample input, there are Q (= 2) challenges.

  • In the first challenge, we have X_1 = 0, Y_1 = 0, N_1 = 1, S_1 = {}"B". Anna paints the 49 cells whose row is different from 0 and column is different from 0.
  • In the second challenge, we have X_2 = 5, Y_2 = 7, N_2 = 8, S_2 = {}"AAAABBBB". Anna paints the 49 cells whose row is different from 5 and column is different from 7.

For example, if your program calls Paint(0, 2, 1) in the first challenge, it is judged as Wrong Answer [1] because it designates a cell whose row is 0.

Here is another sample input for the sample grader.

Sample Input 2

30
3 1 1 A
1 4 1 A
6 6 2 AA
1 1 2 BB
3 1 3 BAB
7 4 3 AAB
6 4 4 BAAB
6 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

AtCoder での提出方法

配布ファイル

Anna.h,Bruno.h を include し,すべての関数を 1 つのファイル内で実装してください.グローバル変数を両者の間で共有しないでください.

このジャッジは C++ 以外に対応していません.

配点 : 100 点

問題文

JOI 放送局が開催する人気バラエティ番組 JOICup は,いよいよ最終ラウンドを迎えることになった.最終ラウンドでは「メッセンジャーゲーム」が行われ,予選を勝ち抜いた Anna と Bruno の 2 人からなるチームのみが出場する.

メッセンジャーゲームは,8 行 8 列のマス目を介して情報を伝えるゲームである.マス目の各行には 0 から 7 までの行番号が,各列には 0 から 7 までの列番号が付けられている.

メッセンジャーゲームでは,Anna と Bruno が別の部屋に隔離された状態で Q 回のチャレンジが行われる.i 回目 (1 \leqq i \leqq Q) のチャレンジは次のように進行する.

  1. Anna は司会のビ太郎から,3 つの整数 X_i, Y_i, N_i (0 \leqq X_i \leqq 7,0 \leqq Y_i \leqq 7,1 \leqq N_i \leqq 43) および A と B からなる N_i 文字の文字列 S_i が書かれたカードと,すべてのマスが白で塗られた 8 行 8 列のマス目を受け取る.
  2. Anna は,行番号が X_i でなく列番号が Y_i でない 49 個のマスについて,各マスを青か赤で塗る.
  3. Anna はマス目を司会のビ太郎に渡す.
  4. ビ太郎は,行番号が X_i または列番号が Y_i である 15 個のマスについて,各マスを青か赤で塗る.この操作は Anna や Bruno から見えない場所で行われる.
  5. Bruno は司会のビ太郎から,整数 N_i のみが書かれたカードとマス目を受け取る.
  6. Bruno はある文字列を紙に書く.書いた文字列が S_i と一致していれば,Anna と Bruno の勝利となる.

チャレンジの進行については,以下の図も参照せよ.

Anna,ビ太郎,Bruno の間でカードとマス目を渡すチャレンジの進行

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


実装の詳細

あなたは 2 つのファイルを提出しなければならない.

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

  • void Anna(int X, int Y, int N, std::string S)

    この関数は合計 Q 回呼び出される.i 回目 (1 \leqq i \leqq Q) の呼び出しは,ゲームにおける i 回目のチャレンジの手順 1.,手順 2.,手順 3. に相当する.

    • 引数 X は,i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた整数 X_i である.
    • 引数 Y は,i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた整数 Y_i である.
    • 引数 N は,i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた整数 N_i である.
    • 引数 S は,i 回目のチャレンジの手順 1. で Anna が受け取るカードに書かれた文字列 S_i である.

    関数 Anna の 1 回の呼び出しについて,以下の関数を,行番号が X_i でなく列番号が Y_i でない 49 個のマスそれぞれについて 1 回ずつ,合計 49 回呼び出さなければならない.

    • void Paint(int a, int b, int c)

      • 引数 a, b は,行番号が a で列番号が b のマスに色を塗ることを表す.ここで,0 \leqq a \leqq 7,0 \leqq b \leqq 7,a \neq X,b \neq Y を満たさなければならない.これが満たされない場合,不正解 [1] と判定される.
      • 引数 c は,c = 0 のとき青,c = 1 のとき赤で塗ることを表す.ここで,0 \leqq c \leqq 1 を満たさなければならない.これが満たされない場合,不正解 [2] と判定される.
      • 関数 Paint を同じ (a, b) で 2 回呼び出した場合,不正解 [3] と判定される.
      • 関数 Anna の実行の終了時に関数 Paint の呼び出し回数が 49 回でなかった場合,不正解 [4] と判定される.

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

  • std::string Bruno(int N, std::vector<std::vector<int>> T)

    この関数は Anna がマス目を塗り終わるたびに 1 回,合計で Q 回呼び出される.i 回目 (1 \leqq i \leqq Q) の呼び出しは,ゲームにおける i 回目のチャレンジの手順 5.,手順 6. に相当する.

    • 引数 N は,i 回目のチャレンジの手順 5. で Bruno が受け取るカードに書かれた整数 N_i である.
    • 引数 T は,i 回目のチャレンジの手順 5. で Bruno が受け取るマス目の各マスの色を表す 8 \times 8 の 2 次元配列である.行番号が a (0 \leqq a \leqq 7) で列番号が b (0 \leqq b \leqq 7) のマスの色は,T[a][b] = 0 であれば青,T[a][b] = 1 であれば赤である.
    • 戻り値は,Bruno が紙に書く文字列である.
    • 戻り値が 44 文字以上の文字列である場合,不正解 [5] と判定される.
    • 戻り値に A と B 以外の文字が含まれている場合,不正解 [6] と判定される.

重要な注意

  • 内部での使用のために他の関数を実装したり,グローバル変数を宣言するのは自由である.ただし,提出された 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++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

コンパイルが成功すれば,grader という実行ファイルが生成される.

実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.特に,ビ太郎が各マスを塗る色が無作為に選ばれるとは限らない.採点プログラムのサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.

採点プログラムのサンプルの入力

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

Q
X_1 Y_1 N_1 S_1
X_2 Y_2 N_2 S_2
\vdots
X_Q Y_Q N_Q S_Q

採点プログラムのサンプルの出力

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

  • 正解の場合,L^{\ast} の値が Accepted: 28 のように出力される.L^{\ast} の値については採点基準の項を参照せよ.
  • 不正解の場合,不正解の種類が Wrong Answer [1] のように出力される.

実行するプログラムが複数の不正解の条件を満たした場合,表示される不正解の種類はそれらのうち 1 つのみである.

採点プログラムのサンプルにおいては,それぞれのチャレンジでビ太郎が各マスを塗る色が,実行ごとに結果が変わらない疑似乱数を用いて無作為に選ばれる.シードの値を変更したい場合は,

./grader 2023

のように 1 個目の引数に整数値を与えて実行せよ.


制約

  • 1 \leqq Q \leqq 20\,000.
  • 0 \leqq X_i \leqq 7 (1 \leqq i \leqq Q).
  • 0 \leqq Y_i \leqq 7 (1 \leqq i \leqq Q).
  • 1 \leqq N_i \leqq 43 (1 \leqq i \leqq Q).
  • Q, X_i, Y_i, N_i は整数である.
  • S_i (1 \leqq i \leqq Q) は A と B からなる N_i 文字の文字列である.

採点基準

この課題のテストケースの中で,1 つでも不正解 [1] 〜 [6](実装の詳細を参照)と判定されたものや,実行時エラー(実行時間制限超過,メモリ制限違反,異常終了など)と判定されたものがあった場合,他のテストケースでどのチャレンジに勝利したかにかかわらず無条件で 0 点となる.

そうでない場合,この課題のすべてのテストケースに対する以下の値の最小値を L^{\ast} とするとき,下表のように得点が与えられる.

  • N_i \leqq L を満たすすべてのチャレンジについて勝利したような最大の整数 L.ただし,テストケース内のすべてのチャレンジに勝利した場合は L = 43 とする.
L^{\ast} 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
得点 0 5 8 10 11 13 14 16 18 19 21 22 24 26 27 29 30 32 34 35 37 38 40 42 43 45 46 48 50 51 53 54 56 57 59 60 62 65 68 71 74 77 84 100

やりとりの例

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

入力例 1

2
0 0 1 B
5 7 8 AAAABBBB

関数の呼び出しの例

Anna の呼び出し Bruno の呼び出し Bruno の戻り値
Anna(0, 0, 1, "B")
Paint(1, 1, 0)
Paint(1, 2, 1)
\ldots
Paint(7, 7, 1)
Bruno(1, ...)
"B"
Anna(5, 7, 8, "AAAABBBB")
Paint(0, 0, 1)
Paint(0, 1, 1)
\ldots
Paint(7, 6, 0)
Bruno(8, ...)
"AAAABBBB"

この入力例は Q (= 2) 回のチャレンジからなる.

  • 1 回目のチャレンジでは X_1 = 0,Y_1 = 0,N_1 = 1,S_1 = {}"B" であるため,Anna は行番号が 0 でなく列番号が 0 でない 49 個のマスに色を塗らなければならない.
  • 2 回目のチャレンジでは X_2 = 5,Y_2 = 7,N_2 = 8,S_2 = {}"AAAABBBB" であるため,Anna は行番号が 5 でなく列番号が 7 でない 49 個のマスに色を塗らなければならない.

たとえば,1 回目のチャレンジで Paint(0, 2, 1) を呼び出した場合,行番号が 0 のマスを指定しているため不正解 [1] となることに注意せよ.

また,採点プログラムのサンプルが読み込む入力のもう 1 つの例を以下に示す.

入力例 2

30
3 1 1 A
1 4 1 A
6 6 2 AA
1 1 2 BB
3 1 3 BAB
7 4 3 AAB
6 4 4 BAAB
6 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

Source Name

JOI 2022/2023 春季トレーニング Contest Day4 問題1