でぶアドベントカレンダー 23日目 でぶヒューリスティックコンテストの問題を考えた

はじめに

メリーでぶばんわ~(メリでぶ) この記事はでぶ Advent Calendar 2024 の23日目の記事です。

今年はchatGPTと相談しながらshojin_debuをテーマにして、ヒューリスティック風の問題を作ってみました。 ビジュアライザも作りました!

問題文 「でぶとダンジョン飯」

shojin_debuはダンジョンに潜ってグルメを堪能することを思いついた。

このダンジョンは H×W の格子状の部屋からなり、各部屋同士は通路で繋がっている。各部屋には食事が置いてあり、食べると shojin_debu は太る（体重が増加する）。

ただし、ダンジョンを通る際には様々な注意点がある

  • 各ターンで「移動先の方向を決める」 → 「移動先にある食事を食べるか決める」という流れで行動する
  • ダンジョンの通路は狭いため、通路ごとに設定された体重制限を超えると、shojin_debuが通路につっかえてしまい、通過できない
  • shojin_debuが部屋に一度入ると、部屋が重みに耐えかねて床が抜けるため、もう一度入ることができない
  • 部屋にある食事は食べなくてもよいが、食事をスルーすると shojin_debuの不満が溜まり、最終スコアに影響する
  • shojin_debu は特殊能力「なんや😡😡😡」を K 回（K は入力で与えられる最大回数）まで使用することができ、通路の壁を破壊して体重制限を回避することができる。ただし、この能力には回数上限があるため、無闇に使用することはできない

床が抜けて落ちるでぶ

shojin_debu は (スタート部屋) から出発し、できるだけ多くの食事を食べながら (ゴール部屋) に到達したい。あなたの目的は、shojin_debu の最終的な体重を最大化しつつ、ゴールに到達した場合のスコアを高めることである。

入力

入力は以下の形式で与えられる

H W 
sx sy gx gy 
K 
c_{0,0} c_{0,1} ... c_{0,W-1} 
c_{1,0} c_{1,1} ... c_{1,W-1} 
... 
c_{H-1,0} c_{H-1,1} ... c_{H-1,W-1} 
h_{0,0} h_{0,1} ... h_{0,W-2} 
h_{1,0} h_{1,1} ... h_{1,W-2} 
... 
h_{H-1,0} h_{H-1,1} ... h_{H-1,W-2} 
v_{0,0} v_{0,1} ... v_{0,W-1} 
v_{1,0} v_{1,1} ... v_{1,W-1} 
...
v_{H-2,0} v_{H-2,1} ... v_{H-2,W-1}
  1. 1 行目:
    • ダンジョンの縦幅 (H) 、横幅 (W)
    • 10 <= H, W <= 20
  2. 2 行目:
    • スタート部屋の座標 (sy, sx) とゴール部屋の座標 (gy, gx)
    • 0 <= sx, gx < H, 0 <= sy, gy < W)
    • (sx, sy)と(gx, gy)は相異なる
    • なお、マップの左上の地点を(0, 0)と定め、下方向に行くとx、右方向に行くとyの座標の値が大きくなる
  3. 3 行目:
    • 「なんや😡」特殊能力を使用できる最大回数 (K)
    • 0 <= K <= 5。
  4. 続く (H) 行:
    • 各部屋に置いてある食事のカロリー (c_{i,j})
    • 100 <= c_{i,j} <= 10000
    • 食事を食べた場合には即座にカロリーの分だけshojin_debuの体重が増加する
    • カロリーの分布はλ=1/2000の指数分布に従い、上限値・下限値を外れたものはクリッピングされる
  5. 次に (H) 行:
    • (W-1) 個の整数 (h_{i,j}) （通路の横方向の制限体重）
    • (h_{i,j}) は (i, j) と (i, j+1) を結ぶ通路の最大通過体重(kg)
    • 10000 <=h_{i,j} <= 50000。
  6. さらに (H-1) 行:
    • W 個の整数 v_{i,j} （通路の縦方向の制限体重）
    • v_{i,j} は (i, j) と (i+1, j) を結ぶ通路の最大通過体重(kg)
    • 10000 <= v_{i,j} <= 50000

