Go to Qiita Advent Calendar 2024 Top
LoginSignup
3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@kusano_k

MC Digital プログラミングコンテスト2022（AtCoder Heuristic Contest 008） #AHC008

Last updated at Posted at 2022-02-26

MC Digital プログラミングコンテスト2022（AtCoder Heuristic Contest 008） - AtCoder

ヒューリスティックコンテストのレートが正式版になったし、企業コンテストで賞金が出るし、seed=0の可視化結果公開OKだしでだいぶ盛り上がっていたように思う。良いですね。

暫定29位、5,406,122,145点（54 %）。
TODO: システムテストが終わったらここに結果を書く。

私のプログラムの動きはこんな感じ。

ニコニコ: https://www.nicovideo.jp/watch/sm40099772

コード: https://github.com/kusano/ahc008

プログラムの概要

中央にこういう壁を作り、ゲートに犬か猫が来たら閉じ込める。

image.png

人は原則として、$\left(x, y\right) = \left(\frac{S}{2}, 0\right)$ から移動可能な位置に移動する。ペットがこの位置に移動できないように壁を作る。そのために、各ペットから $\left(\frac{S}{2}, 0\right)$ への最短経路上で、ペットからの距離が $2$ の位置に壁を作る（ 距離 $1$ はルール上壁を作れないので）。壁を作れないなら、各ペットから $\left(\frac{S}{2}, 0\right)$ への最短経路上で、ペットからの距離が $3$ の位置を目指して移動する。また、ペットを面積 $30$ 未満の領域に閉じ込められるなら、常に壁を作る。人を閉じ込めたり、ペットを面積 $30$ 以上の領域に閉じ込めてしまうなら、これまでの条件を満たしていても、壁は作らない。

最後の16ターンはスコアが上がるなら壁を作る。人を閉じ込めたり、ペットに広い領域を明け渡したりしてでも、スコアを上げてほしいという思い。

以降は、上記の詳細と合わせて、やったことを時系列で書いていく。

chokudaiさんの顔を描く

vis.png

現在位置に隣接するマスを選んで通行不能にする。このターンの開始時点でペットもしくは人が居るマスを選ぶことは出来ない。隣接するマスにペットが居るマスを選ぶことも出来ない。既に通行不能なマスを選んだ場合は何もしない。

「（人に）隣接するマスにペットがいたら、2文目の条件で選べないでしょ？　なぜ同じことをわざわざ太字で言い直しているの？」という勘違いに気が付いた。あと、壁を置ききれなくて、ドット絵をちょっと書き換えた。これで、壁の設置には案外余裕が無いのだということにも気が付いた。完全にネタのつもりだったけど、意外と役に立った。ネタプログラムも書いてみるものだな。

ツカモさんの可視化結果を見る

問題文から、人が自分の周りのスペースを確保するゲームだと思っていたけど、違うわ。これ、ペットを閉じ込めるゲームだ。

モンテカルロ法

0.12 %

桁数が多くて分かりづらいので、以降、スコアは $10^{10}$ に対する割合で書いていく。$10^{10}$ は、ペットも壁も無いときのスコアで、自明な上界。

壁を設置して自分の領域を確保していくの、囲碁っぽいよね？　囲碁といえばモンテカルロ法だよね、という発想。全然ダメ。まあ、そりゃそうか。最初の1手をどうしようが、以降をランダムに進めれば、最終的には自分の周り全てが壁になる。そうなると、最初の1手の評価はどれも同じになってしまう。

ルール的には人は全員同時に動くけど、このときから人は1人ずつ順番に処理していくようにした。他の人が移動する位置には壁を設置できないというルールが面倒。1人ずつ処理すれば、前の人が壁を設置したところには移動しないだけで良い。前の人が後の人のことを考えずに壁を設置するというロスはあるけれど、たいしたことはないだろう。たぶん。

ペットを追いかけて、近づいたら壁を設置

11.8 %

自然な発想。明示的にペットを取り囲む動きをプログラミングしているわけではないけど、四方から近くに壁を設置すれば、自然と取り囲めるはずである。これだけでも、まあまあそれっぽく動く。

真面目に考察してくれていたら、とても申し訳ないのだけど、これだけです。晒したのは乱数の引きが良くて上手く動いたやつ。平均的には、こんなに上手くいかない。

ゲートを作って誘い込む

18.1 %

この記事の冒頭のやつ。盤面を半分に分ければ、猫は上下を等確率で選ぶので上下間の移動が高確率で発生し、ゲートを通る。人を上下に均等に配置すれば、犬も同様。

発想元はMinecraftのトラップタワー。

Minecraftを遊んでいる人は知っていそうだし、遊んでいない人は興味が無いだろうが、一応解説。モンスターは移動可能な範囲の中からランダムに目的地を選択してそこに向かって移動する。このプログラムでのゲートの位置に、モンスターは上を通行可能と認識するのに実際は落っこちる「トラップドア」を置いておくと、モンスターがそこから落下して死亡する。モンスターと戦う危険を冒さずに、しかも自分の手を動かすことなく、モンスターを倒してアイテムを得られてウマウマ。

