prison
IOI 2022 Day 1 Tasks
Japanese (JPN)

囚⼈たちの挑戦ある監獄では，500 ⼈の囚⼈を収容している．ある⽇，看守は囚⼈たちに釈放の機会を与えることにした．看守は，ある部屋にお⾦の⼊った 2 つの鞄，鞄 A と鞄 B を⽤意した．それぞれの鞄には 1 枚以上
N 枚以下の硬貨が⼊っており，2 つの鞄に⼊っている硬貨の枚数は相異なる．より少ない枚数の硬貨を含む鞄を特定することが，看守が囚⼈に与えた課題である．
鞄が⽤意された部屋には，1 つのホワイトボードがある．このホワイトボードには，常にちょうど 1 つの数が書かれていなければいけない．最初にホワイトボードに書かれている数は 0 である．
看守は，囚⼈たちに 1 ⼈ずつ順に部屋に⼊るよう指⽰する．各囚⼈が部屋に⼊るとき，それまでに誰が部屋に⼊ったのか，また何⼈の囚⼈が部屋に⼊ったのかを知ることはできないが，部屋のホワイトボー
ドに書かれている数を⾒ることはできる．その後，囚⼈は鞄 A と鞄 B のいずれかを選び，選んだ鞄の中⾝を調べ，何枚の硬貨が⼊っているかを知ることができる．そして，囚⼈は以下の 2 つの⾏動のうちいずれかを⾏う．
ホワイトボードに書かれている数をある⾮負整数に書き換え，部屋を出る． 必ずしも異なる数に書き換える必要はない．まだ部屋に⼊っていない囚⼈がいる場合，この後も囚⼈たちの挑戦は続
く．
⼀⽅の鞄が，硬貨の枚数が少ない鞄であると宣⾔する．この⾏動により，囚⼈たちの挑戦は終了
する．
看守が，⼀度部屋に⼊った囚⼈をもう⼀度部屋に⼊れることはない．
硬貨の枚数が少ない鞄を正しく特定することができた場合，囚⼈たちの挑戦は成功となる．硬貨の枚数が少ない鞄を正しく特定できなかった場合，もしくは，500 ⼈全員が部屋に⼊り，誰も硬貨の枚数が少ない鞄を宣⾔しなかった場合，囚⼈たちの挑戦は失敗となる．
挑戦を始める前に，囚⼈たちは監獄の広間に集まり，3 段階からなる共通の戦略を定めることにした．
まず，ある⾮負整数 x を定め，x より⼤きい数をホワイトボードに書かないこととする．
0 ≦ i ≦ x なる各整数 i について，ホワイトボードに書かれている数が i の場合に，どちらの鞄を調べるかを定める．
調べた鞄に⼊っているコインの枚数に応じて，その後囚⼈が取るべき⾏動を定める．具体的には，ホワイトボードに書かれている数 i と調べた鞄に⼊っているコインの枚数 j の組としてありうるすべての組に対して，以下のいずれかのようにして，⾏動を定める．
ホワイトボードに書く 0 以上 x 以下の整数を定める．
硬貨の枚数が少ないと宣⾔する鞄を定める．
この挑戦に成功した場合，看守は x ⽇の懲役の後に囚⼈たちを解放するつもりだ．
prison (1 of 4)

あなたの課題は，それぞれの鞄に⼊っている硬貨の枚数にかかわらず，必ず囚⼈たちが課題を成功させることができるような戦略を考案することである．x の値に応じて，あなたの解法の点数は変わる．(詳細は⼩課題の章を参照．)

実装の詳細

あなたは，次の関数を実装する必要がある．
int[][] devise_strategy(int N): それぞれの鞄に⼊っている硬貨の枚数の最⼤値
この関数は，整数からなる⻑さ N + 1 の配列を要素としてもつ配列 s を返さなければいけない．
この配列はあなたの戦略を表すものである． x の値は s の⻑さから 1 引いた値である．
0 ≦ i ≦ x なる各整数 i に対し，配列 s[i] は，部屋に⼊った際のホワイトボードに書かれている
数が i の場合に，囚⼈がどうすべきかを表す．
1. 鞄 A の中⾝を調べる場合，s[i][0] の値は 0 である．鞄 B の中⾝を調べる場合，s[i][0] の値
は 1 である．
2. 調べた鞄に⼊っている硬貨の枚数を j とする．このとき，囚⼈は以下の⾏動をとる．
s[i][j] の値が −1 のとき，鞄 A を硬貨の枚数が少ない鞄であると宣⾔する．
s[i][j] の値が −2 のとき，鞄 B を硬貨の枚数が少ない鞄であると宣⾔する．
s[i][j] の値が⾮負整数のとき，ホワイトボードの数を s[i][j] に書き換える．ただし，s[i][j] は x 以下でなければいけない．
この関数はちょうど 1 回呼び出される．
N

⼊出⼒例

