Skip to content

Instantly share code, notes, and snippets.

@jinjor
Last active August 29, 2015 13:56
Show Gist options
  • Save jinjor/8958718 to your computer and use it in GitHub Desktop.
Save jinjor/8958718 to your computer and use it in GitHub Desktop.
CodeIQ「ジェムストリング問題」の回答
5578864439
ENV: Scala
POINT: 目的のパターンに至るまでの組み合わせの数を再帰的に求める。一度求めた値は再利用して計算量を抑える。
■POINTの補足
種類毎の宝石数をベクトルa、その時の全パターン数をf(a)であらわすと、
aが1次元の時、f(a)はaの絶対値となる。また、aから各種類の宝石のうちひとつを選んで取り去った
ベクトルの集合Bに対して、f(a)=Σ(f(b)+1) | b<-B
例えば、宝石"aaabcc"が与えられた時、全ての組み合わせは
=f([3,1,2])
=(f([2,1,2])+1)+(f([3,2])+1)+(f([3,1,1])+1)
=...
=188
■注意点
・順列を全て求めようとするとメモリが足りなくなる
・頭から目的のパターンまでを数え上げると計算量が膨大になる
・パターン数を求める方法を採用して一度計算した値を再利用すると大幅に計算量を抑えられる
・答えは32ビットでは足りないためLong型が必要
・minilist.txtで自動テストを行うと安心感が得られる
■ベンチマーク
101[ms]
■コードゴルフ(Scala, 512 bytes, 153[ms])
object J{type G=Map[Char,Int];type S=String
val h=collection.mutable.Map[Any,Long]()
def y(g:G):Long=h.getOrElseUpdate(g.map(_._2),if(g.size<1)0 else(for{(c,i)<-g}yield(g+(c->(i-1)))filter(_._2>0))map(y(_)+1)sum)
def d(c:Char,s:G)=s.get(c)map{i=>if(i>1)s+(c->(i-1))else s-c}
def i(s:G,t:S):Long=t.headOption.map{h=>(for{(a,_)<-s;if a<h;b<-d(a,s)map(y(_)+1)}yield b).sum+i(d(h,s)get,t.tail)+1}getOrElse 0
def main(args:Array[S])=println(i("abbbbcddddeefggg"groupBy(a=>a)map(a=>(a._1,a._2.size)),"eagcdfbe"))}
■感想
ナムドット問題に比べて随分簡単だなーと思ってプログラムを実行してみたら、処理が返ってこなくて泣きました。
いつも面白い問題ありがとうございます。
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment