れんしゅうちょう。

GCJ 2011のR1A-BのThe Killer Word。

Patrickの敵を取ったのを忘れていたので、一応書いておこうかとか。

Largeで140秒くらい。

class Word
    def initialize(w, i = nil)
        @to_s = w
        @id = i
        @length = w.length
        @mask = [0]*26
        for i in 0...26
            for j in 0...w.size
                @mask[i] <<= 1
                @mask[i] += 1 if w[j].ord == ('a'.ord + i)
            end
        end
    end
    attr_accessor :to_s, :id, :length
    def mask(c)
        @mask[c.ord - 'a'.ord]
    end
end
def searchKillerWord(dic, ls)
    res = dic[0]
    max = 0
    dp = dic.group_by{|w| w.length}.map{|len,ws| [0, ws]}
    ls.each do |ask|
        nextdp = []
        dp.each do |cnt, words|
            grp = words.group_by{|w| w.mask(ask)}
            grp.each do |pat, ws|
                ncnt = cnt
                ncnt += 1 if pat.zero? && grp.size != 1
                if ws.size != 1
                    nextdp << [ncnt, ws]
                elsif max < ncnt || (max == ncnt && res.id > ws[0].id)
                    max = ncnt
                    res = ws[0]
                end
            end
        end
        dp = nextdp
    end
    res
end
1.upto(gets.to_i) do |case_number|
    n,m=gets.split.map(&:to_i)
    result = []
    dic = []
    n.times do |i|
        w = Word.new(gets.chomp, i)
        dic << w
    end
    m.times do
        line = gets.chomp.split("")
        result << searchKillerWord(dic, line)
    end
    puts "Case ##{case_number}: #{result*" "}"
end

考え方は相変わらずで、再帰をやめてDPにしたのと、Wordとかいうクラス作って、マスクを最初に一回するだけにしたくらい。

クラス作ってる人が結構居て、おいしそうだと思ってパクってみたら、随分と見通しが良くなった。比較的綺麗に書けたと思う。

group_byなんていうのが備わっているあたり、やっぱりRubyぱない。

ツイートする