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

yhpg

はじめに

2016/12/3開催の「オフラインリアルタイムどう書くE10」、残念ながら所用で行けなかったのですが、オンラインで参加し問題を解きましたので、その解説です。

問題

今回は松島さん作成の塗って繋ぐでした。

入力文字列の一文字を一手として正方形のマスを3×3に分割していき、黒マスだった所を白黒塗り分けて行く時に、最終的に白マス同士で繋がっている塊が何個あるかを数えるものです。
塗り分けは市松模様ですが、文字によって2通り ( O なら黒が×型、X なら白が×型 ) に分かれます。

詳細は上のリンクから問題ページをご覧ください。

解説

方針-前半

最初はどうやって攻めるか悩ましかったのですが、あることに気付き、特定のパターンから整理していきました。

それは、X で終わる場合です。
途中までは複雑に黒マスが分離していくのですが、最後につぼみが花開くように各黒マスが、それぞれ白1マスを囲むようになります。
しかも、それまで様々に盤面を区切っていたところがあらかた解放され、全体が繋がってしまいます。

f:id:ange1:20161205013652p:plain

ということは、最後の X の前までにできた黒マスの数に+1してやれば答えになると言えます。X が現れる度に黒マスは4倍、O が現れる毎に5倍になることから、黒マスの数は決定できます。

ただし例外に注意する必要があります。それはずっと O のみで来て、最後に X になるパターンです。
この場合、四隅がずっと黒マスで来ているので、最後に隅に閉じ込められた白マスができるのです。そのため、+1 ではなく +5 になります。

f:id:ange1:20161205013840p:plain

ここまで整理した段階で、X で終わる約半数のケースが通ることになります。( 実際通すことができて途中でtweetしてたりします )

方針-後半

では、最後が X ではなく O の場合どうなるのでしょうか。

実は、O で終わるケースで試しに末尾の O を全て取り去って X で終わるようにし、出力と想定値を比較してみると、4,8や、はたまた12等、2のべき絡みのそれほど大きくない数が差として現れます。

ということは、末尾の O は倍率として効いてくるというより、X で終わったところから何らかの差分を与える効果を持つと推測できます。
そこからもう少し精査してみます。

次の図のように、X に続いて最後に O が来る場合を考えてみます。そうすると、黒4マスで囲まれていた部分 ( 図中ピンクの丸 ) は、依然黒に囲まれたままですが、盤面の端に新たに囲まれている部分ができています ( 図中赤の丸 )。

f:id:ange1:20161205015746p:plain

ということは、実はこれこそが差分の正体なのではないでしょうか。では、この端にできた1マスの白が、O を重ねる毎にどう変化するかを見ていきます。

f:id:ange1:20161205020307p:plain

そうすると、端の黒マスが倍々に増えていくに従って、その分囲まれた白マスができていくことになります。つまり、これは公比 2 の等比数列の和として数えることができるのです。

端の黒マスというのは、最後の O の塊の前の話ですが、これまた O によって倍々に増えていくところから計算することができます。

実装

ここまでをまとめます。

  • 最後の X までで
    • それまで分裂した黒マス ( X で4倍、O で5倍 ) の数の分、白の塊ができる
    • それ以外に中央の大きな塊が1つできる
    • ただし例外的に、ずっと O のみで来て X となった場合は、更に隅に4つ塊ができる
  • 最後の O の塊では
    • 端の黒マス1個につき、公比 2 の等比数列の和 ( 項数は最後の O の数 ) の分塊ができる
    • 端の黒マスは、最後の X より前の O 1個につき倍になる

なお、初期状態で実際には黒マス1個しかありませんが、4辺の端全てに効いているため、端の黒マス4個と同じと見做すことができます。

後、これまで話に出てきませんでしたが、X が一切ない場合や、1文字目に X が来た後ずっと O のパターンは上の計算から微妙にズレますから、補正が必要になります。

ということで実装です。整理したコードより、主要部分を抜粋します。なお、最初の t の計算が上の話で出てきた等比数列の和になっています。

def solve!(input)
  input.sub!(/O*$/,'')
  t=2**$&.size-1
  oc,xc=%W(O X).map{|c|input.count(c)}
  t*4*2**oc+(
    xc==0 ? 0 : xc==1 ? 5+( oc==0 ? 0 : 5**oc ) : 1+4**(xc-1)*5**oc
  )
end

終わりに

文字数が多くなっていくとどんどん盤面が細かくなっていくため、考えがなかなかまとまらず悩まされました。会場ではどのように攻めていく方法が出てきたのか気になるところです。