ABC 031 D 語呂合わせ

2015/11/22 (Sun) ABC AtCoder

問題

問題文

方針

数字に対応しうる文字列の数は $3^{27}$ とおり以上あるので全ての数字に対する割り当てを全探索することはできません.そこで,対応する文字列自体を決めずに長さを全探索します.長さは高々 $3$ なので $3^K$ となり間に合います. 長さを決めると $v_i$ の数字を前から見ていくことで対応する文字列が一意に定まります. 各長さの組み合わせについて,有効な文字列の割り当てが存在するか判定すればいいです.

本番は,実際はオーダーが同じ DFS を C++ で書いていたのですが,実装力がないので最後まで詰め切れませんでした.最初に長さを決め打ちするという発想には感動しました.

実装

k,n = gets.chomp.split.map(&:to_i)
vws = n.times.map {
  a = gets.chomp.split
  [a[0].each_char.map(&:to_i), a[1]]
}

(3**k).times.map { |m|
  [0] + k.times.map { |i| 1 + m / 3**i % 3 }
}.each { |l|
  f = [nil] * (k+1)
  check = vws.all? do |v,w|
    cur = 0
    ok = v.all? do |c|
      if f[c]
        next false if f[c] != w[cur, f[c].size]
      else
        f[c] = w[cur, l[c]]
      end
      cur += l[c]
    end
    next false if !ok
    cur == w.size
  end
  if check
    puts f[1,k]
    exit
  end
}