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

yhpg

はじめに

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

どんな感じ?

今回は鍋谷さん出題の回です。ぱっと見そんなに苦労しないかな…と思ったのですが、ちゃんと全完するには結構条件を煮詰めていかないといけないという難しめの問題でした。

時間内に解けたのはしえるさんのみ。私はロスタイム内でなんとか、というところでした。

問題

問題は7セグパネルがよく見えないでした。概要は次の通りです。

  • 1桁あたり7か所のランプにつき、点灯・非点灯・不明の状態が与えられるとき、表示されている可能性のある数値の中で最小値と最大値を調べる。
  • 数字は右詰めである。先頭 ( 左端 ) から連続する桁についてはブランク ( 7か所全て非点灯 ) となっても良い。ただし、数字の表示されている桁以降のブランクおよび、最後 ( 右端 ) の桁のブランクは不可。
  • 最初の数字桁として 0 は不可。ただし、0 のみの1桁の数字は良い。
  • 入力は、06:4b:46:64:6d,79:20:10:10:02のように、コロン区切りの16進数のかたまり2組をカンマ区切りとしたもの。前半は各桁のランプの点灯箇所を、後半は非点灯箇所を、それぞれ7bitの数値にエンコードしたものを表す。
    ※bitの対応、数字毎の点灯パターンについては、上のリンク先をご覧ください。
  • 出力は、最小値と最大値をカンマ区切りとした文字列。ただし、表示されている可能性のある数値が全くない場合は“-”を出力する。

解説

方針:前半

まずは、与えられた点灯・非点灯パターンから、各桁の候補を調べる必要があります。

…が、これは実は気付けば一発だったりします。なぜかというと、ある数字が候補に含まれるかどうかは、

  • 桁の点灯箇所がその数字の点灯パターンに含まれる ( はみ出さない )
  • 桁の非点灯箇所がその数字の点灯パターンと交わらない

の両方を満たすかどうかを調べれば良いからです。
つまり、点灯箇所を bon、非点灯箇所を boff、数字の点灯パターンを bp とすると、

  • (bon&~bp==0)&&(boff&bp==0)

というbit演算によって調べることができます。

なお、ブランクが候補に入っているかどうかは、単純にbon==0です。これは、bp=0とした時の上の式と同じことです。

方針:後半

で。各桁の候補さえわかれば、先頭の桁から順に見て行って、最大の数字を選び続けて最大値、ブランクまたは最小の数字を選び続けて最小値が作れるかな…と思ったのですが。そうは単純にいかないのが、この問題の難しいところでした。

その原因は、ブランクと 0 の特殊性です。ざっと挙げると、

  • ある桁の候補がブランクしかない場合、以前の桁は全てブランクにしなければならない。
    → 最大値のために、折角先頭から最大の数字を選んできていても、ブランクのみの桁が現れた時点で全て破棄しなければならない
  • 最初の数字桁は ( 最後の桁の場合を除き ) 0 であってはならない。
    → 最小値のために、折角先頭からブランクを選んできていても、0 しか選べない桁が出たら、ブランク以外を選び直さなければならない

というところが大きく引っかかってきます。

そこで、先頭から見ていく際に、最大値・最小値だけでなく、もう2つ、仮/本フラグ、次点最小値を設けて状態遷移を管理することにしました。状態遷移で組む癖がついているのは、Brainf**kを書いているためですね。

具体的には次のようにします。
※ただし、最後の桁に限っては、「ブランク不可」「0可」なので、単純に最大・最小を考えるだけで済みます。なので、最後の桁は省いて考えます。

  • ブランクが選択可能な限り、「仮」状態とし、最小値は「全てブランク選択」としておく
  • ブランクが選択不可能な桁が出たら「本」状態とする。それ以降は単純に最大・最小の数字を選び続ける ( ブランクは選択できないため、ブランクのみの桁が出たら「候補なし」が確定する )。
  • 最大値としては先頭から最大の数字を選び続けるが、ブランクのみの桁が出たら最大値を破棄する。
  • 最大値のない状態で 0 のみの桁が現れた場合、先頭に 0 は持ってこれないので「候補なし」が確定する。
  • 次点最小値は、「『仮』状態の時に、最後に選んだ桁がブランクでない最小値」とする ( 「本」状態になった後は次点最小値を管理する意味はなくなる )。
  • 「仮」状態で、0のみの桁が現れた場合、( ブランクの次に0は不可であるため ) 次点最小値を最小値に繰り上げたうえで 0 を選択する。ただし、次点最小値が存在しない場合は「候補なし」が確定する。
    ※なお「仮」状態で、ブランクなし・0以外の数字ありの桁が出た場合、繰り上げは行わず、最小値には 0 以外の最小の数字を選択する
  • 「仮」状態でブランク選択可能な桁が出た場合の次点最小値の扱いは、
    • 選択できる数字がない場合、次点最小値を破棄する
    • 0 以外の数字を選択できる場合、次点最小値を一旦破棄し、0以外の最小の数字を選択する
    • 数字として 0 のみ選択可能で次点最小値が存在する場合、0 を選択する
    • 数字として 0 のみ選択可能で次点最小値が存在しない場合、依然、次点最小値はなしのままとする。
      ※数字のパターン的に、ブランク・0 のみ可能というのはないのですが…。一応。

こんだけ書いてみてもなんというかややこしいところですが。一応これで網羅できているはずです。

実装

会場で組んだコードはコレだったのですが、潜在バグ ( ただし顕在化はしない ) もあって気持ち悪かったので、同じ方針で組み直しました。

これなら結構すっきりしてるんではないでしょうか。

終わりに

鍋谷さんの発表で「0から99…(桁数分)まで回して作れる数を抽出して、そこからminmaxを取る」と言われて、時間はかかるけどそれなら紛れがないよなあ、とハッとさせられました。
さて。今回は都合で懇親会の方に行けなかったので、次回参加時は行きたいと思います。