次の呼び出しを考える:
devise_strategy(3)

部屋に⼊ったときにホワイトボードに書いてある整数を v とする．例えば，以下の戦略は正しい戦略の例となっている:v = 0 のとき (最初の囚⼈の場合も含む)，鞄 A を調べる．
硬貨の枚数が 1 枚のとき，鞄 A を硬貨の枚数が少ない鞄であると宣⾔する．
硬貨の枚数が 3 枚のとき，鞄 B を硬貨の枚数が少ない鞄であると宣⾔する．
硬貨の枚数が 2 枚のとき，ホワイトボードの数を (0 から) 1 に書き換える．
v = 1 のとき，鞄 B を調べる．
硬貨の枚数が 1 枚のとき，鞄 B を硬貨の枚数が少ない鞄であると宣⾔する．
硬貨の枚数が 3 枚のとき，鞄 A を硬貨の枚数が少ない鞄であると宣⾔する．
硬貨の枚数が 2 枚のとき，ホワイトボードの数を (1 から) 0 に書き換える．ただし，両⽅の鞄が 2 枚の硬貨を含むことはないため，この場合が⽣じることはない．
prison (2 of 4)

この戦略を報告するためには，関数は [[0, -1, 1, -2], [1, -2, 0, -1]] と返す必要がある．
戻り値の配列の⻑さは 2 であるので，この戻り値に対応する x の値は 2 − 1 = 1 である．

制約

2 ≦ N ≦ 5000

⼩課題

1. (5 点) N ≦ 500，x の値は 500 以下でなければいけない．
2. (5 点) N ≦ 500，x の値は 70 以下でなければいけない．
3. (90 点) x の値は 60 以下でなければいけない．
もしあるテストケースにおいて， devise_strategy の戻り値の配列が正しい戦略を表していない場
合，その⼩課題に対するあなたの解法の点数は 0 点となる．
⼩課題 3 には部分点がある．この⼩課題のすべてのテストケースに対する，x の値の最⼤値を m とする．この⼩課題の点数は次の表に基づいて計算される．
条件

点数

40 ≦ m ≦ 60

20

26 ≦ m ≦ 39

25 + 1.5 × (40 − m)

m = 2550m = 2455

m = 2362m = 2270m = 2180m ≦ 2090

採点プログラムのサンプル
採点プログラムのサンプルの⼊⼒形式は以下の通りである．
1 ⾏⽬: N2 + k (0 ≦ k) ⾏⽬: A[k] B[k]最後の⾏: −1
各⾏は，最初の⾏と最後の⾏を除いて，1 つのシナリオを表している．2 + k ⾏⽬に表されているシナリ
オを，シナリオ k と表すことにする．シナリオ k においては，鞄 A は A[k] 枚の硬貨を，鞄 B は B[k]枚の硬貨を含んでいる．
prison (3 of 4)

採点プログラムのサンプルはまず devise_strategy(N) を呼び出す．x の値は戻り値となる配列の⻑さから 1 引いた値である． devise_strategy の戻り値である配列が実装の詳細にある制約を満たしていないことを検知した場合，採点プログラムのサンプルは以下のいずれかのエラーメッセージを出⼒し，終了する．
s is an empty array: s が空配列である．(これが正しい戦略を表すことはない．)
s[i] contains incorrect length: 0 ≦ i ≦ x なる添え字 i に対して，s[i] の⻑さが N + 1
でない．
First element of s[i] is non-binary: 0 ≦ i ≦ x なる添え字 i に対して，s[i][0] の値が0 でも 1 でもない．
s[i][j] contains incorrect value: 0 ≦ i ≦ x, 1 ≦ j ≦ N なる添え字 i , j に対して，
s[i][j] の値が −2 以上 x 以下でない．
その他の場合，採点プログラムのサンプルは 2 つの出⼒を⾏う．
まず，採点プログラムのサンプルはあなたの戦略の結果を以下の形式で出⼒する．
1 + k (0 ≦ k) ⾏⽬: シナリオ k に対するあなたの戦略の結果を表す⽂字． ある囚⼈が鞄 A を硬貨の枚数が少ない鞄であると宣⾔したとき，出⼒は⽂字 A となる． ある囚⼈が鞄 B を硬貨の枚数が少ない鞄であると宣⾔したとき，出⼒は⽂字 B となる． どの囚⼈も硬貨の枚数が少ない鞄を宣⾔しなかったとき，出⼒は⽂字 X となる．
次に，採点プログラムのサンプルはカレントディレクトリの log.txt というファイルに以下の形式で書き込む．
1 + k (0 ≦ k) ⾏⽬: w[k][0] w[k][1] …
1 + k ⾏⽬の数列は，シナリオ k に対応しており，ホワイトボードに書かれた数を表す．具体的には，
w[k][l] は l + 1 番⽬に部屋に⼊った囚⼈が書いた数を表す．

prison (4 of 4)