| 26位 | 54pt | 1:48:50 |
| 問題 | Small | Large |
|---|---|---|
| A | 36:23 誤答1回 | 42:46 |
| B | 57:58 | 1:44:50 |
| C | 9:59 | 10: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なんていう高級な物は無いけど、別に区間がそこまで細切れにならないことは解っているので、あまり気にしなかった。