Layered Barcode
Display 解説

• 窓 64 個、紙 192 枚、商品 256 種類
  • 商品のバーコードは黒がちょうど 32 個のランダムな模様
• 紙の模様 (白・黒・穴) を最初に設計し、1024 回の注文に順に応える
  • 注文は直前と違う商品から一様ランダム
  • 1 手: どこかの窓で見えている紙を取り出し、好きな深さへ差し込む
• 得点 2KE + T (小さいほど良い)
  • 誤り (E) 1 回は 384 手分 → 全ての注文で表示を一致させたうえで、手数 T を減らす

• 問題文のサンプルプログラム
• 紙 k に商品 k の模様をそのまま印刷 (全一致紙)
  • 紙は 192 枚なので、商品 0〜191 の分だけ
• 全ての紙が全ての窓を覆うので、動かせるのは一番上の紙だけ
  • 注文の紙が一番上に来るまで、一番上の紙を一番下へ
  • 商品 192〜255 (1/4) の注文は誤り (1 回 384 手分)
• 全一致紙は他の解法へのヒントのつもり

解法0 のビジュアライザ

• 一番上の紙だけを動かし、目的の紙が来るまで回す
• 紙のない商品 192〜255 の注文は何もせず誤り

seed=0 の全 1,024 注文。注文番号を入れるとその注文へ
キー: p 再生 / 停止、n / b 次 / 今の注文、. / , 1 手

• 窓 j ごとに、窓 j だけが白の紙と、窓 j だけが黒の紙を置く (128 枚)
• 2 枚のうち上の紙の色が窓 j に見える
  • 色を変えたい窓は、上の紙を下の紙の直下へ (1 手)
• 手数は直前の商品と食い違う窓の数 = 平均 32
• この解法を提出する参加者が多く、団子になった
• ここからの改善はやや難しかった

解法1 のビジュアライザ

• 食い違う窓ごとに、上の紙を下の紙の直下へ

seed=0 の全 1,024 注文。注文番号を入れるとその注文へ
キー: p 再生 / 停止、n / b 次 / 今の注文、. / , 1 手

• 解法0 の全一致紙と、解法1 の切り替え紙を組み合わせる
• 切り替え紙は窓 0〜62 の 126 枚だけにし、残り 66 枚を全一致紙にする
  • 全一致紙は最下部に並び、列の先頭の紙が窓 63 に見える
  • 窓 63 は列の先頭を末尾へ送って切り替える
• 注文ごとに安い方を選ぶ
  • 切り替え: 食い違う窓の数
  • 全一致紙 (あれば): 列の中の位置 + 1
• 1 注文 手 → 手

解法1b のビジュアライザ

• 全一致紙が一番上に来る注文では、全ての窓が一度に揃う

seed=0 の全 1,024 注文。注文番号を入れるとその注文へ
キー: p 再生 / 停止、n / b 次 / 今の注文、. / , 1 手

• B 窓ずつのブロックごとに、B+1 枚の櫛形の紙を置く
  • 紙 i は窓 0〜i−1 が黒、窓 i が白、残りは穴
  • (B+1)! 通りの並べ方を幅優先探索
• AI に問題文だけ渡して全て任せると、この方針を選びがち (→ AI 丸投げの強さ)
• B = 2 では改善せず、B を増やしても少ししか減らない
  • → 1 手で多くの窓を揃えたい

補足 (ブロック) のビジュアライザ

• 4 窓ずつのブロックごとに、5 枚を並べ替える

seed=0 の全 1,024 注文。注文番号を入れるとその注文へ
キー: p 再生 / 停止、n / b 次 / 今の注文、. / , 1 手

• 窓 h ごとに紙の束 (段 h) を作る
  • 段 h の紙は窓 0〜h だけが不透明で、ある商品の窓 0〜h の色を印刷
