第23回オフラインリアルタイムどう書く「くねくね増加列」の実装例と若干の解題 #Ruby

問題 http://nabetani.sakura.ne.jp/hena/ord23snakemoinc/
解答リンク集 http://qiita.com/Nabetani/items/7ba11167ea28c929fcf2
イベント http://yhpg.doorkeeper.jp/events/12339

計算量の少ない実装の例

まずは、問題作成用に書いたもの。

# ruby 2.1.2p95
def solve(s)
  cells=["/"]*6+s.chars+["/"]*6 # "/" は番兵
  (?0..?9).each.with_object( {} ){ |digit, length|
    cells.size.times do |pos|
      next unless cells[pos]==digit
      neis=[-6,-1,1, 6]
        .map{ |d| d+pos }
        .flat_map{ |x|
          c=cells[x]
          /\d/===c && c < digit ? [length[x]] : []
        }
      length[pos] = ( neis + [0] ).max + 1
    end
  }.values.max.to_s
end

$stdout.sync=true
DATA.map do |line|
  num, src, exp = line.split(/\s+/)
  actual = solve( src )
  ok = actual==exp
  p [ num, src, exp, actual ] unless ok
  ok
end.all?{ |x| x }.tap{ |x| p x }

__END__
0 01224/82925/69076/32298/21065 6
1 03478/12569/03478/12569/03478 10
2 09900/28127/87036/76545/87650 10
50  02489/77571/84873/03879/84460 7

再帰しない動的計画法で、マス目の数字が小さいものから順に処理する。
cells=["/"]*6+s.chars+["/"]*6 # "/" は番兵
とある部分は邪悪な感じだけど

もともと入力にある / を左右の番兵として活かす。
上下に番兵がいないので、["/"]*6 で追加する。

ということ。
each_with_index のなかの times のなかの flat_map のなかに 〜?〜:〜 があって、ちょっとよろしくない感じ。

計算量を気にしない実装の例

一方。
次にお見せするのは当日書いたもの。

# ruby 2.1.2p95
def max_len( s, pos )
  cur = s[pos]
  cx, cy = pos.divmod 5
  neipos = [[-1,0],[1,0],[0,-1],[0,1]].map{ |dx,dy|
    x = cx+dx
    y = cy+dy
    (0...5)===x && (0...5)===y ? x*5+y : nil
  }.select{ |x| x && cur<s[x] }
  1+( neipos.map{ |x| max_len( s, x ) }.max || 0 )
end

def solve(s0)
  s = s0.scan( /\w/ ).to_a
  25.times.map{ |pos|
    max_len(s,pos)
  }.max.to_s
end

$stdout.sync=true
DATA.map do |line|
  num, src, exp = line.split(/\s+/)
  actual = solve( src )
  ok = actual==exp
  p [ num, src, exp, actual ] unless ok
  ok
end.all?{ |x| x }.tap{ |x| p x }

__END__
0 01224/82925/69076/32298/21065 6
1 03478/12569/03478/12569/03478 10
2 09900/28127/87036/76545/87650 10
50  02489/77571/84873/03879/84460 7

こちらは再帰呼び出しによる深さ優先探索。
メモ化も何もせずに全探索。

計算量のオーダーとしてはひどいものだと思うけど、5×5 とわかっているのでこれでよい。

[ ].max は nil なので、
(array.max || 0) は、array が空っぽなら 0、array の中身があったら最大値。
という計算になる。|| は便利だね。

解題

前回( http://nabetani.sakura.ne.jp/hena/ord22irrpas/ )はメモ化つき再帰だったので、今回はメモ化つき再帰じゃない方の動的計画法と思って出題したつもり。

今回の問題をメモ化つき再帰で書くことはできるし、前回の問題をメモ化つき再帰じゃない方の動的計画法で書くこともできるけどね。

宣伝

CodeIQ にも、狭義単調増加列にからめた問題を出してます。
https://codeiq.jp/ace/nabetani_takenori/q957
こちらもよろしく。