Hatena::Grouptopcoder

れんしゅうちょう。 このページをアンテナに追加 RSSフィード

 | 

2011-10-01[GCJ]Google Code Jam Japan 2011

26位54pt1:48:50
問題SmallLarge
A36:23 誤答1回42:46
B57:581:44:50
C9:5910:46

もしソース全体見たい人が居ればスコアボードから。テンプレ略。

寄り道せずにC→A→Bで解いた。

Cは名前から例によって2進の問題ってのが明らかだったから最初に、C解き終わったらB正解居なかったのでAに。


Cは例によってO(1)とかのがあるんだろうなと思いつつ、普通に後ろの桁からDP

最後が0なら1+1に、1なら1+0にするだけ。

n = geti
res = 0
until n.zero?
    if n.odd?
        res += 1
        n >>= 1
    else
        res += 2
        n >>= 1
        n -= 1
    end
end
res


Aは、どう動いてそこに来たかだけ見ればいいので、入力の最後から逆に辿って最初にあった場所を特定すればよい。

m,c,w = getia
ab = []
c.times do
    ab << getia
end
c.times do
    a,b = ab.pop
    if w <= b
        w += a-1
    elsif w <= b + a - 1
        w -= b
    else
    end
end
w

最初から似たようなコード書いてたけど、-1とかでミスって1ペナ。

sampleは全部あってたので、smallでデバッグするために、そのまんまシミュレートするのを書いてsmall通し、diffとりながらデバッグしてlarge通した。



Bはなんか見た感じ明らかに貪欲的に、満足度高い物を期限切れギリギリの方から詰めてけばいい感じだった。

明らかにごちゃごちゃして詰む感じだったので、A見たいにミスらないように、最初からsmallデバッグ用のを書いてsmall通す。

n, k = getia
cts = []
n.times do
    cts << getia
    cts[-1][1] -= 1
end
cts.sort_by!{|a|a[2]}
flg = (0...k).to_a
nokori = k
res = 0
until k.zero? || cts.empty?
    tmp = cts.pop
    tmp[1].downto(0) do |i|
        if flg[i] == i
            flg[i] = -tmp[2]
            res += tmp[2]
            nokori -= 1
            tmp[0] -= 1
        end
        break if tmp[0].zero?
    end
end
res

もちろんこれじゃLarge通らないが、普通に区間区切ってけばいい。

コーヒーの種類は少ないので、分割されすぎて遅いという事にはならない。

予想通り細々した所で躓き、延々と調整。

n, k = getia
cts = []
n.times do
    cts << getia
    cts[-1][1] -= 1
end
cts.sort_by!{|a|a[2]}
res = 0
memo = [[0, k-1]]
until memo.empty? || cts.empty?
    c,t,s = cts.pop
    nex = []
    until memo.empty?
        rng = memo.pop
        if t < rng[0] || c.zero?#期限切れorコーヒー無し
            nex << rng.dcopy
        elsif rng[1] <= t#範囲内では期限切れにならない
            if rng[1] - rng[0] + 1 <= c #範囲内全部
                c -= rng[1] - rng[0] + 1
                res += (rng[1] - rng[0] + 1)*s
            else    #コーヒー全部
                rng[1] -= c
                res += c * s
                nex << rng.dcopy
                c = 0
            end
        else#範囲内で期限切れになる→範囲分割
            nex << [t+1, rng[1]].dcopy
            memo << [rng[0], t].dcopy
        end
    end
    memo = nex.dcopy
    memo.sort_by!{|a|a[0]}
end
res

優先度付queueなんていう高級な物は無いけど、別に区間がそこまで細切れにならないことは解っているので、あまり気にしなかった。

 |