はじめに

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

どんな感じ?

5月はゴールデンウィークと被るということもあり、開催されなかったため、久しぶりでした。

今回は、いつもの鍋谷さんではなく、松島さんの出題でした。半数の人が全完、丁度良い難易度で面白い問題だったと思います。今回は余裕を持って解くことができました。

問題は松島さんのサイトにある「ドキドキ登山」でした。

内容はとしては、サイクリックなアミダクジ状の登山道を登る時、「落石の通ってる道に来たら登るのを諦める」という条件で、山頂に辿りつける人 ( 入口に対応 ) を列挙するものです。

…アミダクジというキーワードは大きなヒントになるのでは、ということで、問題文には出てきていないのですが、冒頭の問題説明でぽろっと言ってしまった松島さんがお茶目でした。

シンプルに、まず石の通る、N.G.な道の情報を洗い出し、その上で、各登山者の動きをシミュレートして、N.G.な道を通るかどうかを判定します。

次の図のように、横の道が3本ある場合、縦の道は4つの区間に分類されることになります。そのため、「各区間でどの縦の道を通るか」「各横の道を通るか否か」という情報を調べればよいことになります。

f:id:ange1:20160605114118p:plain

石が通る道であれ、登山者が通る道であれ、各区間での縦の道 ( 0～7 ) と、区間を区切る横の道 ( 1～7 ) の数値の差の mod 8 によって、横の道に逸れるかどうかが分かります。横に逸れる毎に縦の道の数値を修正しながら区間を進めていけば、通る道が分かるはずです。

ということで、Rubyで実装しました。

…なお、34行目の(65+c).chr}*""は、山頂に辿りつける登山者の文字 ( A～H ) を join しているのですが、golfer以外はフツー使わないよね、と…。そうなのか…。

ところが、鍋谷さんや ( オンライン参加の ) しえるさんがそうだったのですが、実は「縦の道は見る必要がない」という…。これは気付きませんでした。

どういうことかと言うと、縦の道のある区間が、石・登山者両方の通るものであった場合、そこにつながっている横の道についても、石・登山者両方が通るはずだ、ということです。

そのため、「石の通る横の道の集合」と「登山者の通る横の道の集合」に重なりがあるかどうか、で判定ができるということです。ただし、そもそも石が横の道を一切通らない場合は例外で、石の出発点と同じ縦の道にいる登山者1人だけが山頂に辿りつけないことになります。

ということで、後から書き直したBrainf**kの実装がこちら。

…まあ、見ても良く分かりませんよね。やってることをRubyで表現するとこんな感じになります。

各ケースの入力が標準入力の1行、答えが標準出力への1行に対応します。

最初は石にぶつかって登山者が死んでしまう ( 生存した人を列挙する ) という想定だったのが、あまりにサツバツなのでマイルドな表現に直したらしいです。

同じようなことを参加者の今城さんも考えたようで、石じゃなくて女の子が下りてくる、登山者は男の子で、女の子と出会うとそこで登るのを止めてしまう、というイメージで解いたそうです。心温まる想定ですね!! ( なお、女の子1人が何股もかける訳ではなく、女の子は十分な数が下りてくるということです )

皆さまお疲れ様でした。次は7月の第一土曜とのことです。終了後の飲み会は都合で参加できませんでしたが、次はそちらも参加したいと思います。