私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「連続する数字で作る回文数」（CodeIQ）を参照してください。
与えられた整数に対して、最上位の桁から最下位の桁に向けて一桁ずつ読んでいき、同じ数字が続いている場合、「その数字」と「連続する個数」を並べるという変換を考えます。
例えば、「332111」の場合、3が2個、2が1個、1が3個連続するため、「322113」を出力します。
a 以上 b 未満の整数に対し、この変換を行って「回文数」になるものを探します。
回文数とは逆から数字を並べても同じ数になる数です。(Wikipedia：回文数)
例えば、a = 100, b = 1000 のとき、112, 211, 333はそれぞれ1221, 2112, 33となり、条件を満たします。
他にはありませんのでこの範囲には3個存在します。
標準入力から整数 n が与えられたとき、10n-1 以上 10n 未満の整数の中から、上記の変換により回文数になるものがいくつあるかを求め、標準出力に出力してください。
なお、n は 0 < n ≦ 9 を満たすものとします。
【入出力サンプル】
標準入力
3
標準出力
3
Rubyで解答しています。
#!/usr/bin/ruby $Results = [] # 実際に作っている数は正しくないが、個数を数えるには十分なはず def makeNum(n, bef, s) for i in 1..n if i == bef then next end r = n - i if r == 0 then $Results << s + i.to_s return else makeNum(r, i, s+i.to_s) end end return end # DEBUG def printResults() for r in $Results puts r + r.reverse end end def solve(n) makeNum(n, 0, "") # printResults() return $Results.size end # main while line = gets line.strip! if line.empty? then next end p solve(line.to_i) end
私のプログラムで正しい答えが求められますが、私はなぜこれで正しい答えになるのかを証明できません。Webなどで調べた結果ではなく、自分で考えた結果なのですが…。
問題を読んで法則を考えては見ましたがわからないので総当たりで途中までやって見ました。問題の通りの操作でできる回文数は次のようになります。
n=1、[11]
n=2、[22]
n=3、[1221,2112,33]
n=4、[1331,112211,3113,44]
n=5、[1441,113311,221122,2332,3223,4114,55]
これでわかるのは奇数番目か偶数番目のどちらかの数に注目した場合（ex：113311なら131、1221なら12か21）、nを順番を考慮して分割した場合にできる分割数のうち、同じ数が連続しないもののようです。
例えばn=5の場合、[1,4],[1,3,1],[2,1,2],[2,3],[3,2],[4,1],[5]が順番を考慮した分割数で同じ数が連続しないものですが、回文数の数はこれと一緒ですし、使用される数はそれぞれの分割数に含まれる数を2個ずつ使ってできます。
実際に回文数にするためには並べ方は1パターンではないのですが、答えは個数なのでこのような分割数の数を求めればできそうです。
入力値を数値に変換し、solve()に渡します。
solve()が結果を返すのでそれを印字して終わります。
引数は入力値です。
makeNum()で順番を考慮した互いに異なる分割数を作り、$Resultsに記録します。
$Resultsの要素数が答えなのでこれを返します。
順番を考慮した分割数で同じ数が連続しないものを作ります。
引数nは分割対象の数、befは1回前に使用した数、sはそれまでの分割数を文字列としてつなげたものです。
まず、1≦i≦nまでループします。
iがbefと同じなら前回と同じ数が連続することになるので無視します。
r=n-iを求め、rが0ならそれ以上分割できないので$Resultsに分割数の文字列を追加します。そうでなければmakeNum(n=r, bef=i, s=sにiを追加したもの)で再帰的に分割します。
分割できなくなったら終わります。
テストケースは全てパスしたので正しいのだとは思いますが、何でこうなるかわからないのでスッキリしません。