Tricolor Lights 解説
ynymxiaolongbao

問題概要• AnnaとBrunoの二人が協力して、ディ太郎に勝ちたい• 長さ𝑁のボードがあり、Annaは各場所をR, G, B のいずれかの色で塗る• 各場所には一色だけ禁止色 𝑆𝑖 があり、その色では塗れない

RGGBRBBG

問題概要• Annaが整数𝐿を指定する• ディ太郎がボードの長さ𝐿の区間を切り取り、そこの色の並びをBrunoに伝える• Brunoはディ太郎が切り取った場所がどこかを答える

RGGBRBBG
長さ5→答え3

問題概要• Lは大きくした方が簡単、Nは小さい方が簡単• 小課題４まで：Lの上限は130固定で、Nが段々大きくなる• 小課題５：Nが大きい値で固定で、Lの上限が段々小さくなる

RGGBRBBG
長さ5→答え3

小課題１（𝑁 ≤ 131 = 𝐿 + 1）
• 𝑁 ≤ 130のとき、𝐿 = 𝑁に設定すれば答えはいつも1• 𝑁 = 131のとき、𝐿 = 130にすると、1~130なのか2~131なのか判定できれば良い• 思ったより難しい

小課題１（𝑁 ≤ 131 = 𝐿 + 1）
• 気持ち：一つの桁ではちゃんと情報を伝えられない• たとえば、「この桁がRだったらこういう意味」と決めておいたとしても、その桁をRにすることが禁止されてると、そうできない• →二つの桁を使って情報を伝える

小課題１（𝑁 ≤ 131 = 𝐿 + 1）
• 二つの桁を使って情報を伝える• 二つの桁が等しいか／異なるかR, G
禁止色を自由に決められる

B, B

等しい色にする場合

G, R異なる色にする場合

小課題１（𝑁 ≤ 131 = 𝐿 + 1）
• 等しくする場合：禁止されている色はR,G,Bのうち高々二種類→残りの色を選んで両方それで塗る• 異なるようにする場合：塗り方は2 × 2 = 4通りあるが、等しい色にする方法は3通りしかないので、少なくとも1通りでは異なる色になる（鳩ノ巣原理）

R, G
禁止色

B, B

等しい色にする場合

G, R異なる色にする場合

小課題１（𝑁 ≤ 131 = 𝐿 + 1）
• Anna（色を塗る人）は、1桁目と130桁目を同じ色に塗って、2桁目と131桁目を異なる色に塗る• Bruno（場所を当てる人）は、受け取った色の並びの左端と右端が同じ色かを見て、同じなら1、異なるなら2と答えれば良い小課題２（𝑁 ≤ 250 ~ 2𝐿）• 隣り合う二つが等しいか異なるかに注目• 値が同じことを0、異なることをXと書く• Anna（色を塗る人）：隣あう二つの違いが図のように並ぶようにする

X……X 0 X……X
128

128

小課題２（𝑁 ≤ 250 ~ 2𝐿）• まず0になる（色が等しい）二か所の色を決める• Xになる（色が異なる）場所は、0に近い方から順に、三色のう
ち隣の色・禁止色のどちらでもない色を選んで行く

X……X 0 X……X
128128

小課題２（𝑁 ≤ 250 ~ 2𝐿）• Bruno（場所を当てる人）：場所が1,2,…,129のとき、0がある
位置は129,128,…,1 になっているので、130-「0がある位置」
で場所が分かる

X……X 0 X……X
128128

小課題３（𝑁 ≤ 380 ~ 3𝐿）• Anna：隣あう二つの違いが図のように並ぶようにする• ?はAnna制御できずよく分からなくなった値とする• ?は0かXのどちらかとしてBrunoに伝えられる

X……X ? 0 X……X ? 0 X ? 0 X……X
126122125

小課題３（𝑁 ≤ 380 ~ 3𝐿）• Bruno：0が二回以上出てくるので、その距離を見てどこの0か判定• 値が0のとき、Annaが0と?のどちらで送ったか分からない• 本当の0の次は必ずXで、?の次は必ず0なので、分かる

