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

はじめに

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

どんな感じ?

GWを挟んで2か月ぶりの開催でした。

会場枠参加で出題も担当されている松島さんが、6月付けで転職されたのですが、今回も永和さんで開催されました。松本さんも会場枠で参加されてますし、会場は当分そのままいけそうです。有り難や。

問題

今回は松島さんの出題回で、問題はサイコロできるかなでした。概要は次の通りです。

  • 1~6の数字が配置されたマス目が与えられる
  • その中からvalidなサイコロの展開図が切り取れるかどうかを判定する
  • 「validな」というのは、1~6全ての数を含んだ立方体であることに加え、3組の対面の数字の和が全て7になることを指す

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

解説

なんとか制限時間一杯で次のコードを完成させました。

方針としては、

  • 11種類の展開図パターンそれぞれに対して、
  • 与えられたマス目の配置、および転置 ( transpose ) した配置それぞれで、
  • 展開図に応じた範囲 ( 4×3 or 5×2 ) を、その範囲の左上隅の座標を変えながら、
  • その展開図でvalidなサイコロが作れるかをチェックする

というものです。

なので、各展開図パターンをPATTERNという配列で持っています。
※このパターンのデータを色々間違えて、N.G.なケースが続出していたのですが…。なんとか時間ギリギリで修正できました。

各展開図のデータとしては、展開図の幅、高さの他に、対面の位置に来るマスの組3組分、左上隅からの相対座標を持っておきます。
※ついここだけ、(y座標,x座標) の順にしてしまい、コードの他の箇所とミスマッチなのですが…。

で、チェックを行う関数validでは、その相対座標を使った間接参照でマス目の数を調べ、対面の合計7と、1~6の網羅 ( 実際は3組の小さい方1~3のみ ) を確認しています。
※ちなみに、出題者の松島さんはこの「1~6の網羅」を最初失念されていたようで、なので「対面の合計7はクリアしているけど数字の重複がある」という引っ掛けケースがありませんでした。後日追加されたようですが

ただ、転置は別途ケアしていますが、x方向反転、y方向反転したパターンもチェックする必要がありますから、これはvalidの中で間接参照をする時に、座標の扱いをちょこちょこっと弄って、x方向順/反転・y方向順/反転の4パターンを網羅しています。

終わりに

…本当は鍋谷さんの実装のように、コアの部分のパターン ( 例えば一直線上の4マス ) をチェックしてから、残りを見るようにすれば、パターンのちょっとした違いでチェックをやり直す手間が削減できると思っていたのですが…。結構大変そうだったので、途中で方針展開したのでした。

さて次の開催案内が出ました。興味がある方は ( ってこの記事読む人そんなにいるかね、ってのは置いておいて ) 是非ご参加を。

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