なお、記載がない場合には一様分布からサンプリングされる。

出力

以下の形式で shojin_debu の行動計画を出力せよ。

  1. 最初に「なんや😡」能力の使用回数 (X) を出力

    • 0 <= X <= K

  2. 続いて (X) 行にわたり、破壊する通路の情報を出力

    • 破壊する通路が結ぶ部屋の座標を出力する
    • 例: y1 x1 y2 x2（通路の座標を指定する形式）

  3. 次に、shojin_debu の合計行動回数 (M) を 1 行で出力

  4. その後、各行動を 1 行ずつ合計 (M) 行出力。

    • 各行動は以下のいずれかを含む形式とする。
      • L / R / U / D（左・右・上・下への移動）
      • debu（その部屋の食事を食べる、食べたカロリーの数値分だけ即座に体重[kg]が増加する)
      • NANNYA!!!（食べない場合）

出力例は以下である:

2          // 「なんや😡」を実際に2回使用する
2 1 2 2    // (2,1)-(2,2) 間の通路を破壊
1 1 2 1    // (1,1)-(2,1) 間の通路を破壊
5          // 行動数は5回
R debu     // 右に移動してその部屋の食事を食べる
D debu     // 下に移動してその部屋の食事を食べる
L NANNYA!!!  // 左に移動して食べなかった
U debu     // 上に移動して食べる
R debu     // 右に移動して食べる

スコア

スコアは以下の式で与えられる。

max((最終体重) - 50000*(不満度)/(H*W), 0) (ゴールに到達した場合)
0 (ゴールに到達しなかった場合)

ここで、「不満度」は、部屋に入った際に食事をスルーした回数（＝食事があるのに食べなかった回数）の合計とする。 また、最終体重は、食べた食事のカロリーの総和である。

なお、同じ部屋を2回以上訪問したり、通路の制限体重を超過した状態で移動をしようとした場合には不正解（WA）扱いとなり、スコアは 0 となる。

ビジュアライザ

こちらにビジュアライザを用意しました。

壁を破壊するshojin_debu
seed=2のサンプル出力を以下に貼っておきます

3
8 8 9 8
6 9 6 10
7 5 8 5
52
R debu
D NANNYA!!!
R NANNYA!!!
U NANNYA!!!
U debu
R debu
D debu
D NANNYA!!!
D debu
L NANNYA!!!
D debu
R debu
D debu
L debu
L debu
U NANNYA!!!
L debu
U debu
U NANNYA!!!
L NANNYA!!!
U NANNYA!!!
U debu
R NANNYA!!!
U NANNYA!!!
R NANNYA!!!
U debu
L NANNYA!!!
L NANNYA!!!
U NANNYA!!!
L NANNYA!!!
L NANNYA!!!
L debu
L NANNYA!!!
L debu
D NANNYA!!!
L NANNYA!!!
L debu
D NANNYA!!!
L NANNYA!!!
D debu
D debu
R debu
R debu
R NANNYA!!!
R NANNYA!!!
U debu
R debu
D NANNYA!!!
R debu
D debu
D debu
R debu

最後に

来年はAHCで作問できるといいなあ。いい原案を思いついたら頑張って調整をしてみようと思います。

没問題 「shojin_proの焼肉パーク計画」

shojin_proの焼き肉パーク計画

施設配置問題+ベイズ推定みたいな問題でした。

  • プレイヤーは焼き肉パークに焼き肉施設(焼き肉・トレーニングルーム・ダイエット食売り場)などを配置していく
  • shojin_proには空腹度・怒り度・体重などの内部パラメータが設定されており、内部パラメータや施設の位置関係に従って行動をする
  • shojin_proの行動から内部パラメータを推定し、できるだけ太らないように施設を配置していく

感じの問題でした。インタラクティブなビジュアライザを作るのがめんどくさすぎたので没になりました。 個人的には問題設定が気に入っているのですが、調整が難しそう。 あと推定系の問題は単純に作るとワンパターンな感じになってしまうので難しいですね。