X……X ? 0 X……X ? 0 X ? 0 X……X
126122125

2小課題４（𝑁 ≤ 7000 ~ 𝐿 /2）• 0の間の距離がL-7, 3, L-8, 4, L-9,…,L/2 になるようにする• どの長さLの区間にも0が2つ以上出てくるので、その距離を見るとどこの0か分かる…X……X ? 0 X……X ? 0 X…X ? 0 X……X…
20

101

21100

5小課題５（𝑁 ≤ 5 × 10 , 𝐿 = 28~130）• 𝐿 = 𝑙𝑜𝑔 𝑁 × 定数 くらいにしないといけない• 2進数とか3進数を使う• 大ブロックに分ける解法
L = 130 -> 60 -> 40 -> 33 -> 31 / 32（天才）• 小ブロックに分ける解法（de Bruijn 列）
L = 51(乱択）-> 34 -> 31 -> 29 -> 28

大ブロックに分ける解法
L = 130 -> 60 -> 40 -> 33 -> 31 / 32(天才)𝐿 = 130 （40点）• * を、Annaが自由に決めた0かXの値とする• 図の長さ59のブロックを繰り返す• * * …* の部分でブロックの番号を2進数14桁で書く? *…… ? * ? 0 X………X
14×229

𝐿 = 130 （40点）• 0の後にXが29個並ぶのはブロックの右端の部分だけ→どこからブロックが始まるか分かる→そこに書いてある２進数を見て、そのブロックの番号を求める→どこを切り出したのか分かる? *…… ? * ? 0 X………X
14×2

29

𝐿 = 60 （50点）• ブロックが完全に含まれている必要はない• 困るのは、ブロックが途中で切れて、図のようになるとき• 二進数が完全には読めない? *… ? * ? 0 X………X ? *… ? *𝐿 = 60 （50点）• ブロックの番号𝑥の下の𝑘桁と𝑥 + 1の上14 − 𝑘桁が分かる• 𝑥の下𝑘桁が1…1なら、𝑥の上14−𝑘桁は、𝑥 + 1の上14 − 𝑘桁 -1• そうでない場合、 𝑥の上14−𝑘桁は𝑥 + 1の上14 − 𝑘桁と同じ→ブロックの番号が分かる? *… ? * ? 0 X………X ? *… ? *𝐿 = 40 （58点）• 2進数ではなく３進数が使える• R, G, Bを0, 1, 2とみなして、その差（mod 3）を自由に決められる? *…… ? * ? 0 X………X
9×2

19𝐿 = 40 （58点）• * を0,1,2のAnnaが自由に決められる値とする• 図の長さ39のブロックを繰り返す• * * …* の部分でブロックの番号を3進数9桁で書く? *…… ? * ? 0 X………X
9×219

𝐿 = 33 （80点）• 前の解法は、右端以外の所で1が沢山連続しなければ良い• * * …* の部分でブロックの番号を3進数9桁で書く? *…… ? * ? 0 X………X
9×2

19𝐿 = 33 （80点）• 図のように、間に3つごとに0を挟めばよい（9桁なので、ちょうど３つずつに分かれる）• 右端で必要なX…Xの長さが減る? * … ? 0 ? * … ? 0 ? * …? 0 X……X
3×2

3×2

3×2

8

𝐿 = 31 （88点）• 前の解法では、3進数9桁の間に0を2つ挟んで、* の部分でXが4連続しないようにした• 3進数10桁であってXが4連続しないものを選ぶと、減る𝐿 = 32 （天才）（84点）• 3進数が書けるが、あえて1と2だけを使って2進数14桁を書く• * を、Annaが自由に決められる1か2の値とする• 右端が工夫されている? *……… ? * ? X 0
14×2

𝐿 = 32 （天才）（84点）• 0になりうるのは 0 と ? の場所• 0が一つしかない場合：そこが右端の0• 0が二つ以上ある場合：右端の0だけ、次の0との距離が奇数→右端の0の位置が分かる? *……… ? * ? X 0
14×2

小ブロックに分ける解法（de Bruijn 列）
L = 34 -> 31 -> 29 -> 28

de Bruijn 列• k進数N桁のde Bruijn 列…k進数n桁の文字列は𝑘 𝑁 通りあるが、それらがちょうど一回ずつ長さNの文字列として現れるような列• これは巡回させることができる• 以下のグラフの一筆書きに対応する• 頂点：k進数N-1桁の各文字列• 辺：k進数N桁の各文字列に対応し、その前N-1桁から後ろN-1桁の頂点へ有向辺

de Bruijn 列• 有向グラフが一筆書きできる条件…連結&すべての頂点で入次数と出次数が等しい• 前頁のグラフはその条件を満たす→de Bruijn 列は存在

de Bruijn 列の拡張
• 逆に、グラフがその条件を保っていれば、de Bruijn 列のようなものが作れる• k進数N桁の文字列のうち、いくつかを取り除いても、それらがちょうど一回ずつ出てくるような列が作れることがある• 例えば、「3進数11桁の文字列のうち、0が一回以上出てくるもの」についても、それらがちょうど一回ずつ出てくるような列が作れる（グラフが、連結で各頂点の入次数と出次数が等しいため）• これを拡張 de Bruijn 列と呼ぶことにする

𝐿 = 34 （76点）• ? * X を1ブロックとしてこれを繰り返す• * の部分には、「3進数11桁のうち一回以上0が出てくるもの」からなる拡張de Bruijn 列を書く?*X?*X:?*X

𝐿 = 34 （76点）• 11ブロック分見て、mod 3ごとに、一回以上0が出てくるか見る• 結果がxoxのとき、* になっている余りはoの所• 結果がooxのとき、* になっている余りは右側のoの所• Brunoは拡張de Bruijn列から整数を復元すれば良い

?*X
?*X
:?*X

𝐿 = 31 （88点）• ? * ? * X を1ブロックとしてこれを繰り返す• * の部分二つには、• 「3進数6桁のうち一回以上0が出てくるもの（665個）」• 「そこから0…0を除いたもの（664個）」• からなる拡張de Bruijn 列をそれぞれ繰り返し書く• 6ブロック分見て、mod 5ごとに、一回以上0が出てくるか見る• 結果がNoになる余りは ?とXの所だけ→前のL=32解法と同様に、次の場所との距離が奇数な所がX

𝐿 = 31 （88点）• 周期が665, 664 のde Bruijn 列を合わせると、周期はLCM(665,664)になる• Brunoは得た二つの整数から中国剰余定理を使って場所を復元• 5×LCM(665,664)>=500000で、通る𝐿 = 29 （96点）• ? * ? * ? * X を1ブロックとしてこれを繰り返す• * の部分三つには、• 「3進数4桁のうち一回以上0が出てくるもの（65個）」• 「そこから0000を除いたもの（64個）」• 「そこから0101と1010を除いたもの（63個）」• からなる拡張de Bruijn 列をそれぞれ繰り返し書く• 余りの特定、復元（中国剰余定理）も先ほどと同様• 7×LCM(65, 64, 63) >=500000 で、通る𝐿 = 28 （100点）• ? * ? * ? * ? * X を1ブロックとしてこれを繰り返す• * の部分四つには、• 「3進数3桁のうち一回以上0が出てくるもの（19個）」• 「010,101を除いたもの（17個）」• 「010,101,000を除いたもの（16個）」• 「010,101,020,202を除いたもの（15個）」• からなる拡張de Bruijn 列をそれぞれ繰り返し書く• 9×LCM(19, 17, 16, 15) >=500000 で、通る

得点分布（JOI）
0510154050024681012

得点分布（JOIG）
10点 ２人0点 7 人