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

問題 : http://nabetani.sakura.ne.jp/hena/orde17palin/
実装リンク集 : http://qiita.com/Nabetani/items/aa15539c8dc2c610c1a0

まずは、種類別に数える実装から：

# 0<x<m の b 進数での回文数の数
def impl( m, b )
  s=m.to_s(b)
  keta = s.size
  return m if m<=b
  shead=s[0,keta/2]
  head = shead.to_i(b)
  mids = keta.odd? ? [*0..(b-1)].map{|x| x.to_s(b)} : [""]
  # keta-1 桁までの数
  n0 = 1.upto(keta-1).sum{ |k|
    (k==1 ? 1 : b**(k/2) - b**(k/2-1)) * ( k.odd? ? b : 1 )
  }
  #keta桁の数で、前半が m の前半より小さい
  n1 = (head - b**(keta/2-1)) * mids.count
  #keta桁の数で、前半が m の前半と等しい
  n2 = mids.count{ |mid| (shead+mid+shead.reverse).to_i(b) < m }
  n1+n0+n2
end

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

if $0==__FILE__
  DATA.map{ |line|
    num, src, expected = line.split(/\s+/)
    actual = nil;
    tick = actual = solve( src )
    ok = actual==expected
    p [ ok ? "ok" : "**NG**", num, src, expected, actual, tick ]
    ok
  }.tap{ |x| p ( x.all? ? "okay" : "something wrong" ) }
end

__END__
0 12,34,5 5
1 10,11,10  0
33  2099642384,2789567569,6 14787

出題者なのにあまりきれいに書けてなくてすいません。

続いて、「次の回文数」という関数を作ることで数え上げる作戦。
テストデータを見ると 7万件を超えないようなので、間に合うだろうという算段。
当日その場で書いたもの：

def nextpa(x,b)
  s=x.to_s(b)
  keta = s.size
  shead=s[0,keta/2]
  head = shead.to_i(b)
  if keta.odd?
    smid = s[keta/2]
    mid = smid.to_i(b)
    newmid=x<(shead+smid+shead.reverse).to_i(b) ?  mid : mid+1
    if newmid<b
      return (shead+(newmid).to_s(b)+shead.reverse).to_i(b)
    else
      h=x<(shead+smid+shead.reverse).to_i(b) ?  shead : (head+1).to_s(b)
      m= shead.size<h.size ? "" : "0"
      return (h+m+h.reverse).to_i(b)
    end
  else
      h=x<(shead+shead.reverse).to_i(b) ?  shead : (head+1).to_s(b)
      if shead.size<h.size
        h="1"+"0"*(shead.size-1)
        return (h+"0"+h.reverse).to_i(b)
      else
        return (h+h.reverse).to_i(b)
      end
  end
end

def impl( x, y, b )
  x-=1
  n=0
  loop do
    x=nextpa(x,b)
    return n unless x<y
    n+=1
  end
end

def solve(src)
  x,y,b = src.split(",").map(&:to_i)
  impl( x, y, b ).to_s
end

# 以下略

こちらはさらにごちゃごちゃしている。
繰り上がりの処理で苦しんでいる感じがよく出ている。
こちらの実装は最初に挙げたものと比べるとだいぶ遅いんだけど、我慢できないほどではない。

問題はシンプルな内容だったのでどこかで既出かもと思っていたんだけど、やっぱり既出だったらしい( see http://qiita.com/cielavenir/items/ba87e17548291d63354f )

そういうこともあるよね、と思っていたけど、どうも初らしい。
そう思うと悔しいかも。