Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

計算量の少ない実装の例

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

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

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away