オフラインリアルタイムどう書く E24 の回答

負けました。ほっとんどのテストケースは通るが4つほど通らない、というのがあるというのが時間内の回答です。

が、終わったあとの懇親会でぼーっと考えてたらあそこじゃね？というところに気づいて解けました。そしてその diff がしょーもない。

とりあえず方針はこんな感じです。

単調増加数は各桁に一定の大小関係があるので、桁間で「いくつプラスになるか」というのを割り振るものだと思えばよい。
この捉え方だとある桁数・進数における単調増加数のパターン数をよくある場合の数に落とせる。具体的には、 b-1個のボール(増加分)をr人(桁数)で分けるような何かである。

↓こんな感じ。

5個のボールを2つの仕切りでわける = 4進数2桁における単調増加数のパターン数

こういうマッピングができる
○|○|○○○ -> 12 (5)
○|○○|○○ -> 13 (5)
○○|○○|○ -> 24 (5)

これは nCk で表わせる場合の数である。

これを使うと b 進数 r 桁で表せる単調増加数のパターン数がわかるので m を超えないような最大の r で桁数が確定。次は r 桁のうち idx 番目を num にしたときの単調増加数のパターン数を調べていって桁を確定させると求める数がわかる。

実行速度はたぶんかなりはやい気がします。

$ ruby test.rb
(略)
ruby test.rb  0.43s user 0.18s system 74% cpu 0.818 total

回答のコードは以下

class Solver
  def solve(input)
    @b, @m = input.split(',').map(&:to_i)
    rank = 1
    count = 0


    loop do
      return '-' if rank > (@b - 1)
      # rank 個の仕切りを n - 1 箇所にいれればよい
      # rank 末尾と n の末尾になんか変なのいれてることに注意
      # → nCrankでよい
      tmp = count_for(n: @b - 1, k: rank)
      break if count + tmp >= @m
      count += tmp
      rank += 1
    end
    # 桁数確定

    idx = 1
    num = 1
    nums = []

    loop do
      t_n = @b - 1 - num
      t_k = rank - idx
      tmp = count_for(n: t_n, k: t_k)
      if count + tmp >= @m
        nums << num
        num += 1
        idx += 1
        break if nums.size == rank
        next
      end
      count += tmp
      num += 1
    end

    nums.map { |e| e.to_s(36) }.join('')
  end

  def count_for(n:, k:)
    raise ArgumentError if k > n

    ret = 1
    k.times do |i|
      ret = ret * (n - i)
    end
    k.times do |i|
      ret = ret / (k - i)
    end
    ret.to_i
  end

  def incr?(num)
    tmp = num.to_s(@b).chars
    return true if tmp.size == 1
    tmp.each_cons(2).all? do |c1, c2|
      c1 < c2
    end
  end
end

なお最終コミットはこちらです ↓

fix · hkdnet/misc@2efdfd7 · GitHub

ほんとしょうもない……。