れんしゅうちょう。

■ Problem B. The Killer Word 22:52

問題

QRのC問題でPatrickをいじめ抜いた鬼畜Seanを、今度は我々がいじめ抜く問題。

しかしSmallしか通せなかったため、Patrickの敵を討てなかった。

Hangmanというアメリカでよくある？ちょっとしたゲームをするので、Seanを最も陥れられる手は何かみたいな問題。

見た感じで、DFSすれば楽そうだと思ってそのまんま書いた。

深さが26以下になるのもよろしい。

1回目のWAは、dfsの引数をdupにしていなかったので、行った先でlsが消去されてしまっていた。

「同じのがあれば、First in dictionaryで返せ」は辞書順ではなく、問題で与えられた順である事に注意。これでもう1回WAった。

ソースに"|"が埋め込まれているのは辞書順で'z'より後ろな番兵用だったのだが、結局意味がなかった。

Largeは、適当に作った大きいケースが厳しかったので諦めていた。

終了後にpossの辺りをもうちょっとマシにしてみたら、Largeで830秒。C++で書いてたらギリ間に合うかもしらん。

問題はC++でコンテスト中に書き終えるスキルが無い事だけど。

smallのみACしたソースは以下。

$dic = []
$memo = {}
def poss(str, chr)
    unless $memo[str].nil?
        return $memo[str][chr.ord - 'a'.ord] unless $memo[str][chr.ord - 'a'.ord].nil?
    else
        $memo[str] = []
    end
    res = []
    for i in 0...str.size
        res.push i if str[i] == chr
    end
    $memo[str][chr.ord - 'a'.ord] = res
end

def dfs(ds, ls)
    return [0,ds[0]] if ds.size == 1
    c = ls.shift
    hs = {}
    for w in ds
        po = poss(w,c)
        hs[po] ||= []
        hs[po].push w
    end
    return dfs(ds,ls) if hs.size == 1
    res = [0,"|"]
    hs.each do |pos, dic|
        tmp = dfs(dic, ls.dup).dup
        tmp[0] += 1 if pos.size == 0
        if (tmp[0] > res[0])||(tmp[0] == res[0] && $dic.index(tmp[1]) < $dic.index(res[1]))
            res = tmp
        end
    end
    res
end

each_case do
    n,m=getia
    ds = []
    tmp = {}
    $dic = []
    $memo = {}
    n.times do
        w = gets.chomp
        $dic.push w
        s = w.size
        tmp[s] ||= []
        tmp[s].push w
    end
    $dic.push "|"
    tmp.each do |hash,key|
        ds.push key
    end
    ls = []
    m.times do
        ls.push gets.chomp.to_a
    end
    res = []
    ls.each do |l|
        tmp = [0,"|"]
        ds.each do |ws|
            hoge = dfs(ws,l.dcopy)
            if (tmp[0] < hoge[0])||(tmp[0] == hoge[0] && $dic.index(tmp[1]) > $dic.index(hoge[1]))
                tmp = hoge.dcopy
            end
        end
        res.push tmp[1]
    end
    res.join(" ")
end

ツイートする