• 段 0, 1, …, 63 の順に重ねると、段 h の先頭 (一番上) の紙が窓 h に見える
• 操作は 2 種類
  • 切り替え: 段 h の先頭を、目標色の紙の直下へ
  • 窓 0〜h が目標と一致する紙を掘り出して一番上へ。次の注文で段の先頭へ戻す
• 注文ごとに、手数が最小になる紙を選ぶ (切り替えだけの場合も含む)

• 各段 2 枚から始め、期待手数が最も減る段へ 1 枚ずつ足す
  • l 枚の段 h の紙を使うと、掘る手数 (l−1)/2 と、残りの窓の切り替え (63−h)/2
  • 窓 0〜h が広い深い段ほど枚数が多い
• 1 注文 手 (解法1 の 6 割)
• 右図の重ね順: 紙の模様が階段状に並ぶ

解法2 のビジュアライザ

• 掘り出した紙を一番上に置くと、窓 0〜h が揃う
• 残りの窓は段の先頭で切り替える

seed=0 の全 1,024 注文。注文番号を入れるとその注文へ
キー: p 再生 / 停止、n / b 次 / 今の注文、. / , 1 手

• 全ての商品に紙を持たせたいが、紙 192 枚 < 商品 256 種類
• 似た 2 商品で 1 枚を共有する (ペア紙 64 枚 + 単独紙 128 枚)
  • 色の違う窓は穴にし、その窓の段の先頭で表示
  • 食い違う窓が少ない組から貪欲にペアにする
• 段 h には窓 h が白の紙と黒の紙が両方必要。ペア紙は窓 h で 2 商品が一致する段にだけ置ける
• 注文ごとに商品の紙を掘り出して一番上へ置き、覆われない窓を切り替える

解法3 のビジュアライザ

• 毎回、商品の紙を掘り出して一番上へ
• ペア紙の穴の窓は、段の先頭で表示

seed=0 の全 1,024 注文。注文番号を入れるとその注文へ
キー: p 再生 / 停止、n / b 次 / 今の注文、. / , 1 手

• 解法3 では、段 h の紙で揃うのは窓 0〜h だけ。残りの窓は 1 つずつ切り替える
• 窓を 2 種類に分ける
  • 階段窓 (0〜29): 階段構造を作る。紙は見えている窓がないと動かせないので、段の先頭をつかむのに使う
  • 一括窓 (30〜63): 商品の紙は全て、一括窓を全て覆う
• 商品の紙を一番上に置くだけで一括窓 34 個が揃い、切り替えは階段窓だけになる
• ただし、ペア紙の一括窓の穴 (2 商品で色の違う窓) を表示する方法が要る

• 目的: ペア紙の一括窓の穴 (2 商品で色の違う窓) を、少ない枚数の紙で補いたい
• 全ての段より上に穴埋め紙を置き、並べ替えるだけで穴の窓の色を変える
  • 一括窓ごとに穴埋め紙を 2 枚選び、片方は白、もう片方は黒。他の穴埋め紙はその窓が穴
  • 窓の色 = 2 枚のうち上にある方の色 (穴でない窓は商品の紙が覆う)
• 7 枚で足りた
  • 2 枚の組 21 通りを、一括窓 34 個に順に割り当てる (13 個は最初の組から繰り返す)
  • 6 枚では、表示できる組が足りないケースが多い

• ペア紙が穴の窓の色は、穴埋め紙の上下の要求になる
  • 例: 窓 3 を黒に →「穴埋め紙 2 を 0 より上に」
  • 循環がなければ、その順に並べて表示できる
• ペアの 2 商品の要求はちょうど逆向き
  • 循環しない組だけをペアの候補にする
  • 費用 (階段窓の食い違い × 3 + 一括窓の食い違い) の安い組から貪欲に選ぶ
  • 階段窓の穴は段で切り替える手数がかかるので重くした近似
• 注文ごとに、最短手数の並びを幅優先探索 (7! = 5,040 通り)
• 1 注文 手 (うち穴埋め紙 手)。解法3 から

