https://codeiq.jp/ace/yuki_hiroshi/q684 の回答コード

solver.rb

# 5578864439
# ENV: Ruby
# POINT: 順列をすべて数え上げようと思うと計算量が大きくなりすぎるので，メモ化により枝刈りする

### この問題で出現する宝石列は，
### 与えられた宝石の順列を（辞書順で昇順となるような順序で）すべて求め，
### 各順列に対して先頭から1個，先頭から2個，先頭から3個……を取り出して，
### 重複するものを取り除きながら並べていくことで得ることができます。
###
### 例題（minis.txt）の場合は，出現する宝石の個数が少ないことから，
### 素朴に上記の手順で数え上げるだけでも回答が可能だったので，
### 当初はその方針で実装を始めました。
### つまり，Array#permutationを使ってすべての宝石列を求め，
### 目的の宝石列にたどり着くまでの個数を数え上げる，というアルゴリズムです。
###
### しかしながら，問題となる宝石列（gems.txt）の場合，
### 出現する宝石の個数は16個あるため，
### まず単純に順列を列挙するだけでも16!個という膨大な数になってしまいます。
### したがって，上記の素朴なアルゴリズムでは回答が求められないことに気づきました。
###
### ところで，例題の場合を考えると，
### 与えられた宝石から「aaa」を取り除いたときに残るのは「b」が1個，「c」が2個となります。
### 過程を省いて結果だけ述べれば，
### 先頭が「aaa」に一致する宝石列の総数は，
### 与えられた宝石から「aaa」を取り除いたときに残る宝石の「種類ごとの個数」に依存することがわかりました。
### （「種類ごとの個数」とは，宝石XがNx個，宝石YがNy個，というような情報のことです。）
### この「種類ごとの個数」が一致するような文脈では，
### 残りの宝石を使って作ることのできる宝石列の総数は一致するというわけです。
###
### この回答では，
### 再帰による探索関数に「種類ごとの個数」をキーとしたメモ化の仕組みを組み合わせて，
### 目的の宝石列よりも前方に出現する宝石列を数え上げるアルゴリズムを実装しました。
###
### 以下に，回答を求める際に使用したコードを添付します。

gems = "abbbbcddddeefggg".split("")
princess = "eagcdfbe".split("")

def get_next_cursor(cursor, elem)
  tmp = cursor.dup
  tmp << elem
  tmp
end
def get_next_remain(remain, elem)
  tmp = remain.dup
  tmp.delete_at(tmp.find_index {|e| e == elem })
  tmp
end
# @memoのキーとして使用する配列を生成する
# 配列にはremainに含まれる各文字の個数を昇順に格納する
def get_memo_key(remain)
  remain.uniq.map {|e|
    remain.count {|ee| ee == e }
  }.sort
end
# @princessよりも前に出現する列の個数を数え上げる
def solve(cursor, remain)
  # remainが空なら出現する列の個数は0となる
  if remain.empty?
    return 0
  end
  memo_key = get_memo_key(remain)
  # cursorが@princessの前方と一致する場合はメモ化された値を無視する
  # それ以外の場合はメモ化された値を使う
  if @memo.has_key?(memo_key) && [email protected]_with?(cursor.join)
    return @memo[memo_key]
  end
  count = 0
  # @princessの前方に出現する列の個数を数え上げる
  # solveに渡すcursor自体はsolveの返り値に含まれないので忘れずに1を加算する
  remain.uniq.each {|elem|
    break if (cursor + [elem]).join >= @princess.join
    count += solve(get_next_cursor(cursor, elem), get_next_remain(remain, elem)) + 1
  }
  @memo[memo_key] = count
  count
end

@memo = {}
@princess = princess
puts solve([], gems) + 1