Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

「長くなるように、増え続けるように」の 解説・解題

CodeIQ に「長くなるように、増え続けるように」という問題
https://codeiq.jp/ace/nabetani_takenori/q957
を出した。

挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■ 問題の概要

23342020662 のように、先頭が 1〜9 のいずれかで、 残りは 0〜9 が並んだ文字列があります。
この文字列に区切りを入れ、 値がどんどん増えていく数列 (狭義単調増加列)にすることを考えます。
上記の例の場合、たとえば
「2, 33, 420, 20662」 、 「2, 3, 3420, 20662」 、あるいは 「2334, 2020662」
のように区切ると 値がどんどん増えていく数列 にすることができます。
このように、 値がどんどん増えていく数列 になるように区切る方法はたくさんあることが多いんですが、このなかで要素数が最も多いものを探します。
この例の場合、 「2, 33, 420, 20662」 や 「2, 3, 3420, 20662」 などが、要素数 4 で最大となります。
さて。
入力文字列から、出来る限り要素数の多い 値がどんどん増えていく数列 を作ると、その要素数がいくつになるのかを計算するプログラムを書いて下さい。

■詳細な仕様

入力文字列は

  • 先頭は 1 〜 9 のいずれかの文字。
  • 先頭以外は 0 〜 9 のいずれかの文字。

という形式になっています。
つくるべき 値がどんどん増えていく数列 は、

  • どの要素も、前の要素よりも大きい値である。
  • どの要素も、先頭の文字が「0」であってはいけない。
  • 入力文字列の順序どおりに過不足なく数字が現れること。順序を変えたり余らせたりしてはいけない。

というルールを守らなくてはいけません。

■出力

出力は、最長の 値がどんどん増えていく数列 の要素数を 10進数で表記したものです。
例えば、入力が 23342020662 の場合、数列の項数を最大にするような区切り方は、例えば
「2, 33, 420, 20662」
なので、要素数の 4 を出力します。

■サンプルデータ

# 入力データ 出力の期待値 要素数が最大になる区切り方の例
0 23342020662 4 2, 3, 3420, 20662
1 23342121662 5 2, 3, 34, 212, 1662
2 2334200200662 5 2, 3, 34, 200, 200662
3 1 1 1
4 123 3 1, 2, 3
5 321 2 3, 21
6 11 1 11
7 111 2 1, 11
8 1111 2 1, 111
9 223043 3 22, 30, 43
10 33616382 4 33, 61, 63, 82
11 43727677 4 43, 72, 76, 77
12 123456789 9 1, 2, 3, 4, 5, 6, 7, 8, 9
13 987654321 3 9, 87, 654321
14 9876543210 4 9, 87, 654, 3210
15 1023456789 5 10, 23, 45, 67, 89
16 2000010000 1 2000010000
17 1000020000 2 10000, 20000
18 9080706050 2 9080, 706050
19 1222222221 4 1, 2, 222, 22221
20 1222222223 5 1, 2, 22, 222, 223
21 5463728191 5 54, 63, 72, 81, 91
22 223138576279 6 22, 31, 38, 57, 62, 79
23 9119291321331341 6 9, 119, 291, 321, 331, 341
24 123456789101112131415 15 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
25 103456789101112131415 7 10, 34, 56, 78, 910, 11121, 31415
26 100000000000000000000123456789123456789123456789 2 10000000000000000000012, 3456789123456789123456789

■ 課題
data.txt というファイルがあります。
このファイルの各行には空白区切りで

データ番号 入力データ 出力の期待値

が書かれています。
出力の期待値が間違っているデータが数件(10件以下)含まれています。
出力の期待値が間違っているデータのデータ番号を、昇順にコンマ区切りで並べたものを答えて下さい。

■補足

  • 不正な入力に対処する必要はありません。
  • 区切られた後の値が 64bit整数の最大値を超えることもあるかもしれません。オーバーフローにご注意下さい。
  • 要素数が 1 でも 値がどんどん増えていく数列 に該当します。

こんな感じ。

出題の背景と意図とか

「間違ったデータの番号を答えなさい」という形式にしようと思い、であれば覚えられる数列を区切ったものにしいようと考えた。
昇順にソートした結果を答えてもらうということにすると、問題文がすっきりする。
というわけで、覚えられる数列を、単調増加列になるように区切る必要がある。
じゃあこれ自体を問題にしよう。

