私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「連続する桁の数字で作る平方数」（CodeIQ）を参照してください。
クレジットカード番号のような16桁の数字を考えます。
この中から連続する何桁かの数字をうまく取り出すと、それらの数字の積が平方数にできることが知られています。
例えば、4があればその桁だけを取り出せば4は平方数ですし、28があれば「2×8＝16」なので平方数、2323のように並んでいれば、「2×3×2×3＝36」なので平方数です。
2477 6537 2835 2323
標準入力から平方数 n が入力されたとき、上記のように連続する何桁かの数字を取り出して、それらの数字の積が n になるような取り出し方のうち、取り出した桁をすべて使わないと平方数を作れないものが何通りあるかを標準出力に出力してください。
例えば、n=16のとき、「44」はいずれか1桁だけ取り出しても平方数になりますし、「2222」はいずれか2桁を取り出すと平方数になりますので、「28」と「82」の2通りが残ります。
【入出力サンプル】
標準入力
16標準出力
2
Rubyで解答しています。
#!/usr/bin/ruby
require 'prime'
$Heihosu = {16=>true, 36=>true, 144=>true, 100=>true, 400=>true, 196=>true, 784=>true, 225=>true, 324=>true, 441=>true, 900=>true, 1225=>true, 1764=>true, 3600=>true, 7056=>true, 4900=>true, 19600=>true, 8100=>true, 11025=>true, 15876=>true, 44100=>true, 32400=>true, 63504=>true, 176400=>true, 396900=>true, 99225=>true}
class Nums
attr_reader :lst, :muls
def initialize(n, lst, primes, muls)
@goal = n
@lst = lst
@primes = primes
@muls = muls
end
def checkMuls(muls, n)
nxt = []
for m in muls
v = m*n
if $Heihosu.include?(v) && (v != @goal) then return nil
else nxt << v
end
# h = Math.sqrt(v).floor
# if (h*h == v) && (v != @goal) then
# $Heihosu << v
# return nil
# else
# nxt << v
# end
end
nxt << n
end
def getNext()
nxts = [2,3,5,6,7,8]
ret = []
for n in nxts
primes = @primes.dup
if n == 6 then
primes[2] -= 1
primes[3] -= 1
if (primes[2] < 0) || (primes[3] < 0) then next end
elsif n == 8 then
primes[2] -= 3
if primes[2] < 0 then next end
else
primes[n] -= 1
if primes[n] < 0 then next end
end
if @lst.last == n then next end
muls = checkMuls(@muls, n)
if muls == nil then next end
lst = @lst + [n]
ret << Nums.new(@goal, lst, primes, muls)
end
return ret
end
end
def divide2Primes(n)
ret = {
2=>0,
3=>0,
5=>0,
7=>0
}
for ps in Prime.prime_division(n)
ret[ps[0]] = ps[1]
end
return ret
end
def solve(n)
if (n == 0) || (n == 1) then return 1 end
primes = divide2Primes(n)
ret = 0
queue = [Nums.new(n, [], primes, [])]
while !queue.empty?
v = queue.shift
lst = v.getNext()
for l in lst
if l.muls[0] == n then ret += 1
else queue << l
end
end
end
return ret
end
# main
while line = gets
line.strip!
if line.empty? then next end
n = line.to_i
p solve(n)
end
この問題もかなり難しいです。この1週間あまりの問題は★★の評価は低すぎると思います。
また、問題の説明がわかりにくいです。
わかりやすくすると次の様になるでしょうか？
まず、nを素因数分解します。
問題で求める数列の積がnなのでnの素因数の積で現わせるはずです。
なので、素因数から任意の数を順番に選び、その途中の結果が平方数にならなければ良いというのが基本です。
ただし、素因数の順列では答えになりません。なぜなら6と8を含む数列もありえるからです。
なので、数列を作るのには素因数を取り出すのではなく[2,3,5,6,7,8]から任意の数を選び、素因数から使った数を引くという風にします。6の時は2と3を1個ずつ、8の時は2を3つ減らします。
4と9はそれ自体が平方数なので取り出す数には含めません。
それから、数列の部分で平方数を作れないかのチェックに一工夫いります。
これはコードの解説で説明します。
数列を保持するクラスです。
同時に、部分が平方数にならないかをチェックするため途中までの計算結果も保持します。
メンバ変数は次の通りです。
@goal：入力値n
@lst：数列
@primes：nの素因数のうち数列に使った残り
@muls：数列の任意の位置から最後の数までの積。例えば@lst=[2,3,5]なら@muls=[2*3*5, 3*5, 5]。
途中の結果に平方数が含まれないことをチェックします。
この関数でズルをしていて、平方数かどうかをチェックするために計算せず定数$Heihosuを用いています。コメントアウトしてある部分が計算で求める場合（の単純な方法）ですが、これだと時間が微妙だったのでテストケースの範囲で登場する平方数を定数化してしまいました。
引数mulsは一つ前のmulsでnは新たに追加される数です。例えば数列[2,3]に5を追加した場合にどうかというチェックをする場合、muls=[6(=2*3),3]、n=5が渡ってきます。
そして、6*5と3*5がそれぞれ平方数かどうかをチェックし、平方数ならnilを平方数でなければ[30(=2*3*5), 15(=3*5), 5]を返します。
最終的な数列に対してチェックする場合は任意の場所から連続した任意の数（ただし、全体を除く）を計算しなければなりませんが、都度計算しておけばこの方法で網羅できます。
現在の数列に新しく1つ数を加えて、その部分に平方数を含まない数列のリストを返します。
nxtsは数列に加える候補の数のリストです。なぜ[2,3,5,6,7,8]かは考え方に書いた通りです。
nxtsの候補すべてに対して付け加えられるかをチェックします（40〜62行目）。
@primesから候補の数を削除します（42〜52行目）。考え方に書いた通り6の場合は2と3を、8の場合は2を3個減らします。減らした結果、その素因数が0未満になったらその数は使えないので無視します。
次に直前の数と同じ数の場合は必ず平方数になるので無視します（54行目）。
そして、途中の結果に平方数がないことをcheck()で確認します（56〜57行目）。
このまでのチェックにパスしたものを数列に追加し、新しいインスタンスを作ります。
最終的にチェックを通った数列のリストを返します。
標準入力の数を素因数分解し、連想配列にして返します。
素因数分解はPrime.prime_division()でできます。
結果を連想配列にしているのは数を取り出す際の検索時間を少しでも早くするためです。
問題を解きます。
n=0,1の場合は結果が1つしかないし、これまで説明したロジックでは扱わない数になるので最初にチェックして返してしまいます（82行目）。
入力値を素因数分解し（84行目）、queueに初期値（引数はn=入力値, lst=[]、primes=素因数分解の結果、muls=[]）を登録します（87行目）。
queueがからになるまで（89〜97行目）、数列に数を1つずつ加えて新しい数列を生成します（90〜91行目）。
もし、生成した数列の@muls[0]が入力値に等しかったら答えのうち1パターンなので結果をカウントします。そうでなければqueueに追加して次の候補にします（93〜96行目）。
最終的にカウントを返せば答えになります。
問題がわかりにくかった上難しいので、とりあえず正しいと思う結果で投稿してみてデバッグしようとしたら、テストケースが間違っていました。あまりにも結果が少ないので例えば25とか36のような連続する数も評価しなければならないのか、と思って途方にくれていたら一旦問題が取り下げられ、修正されました。それで、25とか36も除外するコードで投稿したらそれをやらないパターンの結果で正しかったので再投稿して正解という具合でした。
問題の読み取りにくさ、問題自体の難しさ、テストケースの間違い、と3つものポイントで苦労しました。
ついでにわかったことですが、CodeIQの評価環境が私のローカルよりも速くなった様です。このコードは私のローカルだと1秒近くかかるのに結果は0.6秒台になっていました。ひょっとしたらズルをしなくてもパスしていたかもしれません。