れんしゅうちょう。

■ [GCJ]総評 22:53

2:27:09で30pts、504位通過。

OO|O-|--

AもBも最初にぱっと思い付いたのを書いて、バグらせて、修正して提出しただけ。

Cは問題読んで「tのあるカードは全部速攻で使う」の以外はDFSするしか思い付かなかった。

N+M<=80では無理ゲーっぽいので、諦めて他に時間を使った。

以下ABを詳しく。

ツイートする

■ Problem A. FreeCell Statistics 22:52

問題

n回以下の試行でPd%の勝率、それを含めて全体でPg%の勝率となるような場合はあり得るか判定せよ的な問題。

D回の試行でDw回勝ち、Dl=D-Dw回負け、全体G回でGw回勝ち、Gl=G-Gw回負けるとする。

n回以下の制約より、Dを最小化したい。

Dw/D = Pd/100なので、約分すればよく、D=100/GCD(100,Pd)、Dw=Pd/GCD(100,Pd)とすればよい。

この時点でD>nとなっていたらBroken確定。

次に、全体を考えると、G>=D, Gw>=Dw, Gl>=Dlであればよい。

G,Gw,Glの最小値をPdと同様に求めれば、それをk倍しても全体の割合は一致する。

しかし、これらは全て左辺に登場し、">="なのでG,Gw,Glが0で無ければ充分大きいkを取り、G>=D, Gw>=Dw, Gl>=Dlを満たす事が出来る。

また、G!=0や、Gw=0⇔Pd=0、Gl=0⇔Pd=100を用いれば、解になる。

上記のD>nまでは開始10分でたどり着き、Gはk倍すればいいとまで解った物の条件の一行でバグを生みB問題へ逃げるという情けなさ。

ACしたコードは以下

n,pd,pg=getia
d = 100 / pd.gcd(100)
dw = pd / pd.gcd(100)
dl = d - dw
g = 100 / pg.gcd(100)
gw = pg / pg.gcd(100)
gl = g - gw
if d > n
    "Broken"
else
    if (gw == 0 && dw != 0)||(gl == 0 && dl != 0)
        "Broken"
    else
        "Possible"
    end
end

最後の変形に気付きながらも、どうせ計算量余裕ってレベルじゃないのでほうっておいた。

ツイートする

■ 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

ツイートする