CodeIQ：排他的 n乗数

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「排他的 n乗数」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

【概要】
「排他的n乗数」と呼ばれる数があります。
例えば、608 は、「排他的3乗数」です。この数は、

10進数で表記した時に、同じ数字を含まない

n乗(今回は、n=3)した結果( 6083=224755712 )の 10進数表記に、元の数に現れる数字が含まれない

という性質を持っています。
他にはたとえば、284 ( 2844 = 6505390336 )は、排他的4乗数です。
逆に、222=484 は、条件(a) に合わないので 22 は排他的2乗数ではありません。
1234=228886641 は、条件(b) に合わないので、123 は排他的4乗数ではありません。

さて、2つの正の整数 m と n を与えられます。
m より小さい「排他的n乗数」のうち、もっとも大きな値を計算するプログラムを書いてください。

【入出力】
入力は

620,3

のような感じです。m と n がコンマ区切りでならべられています。

出力は、

608

のように、条件を満たす排他的n乗数を 10進数で出力してください。
ただし、条件を満たす数がない場合には「-」を出力してください。

末尾の改行はあってもなくても構いません。

【例】

入力出力

620,3 608

300,4 284

【補足】
m は2以上、10万以下です。
n は2以上です
m の n 乗が 2の52乗を超えることはありません
不正な入力に対処する必要はありません
この問題は数学のおもちゃ箱（上）の 178ページの記事「排他的平方数」からヒントを得て作った問題です

入力	出力
620,3	608
300,4	284

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def isA(m)
	counts = Array.new(10,0)
	m.to_s.chars{|i|
		if (counts[i.to_i] += 1) > 1 then return false end
	}
	return true
end

def isB(m,n)
	x = (m**n).to_s

	a = x.split("").uniq
	b = m.to_s.split("")

	if (a & b).empty? then return true
	else return false
	end
end

def solve(m,n)
	(m-1).downto(1){|i|
		if !isA(i) then next end
		if isB(i,n) then return i.to_s end
	}
	return "-"
end

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

	m, n = line.split(",").map{|v| v.to_i}
	puts solve(m,n)
end

解説

とりあえず単純に総当たりでやってみたら時間制限的にもOKでした。
本当はもっと効率の良いアルゴリズムがあるかもしれません。

solve()

単純に総当たりで条件(a),(b)に合致する最大の数値を探します。
isA()、isB()はそれぞれ条件(a),(b)に合致するかどうかを判定する関数で、両方がtrueの数字が答えになります。答えの数字が見つかったらそこでループを終了し、ループの最後まで見つからなかったら「-」を返します。

isA()

「10進数で表記した時に、同じ数字を含まない」をチェックします。
数字の種類は0〜9の10種類しかないので要素数10の配列（counts）を用意し、その要素番号の数字がいくつあるかを格納します。配列は0で初期化しておきます。
入力値mは文字列にして1文字ずつ取り出し、取り出した1文字を再度数値にしてcountsの添字としてその要素番号の値を1増やします。これで各数字が何回使われているかがわかりますが、初めて2回使われる数字が見つかって時点でそれ以上の処理は必要ないためfalseを返して処理を終了します。最後まで2以上になる数字がなかったらtrueを返します。

isB()

「n乗した結果の10進数表記に、元の数に現れる数字が含まれない」をチェックします。
まず、mⁿを計算して文字列にしてから1文字ずつの重複のない配列にします（14行目）。224755712なら[2,4,7,5,1]になります。
mも同様に1文字ずつの配列にします（15行目）。
そしてこれらの積集合を求め、積集合が空ならtrue、そうでないならfalseを返します。

雑感

何も考えずに総当たりでやってみたらテストケースの最悪の場合でも1秒で終わりました。
試しに順列を使ってやってみたら総当たりよりも遅くなってしまいました。動的計画法でmを作るのも考えられますが、小さい値から作らなくてはいけないのであまりうまくいかない気がします。