犬猫がいないときの特別扱いを削除

18.1 %

Seed=0の特別扱い。計算してみると、犬も猫もいない入力は0.137 %しかありません。こんなの特別扱いしていても面倒なだけ。スコアが変わっていないので、ジャッジの100ケースの中にもそんな入力は無い。

image.png

Seed=0でもゲートを作るようになったので、以降seed=0の結果は晒せなくなる。

ちなみに、seed=0は意図的に犬も猫もいないようにされている。

初期位置がゲートに近い人でゲートを作る

25.6 %

ゲートを作るために初期位置に移動する手数を削減。これまでは単に0～4の5人でゲートを作っていた。

ゲートを作る人が、ペットを閉じ込める仕事もそのまま担当している。ゲートを作るのはともかく、ペットを閉じ込めるのは最優先事項。上記のように人は0番目の人から順番に処理しているので、内部的に人を並び替えるようにした。

右上、右下から狙っていく

14.3 %

バグを直したら、 19.8 %　狙いを変える前からバグっていたので、この方針の影響が結局どうだったのかは良く分からん。

これまでは、ゲート担当者以外は自分に一番近いペットを付け狙っていた。手作業で操作することを想像すると、端のほうから順番に閉じ込めていきたい。ということで、右上や右下のペットから順番に狙っていくことにした。

スコアは下がった。とりあえず気にせずこのままで。

最後は人を閉じ込めてでもスコアを上げる

21.2 %

最後16ターンは、スコアが上がるなら壁を設置するようにした。人を閉じ込めてでもスコアが上がる場合は多い。

壁 壁 壁 壁 壁 壁 壁 壁 壁
人1   人2   人3        🐕 壁
壁 壁 壁 壁 壁 壁 壁 壁 壁

この状況だと人3が壁を設置するべきだけど、何も考えずに番号が若い順に処理しているので、人1が壁を設置して、人2と人3も閉じ込めてしまう。この辺は頑張る余地があった。あと、16ターンも適当。このときは、「プログラムの改良が進めば、だいたいのペットは閉じ込められるようになるはず！　ここを頑張ってもしょうがない」と思っていた。最終的にも、このルーチンはけっこう動いていた :weary:

同じペットを追い続けるようにする

22.8 %

左上か右下に近いペットをターンごとに選んでいた。ペットの位置が入れ替わると別のペットを追いかける無駄な動きが発生してしまうので、固定。

nターン後の各マスのペットの存在確率を可視化してみる

こんな感じ。

image.png

いちいちスクリプトを書いてこれを計算するのも面倒だし、手でポチポチ壁を置きながら変化を見てみたら何かが見えてこないかなと考えた。何も見えてこなかった。

最初は、

for (...)
  innerHTML += `<div ...>`

と書いていて、とても重かった。「面倒だからDOMの操作を真面目にやりたくないのだが……」と思いながら、ループの中は文字列の連結にして、 innerHTML への代入を最後の1回だけにしたら軽くなった。「 innerHTML はセキュリティ的に問題があるだけでなく、パフォーマンスも悪い」とどこかで見たけど、こういうことか。

このプログラムを書く前から分かっていたこととして、$(x+y) \mod 2$ のパリティについて、牛と兎はターンの偶奇に一致する。豚は一定。

最短経路上に壁を設置する／各人がもっとも近いペットを追う

39.8 %

単にペットの近くではなく、ペットと $\left(\frac{S}{2}, 0\right)$ の最短経路上に壁を設置する。

image.png

兎から距離が $2$ のマスと、$\left(\frac{S}{2}, 0\right)$ への最短経路のうちの1本を図示している。距離が $2$ のマスうちのどこに壁を設置するべきかは一目瞭然。

上記の「右上、右下から狙っていく」を止めた。これについての詳細は後で。

人を上下に均等に振り分ける

44.4 %

上下に人が偏ると、犬が上手く誘導されない。

壁設置の条件を微修正

46.1 %

上のパリティの話。なんか点数が上がったから、距離 $2$ だったら距離 $3$ に移動せずに停止していたけど、これ、牛と兎はパリティがターンごとに変わるので、距離 $3$ に移動しても次のターンは絶対に距離 $3$ にならないからだよね。なら豚は移動するべき。

あと、何となく牛と兎は距離 $2$ の位置だけではなく、距離 $3$ の位置にも壁を設置するようにしてみた。

ペットを閉じ込めるときのマス数を見る

46.9 %

これまでは、ペットに近づいたら壁を設置することによって、ペットを囲むことを期待していた。これだと、袋小路の奥にペットがいて人がペットから離れた袋小路の首の部分にいるときに閉じ込められないし、たまたまペットをとても広い領域に閉じ込めてしまうこともある。ペットを狭い領域に閉じ込められるなら壁を設置するし、広い領域に閉じ込めてしまうなら壁を設置しないようにした。