解法4 のビジュアライザ

• 商品の紙のすぐ下に穴埋め紙 7 枚
• 切り替えは階段窓 0〜29 だけ

seed=0 の全 1,024 注文。注文番号を入れるとその注文へ
キー: p 再生 / 停止、n / b 次 / 今の注文、. / , 1 手

• 解法4 は、ペア紙を置ける最も深い段から詰めていた
  • ペア紙は 2 商品が使うので、同じ段に集まると互いの下に埋もれて掘る手数が増える
• 置ける段のうちペア紙が最も少ない段 (同数なら深い段) に置く
• 残りの単独紙は、段の白黒が揃うように選ぶ (偏ると切り替えで目標色の紙が深くなる)

解法5 のビジュアライザ

• ペア紙が各段に散らばり、掘る手数が減る

seed=0 の全 1,024 注文。注文番号を入れるとその注文へ
キー: p 再生 / 停止、n / b 次 / 今の注文、. / , 1 手

• 段 k の紙 y を、段 l (l ≤ k) の先頭の直上へ移す
  • y は窓 l〜k の段の先頭より上に来る → 窓 l〜k のうち y が不透明な窓が y の色になる
• 色の違う窓を 1 手でまとめて直せる
  • 直る窓の数 − 掘る手数 ≥ 2 なら行う (持ち上げと、次の注文で戻すのに 2 手)
• 1 注文 手 → 手

解法6 のビジュアライザ

• 深い段の紙を浅い段の先頭の上へ移し、複数の窓をまとめて直す

seed=0 の全 1,024 注文。注文番号を入れるとその注文へ
キー: p 再生 / 停止、n / b 次 / 今の注文、. / , 1 手

• 戻す → 穴埋め紙 → 掘る → 持ち上げ → 切り替え、と順に行うと、同じ紙を何度も動かすことがある
• 最終的な並びだけを決め、動いた紙を 1 回ずつ動かす操作列に作り直す
  • 見えている紙から順に、最終の並びで自分より下にある確定済みの紙の直上へ移す
  • 途中で見えている紙がなくなったら、元の操作列を使う
• 1 注文 手 → 手

前の注文の紙 A を戻した直後に、切り替えでさらに下げる例。組み直すと、紙 A は一番上から紙 B の下へ直接移る

解法7 のビジュアライザ

• 1 注文の中で、各紙を 1 回ずつしか動かさない

seed=0 の全 1,024 注文。注文番号を入れるとその注文へ
キー: p 再生 / 停止、n / b 次 / 今の注文、. / , 1 手

• 解法7 までは、使った紙を段の先頭へ戻していた (最近使った紙が上)
  • 注文は互いに独立なので、最近使ったことに意味はない
• 紙を使う商品の数 (使用数) の多い順に並べる → ペア紙が浅くなり、掘る手数が減る
  • 切り替えで先頭から下げる紙と、今回の紙に窓を覆われた段へ戻す紙を、使用数順の位置へ
• ただし先頭 2 枚は白黒を変える → 次にその窓の色を変えるときに 1 手
• 1 注文 手 → 手

• 上から: 穴埋め紙 7 枚、段 0〜29 (185 枚)
  • ペア紙 71 枚、単独紙 114 枚
  • 階段窓 30 個、一括窓 34 個
• 紙の設計: ペアを貪欲に決める → ペア紙を各段に散らし、単独紙で段の白黒を揃える
• 注文ごと: 戻す → 穴埋め紙 → 掘る → 持ち上げ → 切り替え → 組み直し
• 1 注文 手。コードは約 21 KB

解法8 のビジュアライザ

• 段の中は使用数の多い紙が上

seed=0 の全 1,024 注文。注文番号を入れるとその注文へ
キー: p 再生 / 停止、n / b 次 / 今の注文、. / , 1 手