オフラインリアルタイムどう書く E24 の実装例（速いやつ）

問題 : http://nabetani.sakura.ne.jp/hena/orde24tancho/
実装リンク集 : https://qiita.com/Nabetani/items/928d6a94d83c21ef64d7

で。

腕力版 https://qiita.com/Nabetani/items/e979f3575f82916960c6 とは違って、だいぶ速いやつを。

まずは、会場で示したまあまあ速いやつ。
まあまあ速いけど、 ciel さんの示した( https://qiita.com/Nabetani/items/928d6a94d83c21ef64d7#comment-a5648154dce0a67301e4 ) 100 番目のテストデータは無理。

ruby

require "benchmark"

def inc(dig, b)
  if dig[0] < b-1
    return [dig[0]+1] + dig[1..-1]
  end
  if dig==[b-1]
    return b==2 ? nil : [2,1]
  end
  head = inc(dig[1..-1], b-1)
  return nil unless head
  [head[0]+1]+head
end

def undigits(dig, b)
  r=0
  dig.reverse.each do |d|
    r*=b
    r+=d
  end
  r
end

def nextnum( num, b )
  dig = num.digits(b)
  nn = inc( dig, b)
  nn && undigits(nn, b)
end

def impl( b, n )
  num=1
  (n-1).times do 
    num = nextnum( num, b )
    return nil unless num
  end
  num
end

def solve(src)
  b,n = src.split(",").map(&:to_i)
  impl( b, n )&.to_s(b) || "-"
end

if $0==__FILE__
  DATA.each do |s|
    num, src, expected = s.split(/\s+/)
    actual = nil;
    tick = Benchmark.realtime{ actual = solve(src) }
    res = actual == expected ? "ok" : "***NG***"
    p [ res, num, src, actual, expected, "%.3f" % tick ]
  end
end

__END__
0   16,333  38e
1   2,100   -
2   2,1 1
56  36,44811    abpu

「次の単調増加数」という計算が簡単にできるので、それで一つ一つ進めるという実装。
「次の単調増加数」は「inc」で、再帰呼び出しになっている。

ruby には digits という便利関数があって今回も役に立っているんだけど、逆関数がないのがちょっと不便というかなんでないんだよ、という感じ。

これだけだと出題者としてはちょっとしまらないので、もっと速いのを書いた。
これなら 36進数までならどんなに大きな数でも終わる。

ruby

require "benchmark"

# 階乗
def fact( n )
  return 1 if n<2
  n * fact(n-1)
end

# num 種類の数字を使った keta 桁の単調増加数の個数
def count(num, keta)
  return 0 if num<keta
  fact( num ) / fact(num-keta) / fact(keta)
end

# keta 桁の単調増加数の中で、 t+1 番目
def find( b, keta, t )
  return (t+1).to_s(36) if keta==1
  (1..(b-keta)).each do |head|
    tail_d = b - 1 - head
    c = count(tail_d, keta-1)
    if c<=t
      t-=c
    else
      tail0 = find(tail_d+1, keta-1, t)
      tail = tail0.chars.map{ |c| (c.to_i(36)+head).to_s(36) }.join
      return head.to_s(36)+tail
    end
  end
end

def impl( b, m )
  t = m-1
  (1..(b-1)).each do |keta|
    c = count( b-1, keta )
    if c<=t
      t-=c
    else
      return find( b, keta, t )
    end
  end
  nil
end


def solve(src)
  b,m = src.split(",").map(&:to_i)
  impl( b, m ) || "-"
end

DATA.each do |s|
  num, src, expected = s.split(/\s+/)
  next unless expected
  actual = nil;
  tick = Benchmark.realtime{ actual = solve(src) }
  res = actual == expected ? "ok" : "***NG***"
  p [ res, num, src, actual, expected, "%.3f" % tick ]
end

__END__
0   16,333  38e
1   2,100   -
2   2,1 1
56  36,44811    abpu
100 36,30000000000  134689bdefhijkrstuwyz

ruby なので、オーバーフローを気にしなくていいのは楽だね。36の階乗とか平気で計算できる。

戦略としては。
1. まず桁数を決める。
2. 頭の数字を決める ( find の head )
3. 残りの数字を find で決めて、頭の数字の後につなげる
という感じ。

書くまでは面倒になりそうだと思っていたんだけど、意外に短くなった。