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

• 問題 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
こちらもよろしく。