私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「140問目！素数列から抜き出してつぶやこう？」（CodeIQ）を参照してください。
今週のアルゴリズムも140問目！
「140」といえばTwitterにおけるつぶやきの文字数の上限です。
m 以上 n 以下の素数を一列に並べ、その中から連続した数字列を最長140文字で抜き出したとき、最初と最後の数字が同じで、含まれる数の和が最大になるものを求め、その和を出力してください。
例えば、m = 5, n = 30 のとき、
57111317192329
という数字列の中から、最初と最後の数字が同じで、長いものを抜き出すと、含まれる数の和は
7111317 → 21
1113171 → 15
3171923 → 26
92329 → 25
232 → 7
となりますので、最大なのは26です。
標準入力から m と n がスペース区切りで与えられるとき、和の最大値を求め、標準出力に出力してください。
なお、m と n は 1 < m < n < 100000を満たす整数とします。
【入出力サンプル】
標準入力
5 30
標準出力
26
Rubyで解答しています。
#!/usr/bin/ruby
require 'prime'
def makeNum(m,n)
ret = ""
Prime.each(n){|i|
next if i < m
ret += i.to_s
}
return ret.split("").map{|a| a.to_i}
end
def solve(m,n)
full = makeNum(m,n)
mx = 0
for i in 0...full.size
pos = full[i,140].rindex(full[i])
# printf("%s, find=%d, pos=%d\n", full[i,140].to_s, full[i], pos)
next if pos == 0
num = full[i, pos+1]
# p num
s = num.reduce(:+)
mx = s if s > mx
end
return mx
end
# main
while line = gets
line.strip!
if line.empty? then next end
m,n = line.split.map{|a| a.to_i}
p solve(m,n)
end
今回はメモ化再帰ではありません。
うまい方法が思いつかなかったので総当たりです。
入力値を数値にしてsolve()に渡し、結果を印字します。
makeNum()でm以上n以下の素数を繋げた数字列（配列）fullを取得します。
fullの先頭から最後の一つ前までを開始位置として順番にチェックします。最後の一つ手前までなのは「連続した数」が評価対象なので数字1つだけの場合はチェックしなくて良いからです。
posはi番目を先頭とした時にi+140番目から手前に向かってi番目の数と同じ値が最初に出現する位置です。これはArray#rindex()で単純に探索しています。
pos=0の場合、つまり先頭まで同じ数がなかった場合は評価対象にならないので無視します。
そうでなければその間の値の合計を求めます。num=full[i,pos+1]と1足しているのはpos = full[i,140].rindex(full[i])が返すのがiの場所を0とした場合のインデックスなので要素数の場合+1する必要があるためです。例えば[1,2,1]だとインデックスは2が返りますが、要素数は3になるということです。
あとは合計値が過去の合計値より大きければその値を候補値として記録し、最後までチェックした時に残った候補値が答えになります。
m以上n以下の素数を繋げた数字列を作成して返します。
Rubyには素数ライブラリがあるので簡単です。
一旦文字列で連結してから数値の配列に変換しています。
これ、もっと効率の良い方法はあるのでしょうか？
140個までという条件が以外に面倒で総当たりより良い方法を思いつきませんでした。