オフラインリアルタイムどう書く E21 の実装例

問題 : http://mtsmfm.github.io/2018/02/03/doukaku-e21.html
解答リンク集 : https://qiita.com/mtsmfm/items/b48952dee07784cce8f2

負けた。

帰宅した後でみなおして、テスト通した：

ruby

def okay( revo0, ms, bc )
  revo = revo0.dup
  rpos = mpos = 0
  dead = [false]*ms.size
  expected = ms.map{ |x| x[1] }
  states = {}
  loop do
    s = [ bc, rpos, mpos, dead, revo ].inspect
    return false if states[ s ]
    states[s] = true
    if revo[rpos]
      revo[rpos]=false
      raise "zombie!" if dead[mpos]
      dead[mpos]=true
      bc-=1
      return dead == expected if bc==0
    else
      rpos = ( rpos+ms[mpos][0] ) % revo.size
    end
    loop do
      mpos = (mpos+1) % ms.size
      break unless dead[mpos]
    end
  end
end

def solve( src )
  members, srevo = src.split("/")
  rcount = srevo.to_i
  members = members.scan( /\[\d\]|\d/ ).map{ |x| x.size==3 ? [x[1].to_i,true] : [x.to_i, false]}
  bcount = members.count{ |x| x[1]}
  [*0...rcount].combination( bcount ).flat_map{ |s|
    revo = Array.new(rcount){ |x| s.include?(x) }
    if okay( revo, members, bcount )
      [revo.map{|x| x ? ?1: ?0 }.join]
    else
      []
    end
  }.join(",")
end

TESTS=<<TESTS.freeze
/*0*/ test("3[2]3/6", "000100");
/*1*/ test("21[3]/6", "000100");
/*2*/ test("12[3]/6", "000100");
/*29*/ test("[7][6][5]54[5]8[5]53[8]1/15", "010001110010001");
TESTS

$stdout.sync=true

TESTS.scan( /(\d+)\*\/\s*test\("([^\"]+)",\s*"([^\"]+)"\)/ ).to_a.drop(0).map{ |num, src, expected|
  actual = solve( src )
  okay = actual == expected
  p [ num, (okay ? "ok" : "**NG**" ), src, actual, expected ]
  okay
}.all?.tap{ |x| puts( x ? "okay" : "something wrong" ) }

実装戦略は 男装の状態を……いや、そうじゃなくて、弾倉の状態を全探索。

敗因は、ひとえに精進不足。反省。

実行すると、手元で 7秒ほどかかる。遅い。