単調非減少と単調非増加で配列(Enumerator)を切断する
要するにこれです。
atcoder.jp
配列 A が与えられます。 A を何箇所かで切って、A の連続した部分であるようないくつかの数列に分けます。 この時、分けられたあとの数列は全て、単調非減少または単調非増加な列になっている必要があります。
コード
Enumerable にこんなメソッドupdown_cut
を生やしてみました。
module Enumerable def updown_cut e = to_enum updown = 0 calc = ->(compare) { case updown when 0 then [compare, false] when -1 case compare when -1, 0 then [-1, false] else [0, true] end else case compare when 1, 0 then [1, false] else [0, true] end end } begin a = e.next rescue StopIteration return self end pool = [a] loop do b = e.next updown, f = calc.(a <=> b) a = b if f yield pool pool = [a] else pool << a end end yield pool self end end
使い方
配列(あるいは Enumerator)を単調非減少、あるいは単調非増加な配列になるよう切ってくれます。切られた配列はブロック変数に入ります。
[1, 2, 3, 2, 2, 1].updown_cut { p _1 } #=> #[1, 2, 3] #[2, 2, 1] ary = ([*1..7] * 2).shuffle #=>[3, 1, 2, 7, 6, 7, 6, 5, 1, 5, 4, 4, 3, 2] ary.enum_for(:updown_cut).to_a #=>[[3, 1], [2, 7], [6, 7], [6, 5, 1], [5, 4, 4, 3, 2]] str = ("abcdef" * 4).chars.shuffle.join #=>"ecfdedcfecbabbbadfadcaef" str.each_char.enum_for(:updown_cut).map(&:join) #=>["ec", "fd", "edc", "fecba", "bbba", "df", "ad", "ca", "ef"]
いやあ、苦労しました。