オフラインリアルタイムどう書くE05参加しました

はじめに

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

どんな感じ?

今回、また鍋谷さん出題に戻りました。残念ながらキャンセルが多く、参加人数が少なかったのですが、その分各自の発表時間が長く、濃くなった印象もあります。

今回は ( 事前のコメント通り ) 易しめの問題で、ほとんどの人が完成に持ち込んでいました。

問題

問題はドキドキトロッコでした。前回のドキドキ登山類似…? ですが、N.G.な道が明確に「死」というサツバツな設定だったりします。

…ではなくて、次のような問題でした。

• 3線 ( a,b,c ) のトロッコの路線に対し、1～9 のコース ( 切り替えポイントや行き止まりを含む ) の列が与えられた時、行き止まりにならずに最後までたどり着ける「ルートのある」路線を全てつなげたもの ( なければ “-”) を答える

なお、1～9 のコースについては、オリジナルの問題をご覧ください。

解説

自分の方針

会場では大まかに3通りの方針が出ていました。
「明らかにDFSじゃないか」という意見もありましたが、最初の方の発表は ( 私も含めて ) 違ったという…。

さて、真っ先に思い浮かんだのは、「ある路線から出発して、辿りつける路線のセットを調べる」という方針でした。これはbit-setで管理できますし、前からコースを見て行って、「状態の重ね合わせ」 を行えば済むから( bit-set なので bit-or でできる )です。

路線a,b,cとbitの対応は次の図のようになります。

この対応に基づいて、各コースはbit-setの3要素配列としてデータ化することができます。コース1であれば、次のように(3,6,4)というように、です。

後は、コースを先頭から見て行って、行ける可能性を重ね合わせて更新していって、どこか1箇所にでも行ける ( bit-setとして非ゼロ ) であれば、元の線路は「活き」ということになります。

実装

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

今回は見やすさ重視に行って、* 演算子による join 等封印したのですが、文字コードをベタに書いた所でボロが出てしまいました…。いえ、体が?a.ordと書くのを拒否したんです。しようがないんです。

今回はBrainf**kは、条件分岐の嵐になって大変かなあ…と思ったのですが、良く考えたら、Brainf**kの条件判断は非ゼロ-ゼロなので、負数さえ使わなければ加算で logical-or ができるという、非常にこの問題に優れた特性を持つので、各bitをセルに持つようにすることで、とても素直に組むことができました。

終わりに

次回はまた松島さんの出題とのことで、楽しみにしています。…そう言えば、E01から、問題文の説明に全て図が出てきていて見ている分には分かり易いのですが、別にそれは必須ではないよね、というお話が。どうなるんでしょうね。