はじめに

2018/2/3開催の「オフラインリアルタイムどう書くE21」に参加しましたので、そのレポートです。

前回記事にしたのが確かE14なので、それから随分空いてしまいました。オフライン参加できなかったり、記事書くタイミングを逃したり色々あったわけですが…、まあ久々にということで。

どんな感じ?

年が明けて一発目、一年の計は…というやつですね。今回は参加人数少な目で、ほぼ見知ったメンバーでした。なお、冒頭にオブラブというコミュニティのカレンダーを頂きました。カレンダーに月別で技術情報を載せているという、なかなか面白いものです。有難や。

今回は松島さんの出題回で、問題はドキドキロシアンルーレットでした。頻繁に人が死ぬと定評のあるドキドキシリーズ? ですが、会場の空気は別にそんなサツバツとはしておりませんですよ。概要は次の通りです。

詳細は上のリンクからご覧ください。

実は「やられた場合は進まない」から分かる「その次の人は必ず外す」に違和感を感じたので、最初ちょっと混乱してました。「あれ? リボルバーって撃ったら取り敢えず1つ回るよな…?」的な。この問題では進まないという前提です。

最初は貪欲に、「最初に廻って来た順で実弾を引きあてる」ように決めて行けば良いんじゃないか? と思って組み始めたのですが、良く考えたら「皆1周外して、次の周でやられる」とか、色々パターンがあるよな…ということで、「取り敢えず実弾を色々配置して全探索するか」ということに落ち着きました。

そのため、実弾の位置を combination で全列挙して、実際にロシアンルーレットをシミュレートしています。本当に人を殺さなくても試せるのがプログラミングの良い所ですね! ( 詭弁 )

※ちなみに、当初の問題のパラメータでは複数解が有り得ると分かったので、途中で差し替えがありました。ただコード的には複数解を全部挙げるようにしています。

なお、やられるたびに参加者が減っていくわけなので、そこは人の情報を保持するArrayに対して、

ということをしています。で、やられるべきでない人がやられた場合は、その弾丸の配置が不適切だったと判断できる、ということです。

ただし、懸念事項が1つだけあります。それは、参加者が延々と外れを引き続き、いつまでたってもやられないというケースが有り得るということです。対処しないと永久ループになってしまいますから、何かしらシミュレーション手順に上限を設ける必要があります。

そこで、どれくらいで上限を設ければ良いか、それは同じ人が同じ弾倉の位置に戻ってくるまでどれくらい異なるパターンをたどれるか、なので、最大弾数×人数で見積もれるだろうと考えました。ただし、だれかがやられるとパターンが崩れますので、このステップ数のカウントはやられる人が出る度にリセットしておきます。

ということで、何とか時間内に実装できました。

ただ、実装は間に合いませんでしたが、「やられる人の順番」をベースにする方法も考えていまして。単純には、permutation なりで順番を列挙して、その順番に沿った弾倉の状況を探っていくような感じです。

ただ、気を付けなければ行けない所としては、

この2点です。組み合わせ数はそれなりに多くなりそうな気もするのですが、ただ、空回りする周数が増えれば、弾倉の位置がどんどん空と判明して行って、そのうち実弾を入れられる場所に余裕がなくなっていくはずです。そのため、枝刈はラフにやっても良いんじゃないかな、と思ってました。

ということで、終了してから実装した動的計画法バージョンがこちらです。

探索部を相互再帰で書いているのですが、「空砲?で次に回す」処理に注力するだけで済んでいます。( 空砲というと意味が違うような気もしますが、ともかく実弾に当たらなかった、という意味で )

何周空回りさせるかは、関数 detail で試していくわけですが、最初の弾倉位置が被ったらもうこれ以上アタリはないと判断できます。このことで、無限ループへの対処が非常に単純にできています。

解の重複に途中で気づいてしまった出題者の松島さん、痛恨のミスという面持ちだったのですが、問題として手ごたえのある面白いものだと思います。

※逆に、いつもは出題者の立場か、或いは時間内に解けている鍋谷さんが今回は苦戦し、とても悔しがっていたのが印象的でした。

さて次の開催案内がもう出ています。興味がある方は是非ご参加を。

なお、今回の色々な方の実装例は、オフラインリアルタイムどう書く E21 の問題 - Qiitaに紹介されています。