CodeIQ：回文数の中央値

問題の概要

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# 桁数    0   一  十   百   千     万   十万    百万   千万     一億    十億      百億     千億       一兆       十兆       百兆
Counts = [0, 10, 19, 109, 199, 1099, 1999, 10999, 19999, 109999, 199999, 1099999, 1999999, 10999999, 19999999, 109999999]

# 回分数かどうかチェックする
def isKaibun(n)
	s = n.to_s
	r  = s.size-1

	for i in 0..(r/2)
#		printf("%s, %s\n", s[i], s[r-i])
		return false if s[i] != s[r-i]
	end
	return true
end

# r桁のn番目の回分数を求める
def getKaibun(n, r)
	return n-1 if r == 1

	s = (n-1).to_s

	if (r % 2) == 0 then s += s.reverse
	else s += s[0..-2].reverse
	end

	while s.size < r
		s = '0' + s + '0'
	end

	return s.to_i + 10**(r-1) + 1
end

# 引数以下の最大の回分数がその桁の何番目かを返す
# 0は1番目
def getIndexOfKaibun(n)
	r = n.to_s.size
	return n+1 if r == 1

	base = 10**(r-1) + 1
	ret = (n - base) / (10**(r/2))

	loop{
		v = getKaibun(ret+1, r)
#		printf("n=%d, v=%d, ret=%d\n", n, v, ret)
		if v <= n then break
		else ret -= 1
		end
	}

	return ret + 1
end

# 何桁の何番目の回分数かを求める
def search(idx)
	for i in 1...Counts.size
		return [i, idx-Counts[i-1]] if (Counts[i-1] < idx) && (idx <= Counts[i])
	end
end

# 問題を解く
def solve(mn, mx)
	mx = 999999999999999 if mx > 999999999999999

	# 入力値の範囲にある回分数の最小と最大のインデックスを決める
	r_min = mn.to_s.size
	i_min_of_r = getIndexOfKaibun(mn)

	r_max = mx.to_s.size
	i_max_of_r = getIndexOfKaibun(mx)

	# 全体で何番目か？
	i_min = Counts[r_min-1] + i_min_of_r
	i_max = Counts[r_max-1] + i_max_of_r

	# 範囲内に値が無い
	return "-" if i_max < i_min

#	printf("i_min_of_r=%d, i_max_of_r=%d, i_min=%d, i_max=%d\n", i_min_of_r, i_max_of_r, i_min, i_max)
#	p getKaibun(i_min_of_r, r_min)
#	p getKaibun(i_max_of_r, r_max)

	# 範囲内の個数を求める
	if isKaibun(mn) then
		# mnが回分数の場合、mnが範囲内に含まれる
		cnt = i_max - i_min + 1
		if (cnt) % 2 == 1 then target = [(i_max + i_min)/2]
		else target = [(i_max + i_min)/2, (i_max + i_min)/2+1]
		end
#		printf("mn=Kaibun: cnt=%d target=%s\n", cnt, target.to_s)
	else
		# mnが回分数でない場合、mnは範囲に含まれない
		cnt = i_max - i_min
		if (cnt) % 2 == 1 then target = [(i_max + i_min)/2+1]
		else target = [(i_max + i_min)/2, (i_max + i_min)/2+1]
		end
#		printf("mn!=Kaibun: cnt=%d target=%s\n", cnt, target.to_s)
	end


	ret = []
	for t in target
		r, pos = search(t)
#		printf("r=%d, pos=%s\n", r, pos)
		ret << getKaibun(pos, r)
	end

	if (ret.size == 2) && ((ret[0] < mn) || (mx < ret[1])) then return '-'
	elsif (ret.size == 1) && ((ret[0] < mn) || (mx < ret[0])) then return '-'
	else return ret.join(',')
	end
end

# main
while line = gets
	line.strip!
	next if line.empty?

	mn, mx = line.split(',').map{|a| a.to_i}

	puts solve(mn, mx)
end

解説

★★★の問題です。かなり難しいと思います。

雑感

非常に難しい問題でした。
入力値からそれ以下の回分数が何番目かを求めて、下限と上限の真ん中の番号の回分数を求めれば良いというのはすぐに思いついてのですが、何番目の回分数かを求める、何番目という情報から該当する回分数を求める方法がわからず苦労しました（"回分数 性質"で検索しましたが有用な情報を見つけられなかった）。
ブレークスルーは回分数を作る方法を考えていた時にn番目はnとnを反転した文字列を連結して10…01を足せば良いことに気づいたことで、これによって何番目の回分数かを求めるのも容易にできるようになったことでした（最初はもっとゴチャゴチャした方法でやっていた）。
この出題者の問題は例が詳しいので正答率が高い（挑戦者数とバッジ獲得数が近い）のですが、私が正解した時点で50%くらいしかない状態で、かなり難しい問題だったようです。