狭い／広いの閾値は $30$。適当。ちゃんとテストを回して閾値を決めましょう。しかし、今回の場合はケースによってスコアのバラつきが大きいから、大量にテストを回さないといけなくて面倒なんだよな……。結局最後までローカルテストケースに入っていた100個のseedしか使っていないわ。

中央から遠いペットを人ごとに狙う

48.6 %

「各人がもっとも近いペットを追う」の続き。ちゃんと考えてみると、自分に近いペットか端のほうのペットを狙うかの問題ではなく、全員が同じペットを狙ってしまうことが問題。人によって違うペットを狙うようにした。ついでに、単に座標が右上や右下かではなく、 $\left(\frac{S}{2}, 0\right)$ から遠いペットを狙うようにした。

犬誘導のために他の人が待機するとき、少し離れる

51.2 %

微修正のつもりだったけどこれで念願の50 %が達成できるのか。ゲートを閉じる人と同じ場所に待機していたけど、犬が詰まるので少し離れるようにした。

猫だけになったら、猫を追う

54.1 %

（ゲートを閉じる人以外は）犬猫を無視していたけど、残りが猫だけになったら追いかけるようにした。犬は、追いかけるのではなく、ゲートの周囲に立つことで犬を誘導するようになっている。

これはたぶんダメ。普通に猫を追いかけてもなかなか捕まえられない。もっと上手いやり方がありそう。提供されているビジュアライザで1個見て、良い感じだなと思ったけど、今seed 100個を動画にしたのを見ていると、ほとんど捕まえられていない。まとめて動画にするやつを最初に作っておけば良かったな……。

2次元配列を1次元化

vector<vector<int>>(S, vector<int>(S)) を vector<int>(S*S) に。これ、高速化に寄与するだけではなく、 for (int x=0; x<S; x++) for (int y=0; y<S; y++) F[x][y] が for (int p=0; p<S*S; p++) F[p] でプログラムも楽になる。今回、コードの分量が多いのでとても面倒だった。どうせ最後にはやるのだから、最初からやっておけば良かった。

ゲートの設置数を制限

52.2 %

見張っているゲートは右端の1個だけである。ゲートは左端のほうにあるから、猫は基本的に右端のゲートを通るのだけど、ゲートが多くて見張っているゲートが右側にあると、猫がそこを通らない。

スコアが下がっていたので削除。本当はもっと大量のケースで確認するべきだけど、100ケースで確認 :rolling_eyes: 　まあ、ゲートが多いということは犬や猫が多くて、1匹あたりの確率が多少低くなっても、順番に捕まえられるのでしょう。

ペット数が少ないときはゲートを作らない

「犬猫がいないときの特別扱いを削除」の続き。犬や猫がいない入力は（生成確率が低いので）どうでも良いけど、犬や猫が1匹や2匹のときもゲートを作らずに、普通に追いかけたほうが良いのでは？　良くなかった。マジか。まあ、確率が0.137 %とはいえ、犬や猫がいないときにはスコアが上がるので、ゲートを作らずに追いかける処理はそのままで。

全シードをまとめて動画にする

頑張ればわずかにスコアを上げる余地はあるかもしれないが……もう面倒だな。コンテスト終了後に皆がヴィジュアライザの生成するアニメーションGIFを上げるだろうけど、全ケースまとめると見栄えがするのでは？　ということで残り時間は動画にするスクリプトを書いていた。

PythonのPillowで連番PNGを作り、ffmpegで動画化。

ffmpeg -r 30 -i out_%06d.png -b:v 100M -pix_fmt yuv420p out.mp4

PNGは各画素がRGBの値を持っている。一方、動画は、一般的には輝度（Y）と色差（UとV）で色を表わし、輝度は各画素が持っているものの、色差は2x2の4画素ごとに1個の値しか持っていない。一般的ではない各画素が3個の値を持っている状態（YUV444）だと、Twitterに投稿できなかったりするので、 -pix_fmt yuv420p で変換しましょう。

コンテスト終了後に他の人のプログラムを見て

え、皆だいたい盤面全体に壁を作っておいて、ペットを閉じ込める方針なの！？

私が見つけた限り、ゲートっぽいものを作っているのは、ツカモさんと、作問者のYoichi Iwataさんだけだな。

Wataさんのゲート、形が私と全く一緒w

ヒューリスティックコンテスト、こう、頭を使った綺麗な盤面はそこそこのスコアは取れるけど、最終的にはプログラムが作る不定形になるものだと思っていた。綺麗な盤面を作る方針は全く考えていなかった。プログラムを書いて試さないまでも、上位陣のスコアが取れるかどうかくらいは考えるべきだったな……。反省。

まあ、とはいえ、私の方針でもそこそこの点数は取れているし、どちらの方針でも同じくらいになるようにバランスが調整されているのかもしれない。

バランス調整という話だと、300ターンも絶妙。300ターンだと、全てのペットを捕まえられるかどうかという争いになる。もっとターン数が多いと、全てのペットを捕まえることが前提で、あとはちまちまと詰めていくというあまり面白くない戦いになりそう。

3
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?