オフラインリアルタイムどう書く E22 の実装例

問題 : http://nabetani.sakura.ne.jp/hena/orde22numord/
解答リンク集 : https://qiita.com/Nabetani/items/99e38a39165e1905b415

正直言って、難しすぎるかとも思っていたんだけど、きっともっと簡単な解法があるに違いないとも思っていて、そんな感じで出してみたこの問題。
今のところ思いがけない簡単な解法はなく、やっぱり難しかった模様。

ナイーブじゃない実装の方針はいくつかあると思うんだけど、私が思いついたのは下記のようなものだけ。

ruby2.5

# kc の範囲の数が digit より前に何件あるか。b進数。
def order_at( kc, digit, b )
  kc.sum{ |min, max|
    smin, smax = [min,max].map{ |m| m.to_s(b) }
    next 0 if digit <= smin
    next max-min+1 if smax < digit
    ( digit+"0"*100 )[0,smin.size].to_i(b) - min + ( digit.size<=smin.size ? 0 : 1 )
  }
end

# b 進数、kc の範囲の数で、 ord 番目の数の b 進数表現 を返す。
# min と max の間。頭は digit であるらしい。
def find( b, kc, digit, ord, min, max )
  val = digit.to_i(b)
  lo = order_at( kc, digit, b )
  return nil if ord<lo
  return digit if ! digit.empty? && lo==ord && min<=val && val<=max
  return nil if max.to_s(b).size<digit.size
  hi = order_at( kc, digit + (b-1).to_s(b)*100, b )
  return nil if hi<ord
  (0...b).inject(nil) do |acc, n|
    if digit.empty? && n==0
      acc
    else
      acc || find( b, kc, digit+n.to_s(b), ord, min, max )
    end
  end
end

def solve_impl(m,n,b,x)
  ketamin, ketamax = [m,n].map{ |e| e.to_s(b).size }
  kc = (ketamin..ketamax).map{ |k|
    nmin=[m,b**(k-1)].max
    nmax=[n,b**k-1].min
    nmin<=nmax ? [nmin, nmax] : nil
  }.compact
  find( b, kc, "", x-1, m, n )
end

def solve(src)
  m,n,b,x = src.split(",").map(&:to_i)
  solve_impl(m,n,b,x).to_i(b).to_s
end

DATA.map{ |line|
  num, src, expected = line.split(/\s+/)
  actual = solve(src)
  okay = actual == expected
  puts [ (okay ? "ok" : "**NG**" ), src, actual, expected].join(", ")
  okay
}.all?.tap{ |o| puts( o ? "okay" : "something wrong" ) }

__END__
0 2,15,3,8  14
1 6,8,8,1 8
2 6,6,5,1 6
3 4,11,5,2  6
35  26065964,66252692,18,29196596 63208819
36  66097362,104618756,16,32740764  98838125

先頭の桁から順に決めていくという戦略。
この戦略は、上記の「order_at」が割りと簡単に実装できることに依拠している。

まあでも難しいよね。ちょっと反省している。

それと。 Tweet したとおり、問題がシンプルなので既出じゃないかと疑っている。どうだろう。

ちなみに。
次回は明日（3/7 水) で、F10。こちらの問題はだいぶ簡単。
その次は 4/7 土 で、E23。こちらは作問未着手。
御用とお急ぎでなければ是非おいでください。