読者です 読者をやめる 読者になる 読者になる

「 今週のお題:ナルシストなナルシシスト数」問題解答 ( CodeIQ )

はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 入力 n に対して、ナルシシスト数の n進数版 ( n進数表記の場合の、各桁の桁数乗の総和が、元の数に等しい ) の中で、2桁以上のものを、小さい順に n 個出力する。( n個に満たない場合は全て )

詳細は、CodeIQ magazineの当該記事をご覧ください。

解説

Rubyで提出しました。なお、短くするのは諦めてます。

c=n=eval *$<
2.upto(1.0/0){|d|
  break if (n-1)**d*d<n**(d-1)
  f=->i{i.to_s(n).chars.reduce(0){|s,e|s+e.to_i**d}}
  h=d/2
  m={}
  (b=n**(d-h)).times{|i|(m[i-f[i]]||=[])<<i}
  (n**(h-1)).upto(n**h-1){|i|
     next unless r=m[f[i]-i*b]
     r.each{|e|
       puts (i*b+e).to_s(n)
       break if 1>c-=1
     } or break
  } or break
}

素直に全検しても良いのかもしれませんが、時間がかかりそうなので、DBで言うところの hash-join に近い方法でオーダを落とすことにしました。

桁数をまず決めて、その半分の桁で「各桁の桁数乗の和と実際の数値の差」をハッシュとして記憶しておきます。
※その差の値をキーとし、実際の数値のリストを保持するハッシュとなります。

そのうえで、もう半分の桁でループを回し、ハッシュに丁度該当する差のデータがあれば、半分ずつの桁を合成した数値が答えとなります。

ただ、上限の数だけ見つからない可能性を考慮し、桁数がある程度増えた時点で打ち切るよう 条件を設定しておきます。 全ての桁が最大値を取ったとしても、桁数乗の和の合計が、想定した桁数に満たない場合、具体的には、

$$ (n-1)^d\times d\lt n^{d-1} $$

という条件です。

終わりに

まあ、ある意味素直に調べていく問題だったような気がします。