という流れで問題を思いついた。

実装戦略と例

実装戦略は

の二通りがある。と思う。

wikipedia( http://ja.wikipedia.org/wiki/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95 )を見ると用語には混乱があり、メモ化つき再帰を動的計画法の一種と捉える場合と別物と捉える場合があるらしい。要注意。

ruby / 動的計画法（ボトムアップ）

# ruby 2.1.2p95

# 問題を解くクラス。
class Solver
  def initialize( src )
    @src=src.scan(/[1-9]0*/).to_a # 入力文字列を、0が先頭にならないように切ったもの
    @bests=[[]] # index 番目まで処理した結果のベスト
    @max_size = 0 # 既知の最長の要素数
    @start_index=0 # @bests のどこから調べた良いのか。
  end

  # prev を利用して(begin_ix...end_ix) 範囲の文字を末尾につけたものを、可能なら作る。
  def best_with( prev, begin_ix, end_ix )
    if prev.size+1 < @max_size
      # @bests[begin_ix] を利用しても現状より長くならないので次へ。
      # やや邪悪だけど、ここで探索範囲を更新
      @start_index = begin_ix if @start_index<begin_ix
      return nil
    end
    new_elem = @src[begin_ix...end_ix].join.to_i
    if prev.empty? || prev.last<new_elem
      prev+[new_elem]
    end
  end

  # @src[0...len] を使って要素が多いものを作る
  def element_added( len )
    (@start_index...len).inject([]){ |acc, top_of_new|
      cand = best_with( @bests[ top_of_new ], top_of_new, len )
      if cand && ( acc.size<cand.size || ( acc.size==cand.size && cand.last < acc.last ) )
        cand
      else
        acc
      end
    }
  end

  # 最短となるパターンを、配列として返す
  def solve
    1.upto(@src.size).each do |len|
      @bests[ len ] = element_added(len)
      @max_size = [ @max_size, @bests[len].size ].max
    end
    @bests[@src.size]
  end
end

# ファイルを読み、期待と実際があっているかどうか調べる
open( ARGV.empty? ? "data.txt" : ARGV.first ) do |f|
  f.each_with_object([]){ |line, fails|
    num, src, ex = line.split(/\s+/)
    actual = Solver.new(src).solve.size
    fails << num unless ex.to_i == actual
  }.tap{ |x| puts x.join(",") }
end

まず。
0 の処理が面倒なので、"1022003" を ["10","2","200","3"] のように切る。
次に。
切ったものの n 番目まで使って作れる数列で、一番良いものを @bests[n] に入れる。
一番良いものの定義は

  • できるだけ長いもの
  • 長さが同じもののなかでは、末尾の値が小さいもの

こんな感じ。
一番よいものの作り方は、

  • すでにある数列の末尾に要素を追加する。

のみ。
この時に利用する「すでにある数列」は @bests に入っているものを使うんだけど、すでにわかっている最長のものと同等以上のものが作れる時だけ計算する。

というわけで、この ruby のプログラムを手元で実行すると 1秒足らずになる。
C/C++/Google GO などで、文字列のスライスをうまく使うと 100倍ぐらい速くなるんじゃないかと思うけど、書いてない。

感想など

それほど難しくないつもりで出題したんだけど、聞こえてきた声から判断すると、やや難しかったような気がする。
計算量のことをまったく考慮しないで書くと、地球消滅までに計算が終わらなさそうなプログラムになってしまいがちなので、そこはちゃんと考えて書く必要がある。

まずはメモ化。上記の ruby でいうところの @bests がメモに当たる。
メモ化は計算量のオーダーが変わるので、何倍とかいうレベルではなく、元のコードのダメさ加減によるけど、何億倍とか、何京倍とかいう勢いで違ってくる。
そして枝刈り。探索範囲を限定することで速くなる。上記のソースでは @max_size や @start_index を使って枝刈りをしている。
この問題の場合、枝刈りでは数十倍ぐらいしか差が出ない。

誰も突っ込んでくれなかったのでここに書いておくと、正解は、円周率の小数部 でした。

最後に

次の問題製作中です。

それと。
第24回 オフラインリアルタイムどう書く( http://yhpg.doorkeeper.jp/events/13159 ) やります。8月2日(土) 横浜。
お暇とご興味のある方は是非。
ぬるいイベントなのでお気軽に。