はじめに

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

問題

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

入力 n ( nは平方数 ) に対して、10進数での各桁の積が n かつ、連続する桁の積が ( 全桁の積をとった時を除いて ) いずれも平方数にならないような数が何通りあるか出力する。

例えば n=16 に対しては、「各桁の積がn」となる数は、44, 224, 1224, 11224 等いくらでもありますが、「連続する桁の積がいずれも平方数とならない」のは、28, 82 の2通りに限ります。( 44 の場合は、4 の一桁だけで平方数なので不適 )

解説

方針

nが1桁の場合を除き、条件に合う数字の各桁は、2,3,5,6,7,8 の6種類であり、現れる素因数は 2,3,5,7 の4種類であるため、4次元のベクトルとして表現することができます。
しかも、積が平方数になるかどうかという観点からは、素因数の指数の偶奇だけを見れば良いので、積の計算はベクトルの各次元のbitのon/offで済みます。
そこで、素因数 2,3,5,7 に 1,2,4,8 の bit を割り当て、2,8→1, 3→2, 5→4, 6→3, 7→8 と変換して考えます。これにより、積の計算は bit-xor、平方数かどうかの判定は全bitが 0 ( 要するに 0 と等しいかどうか ) で行うことができます。

また、2,8 は共に変換後の表現は同一になりますから、結局 2or8,3,6,5,7 の5種類の桁の個数の配列毎に、桁の並べ方が決まることになります。その並べ方を数えることを考えます。
※2,8が混在する場合は、2,8を同一視した並べ方の数に、更に2,8の並べ替えの分の倍率を掛ければ良い、となります。

ということで、手順としては

n を 2or8,3,6,5,7 の積に分解して、個数の配列を作る
その個数を元に桁の並べ方を列挙する
それぞれに対して、途中の連続する桁の積が平方数になることがあるかどうか ( 変換した数値の bit-xor が 0 になるかどうか ) を判定する

ということを考えます。

実装

次のRubyのコードを提出しました。

まず、n の分解ですが、これは素因数分解したときの各指数で作ることができます。
例えば n=176400=2⁴×3²×5²×7² であれば、2,3,6,5,7 の個数が (4,2,0,2,2) という具合になります。
6 を使う場合は、2,3の個数を1個ずつ減らして6を1増やす ( この例だと (3,1,1,2,2) や (2,0,2,2,2) )、8を使う場合は 2 の個数を2個減らす ( (2,2,0,2,2) が 2×8×3²×5²×7² に対応する ) ということで、素因数分解の結果を加工して作ることができます。これは、メインの処理である solve_sup で行っています。

この個数を配列を元に、実際に桁の並べ方を列挙するのが dupperm です。が、素直に全通り列挙するとTLEするため、「同じ数字の桁は連続しない」という性質を利用して、列挙する数を減らしました。

duppermにより列挙された桁の並べ方のパターンの中で、問題の条件に合うものをカウントするのが listup です。なお、RubyのEnumerableの使い方をそのままやりたかったので、duppermはブロックを引数にとれるようにし、ブロックがない場合は、自分自身を指定した enum_for を呼び出すようにしています。

require 'prime'

# 同じ要素が複数ある場合の順列それぞれにブロックを実行する
# ただし、個数の合計が2を超える場合は、同じ要素が連続する順列を省く
# ev が要素、cv が対応する個数の配列
def dupperm(ev,cv,&b)
  # raise unless ev.size==cv.size
  return enum_for(__method__,ev,cv) unless b
  n=ev.size
  sinit=cv.reduce(&:+)
  f1=->r,s{
    if s==0
      b.call(r)
    else
      n.times{|i|
        next if cv[i]==0
        cv[i]-=1
        f1[r+[ev[i]],s-1]
        cv[i]+=1
      }
    end
  }
  f2=->r,s,prev{
    if s==0
      b.call(r)
    else
      n.times{|i|
        next if i==prev||cv[i]==0
        cv[i]-=1
        f2[r+[ev[i]],s-1,i]
        cv[i]+=1
      }
    end
  }
  sinit>2 ? f2[[],sinit,nil] : f1[[],sinit]
end

# 桁に現れる 2,3,6,5,7 の個数に応じて、
# どの連続する桁 ( 全体を除く ) の積も平方数にならないものを
# カウントする
def listup(cv)
  s=cv.reduce(&:+)-1
  dupperm([1,2,3,4,8],cv).count{|r|
    t=[]
    s.times.all?{|i|
      t<<r[i]
      i.times{|j| 0==(t[j]^=r[i]) and break }
    }
  }
end

def solve_sup(n)
  cv=[0]*5
  idmap={2=>0,3=>1,5=>3,7=>4}
  Prime.prime_division(n).each{|q,r|
    i=idmap[q] or break
    cv[i]+=r
  } or return 0
  a=0
  loop{
    a+=listup(cv)
    t=cv[0]
    c8=0
    while cv[0]>2
      cv[0]-=2
      c8+=1
      a+=(1..c8).reduce(listup(cv)){|s,e|s*(cv[0]+1-e)/e}
    end
    cv[0]=t
    break unless cv[0]>0&&cv[1]>0
    cv[0]-=1
    cv[1]-=1
    cv[2]+=1
  }
  a
end
def solve(n)
  n==0 ? 1 : n<10 ? 1+solve_sup(n) : solve_sup(n)
end
puts solve(gets.to_i)

終わりに

最初は、分解・列挙・判定をそれぞれ独立させたかったのですが、結局TLE回避のため、列挙のところで候補を絞る処理を入れてしまいました。最初から列挙・判定を融合しておけば良かったんじゃないかなと後悔しましたが…。まあ、通ればいいや。( ということに )

ange1のブログ

「今週のお題：連続する桁の数字で作る平方数」問題解答 ( CodeIQ )

はじめに

問題

解説

方針

実装

終わりに