ABC198 Dの解法メモ【Ruby】

入水目指して過去挑戦して解けてないAtCoder Problems上でDifficultyが水色の問題を解いていく。

ABC198 D: Send More Money概要

3つの英小文字からなる文字列$ S1, S2, S3 $に対して、アルファベットと0~9の数字を1対1対応させたときに、 $ S1 + S2 = S3 $となるような対応を見つけて$ S1, S2, S3 $を数値に変換したものを出力する問題。

解法イメージ

まず、数値とアルファベットを対応させるので、アルファベットの種類が11種類以上になると数値を割り当てられない文字が出てくる。
そのため、アルファベットの種類数は10種類以下とする。

10種類の文字に対しての数値の割り当て方は $ 10! = 3,628,800 $通りなので全探査しても間に合う…らしいのだが、実装が下手でTLEしちゃったので1の位から順に文字に数値を当てはめて計算していく。

$ S1, S2, S3 $の右から$ i $番目の文字をそれぞれ$ c1, c2, c3 $だったとすると、$c1, c2$の数値が決まると$ c3 $も自動的に決まるので検討する組み合わせを減らすことができる。
また、すでに数字が割り当てられている文字や残っている数字の組み合わせでは$ c1 + c2 \equiv c3 \pmod{10} $が成り立たなくなった時点で計算を中断できる。

これらによって計算量を減らすことで間に合わせることができる。

実装例

@s1 = gets.chomp.reverse
@s2 = gets.chomp.reverse
@s3 = gets.chomp.reverse
@arr = (@s1.chars + @s2.chars + @s3.chars).uniq


@max = [@s1.length, @s2.length, @s3.length].max
if @arr.length > 10 || @s3.length < @max
  puts "UNSOLVABLE"
  return
end

def calc(i, u, hash, arr)
  if i == @max
    return if u > 0

    res1 = @s1.reverse.each_char.map {|c| hash[c] }.join("")
    res2 = @s2.reverse.each_char.map {|c| hash[c] }.join("")
    res3 = @s3.reverse.each_char.map {|c| hash[c] }.join("")
    return if res1[0] == "0" || res2[0] == "0" || res3[0] == "0"
    puts [res1, res2, res3]
    exit
  end
  
  c1 = @s1[i].to_s
  c2 = @s2[i].to_s
  c3 = @s3[i].to_s

  m1 = hash[c1]
  r1 = m1.nil? ? 0..9 : m1..m1
    r1.each do |num1|
    if m1.nil?
      next if !arr[num1].nil?
      hash[c1] = num1
      arr[num1] = c1
    end
    
    m2 = hash[c2]
    r2 = m2.nil? ? 0..9 : m2..m2
    r2.each do |num2|
      if m2.nil?
        next if !arr[num2].nil?
        hash[c2] = num2
        arr[num2] = c2
      end

      m3 = hash[c3]
      num3 = (num1 + num2 + u) % 10
      div3 = (num1 + num2 + u) / 10
      if !m3.nil?
        calc(i + 1, div3, hash, arr) if num3 == m3
      elsif arr[num3].nil?
        hash[c3] = num3
        arr[num3] = c3

        calc(i + 1, div3, hash, arr)
        
        hash[c3] = nil
        arr[num3] = nil
      end
      if m2.nil?
        hash[c2] = nil
        arr[num2] = nil
      end
    end
    
    if m1.nil?
      hash[c1] = nil
      arr[num1] = nil
    end
  end
end

calc(0, 0, { "" => 0 }, [])
puts "UNSOLVABLE"