hotpepsiの練習帳

Google Code Jam 2013 Round 1A

23:23

Problem A. Bullseye

問題

• 白地に黒丸を描く
• 書き始めの半径rと、ペンキの量tが与えられる
• 中途半端な丸は描かない
• 何個丸が描けるか求める

方針 (small)

• シミュレーション
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1A_A_s.py

方針 (large)

• 半径rに必要なペンキの量は(r+1)^2-r^2=2*x+1
• 半径は2ずつ増えるので、必要なペンキ量は1,5,9,...または3,7,11,...
• 半径の半分をxとすると4x+1または4x+3
• 積分するとxから必要なペンキの量が求まる (2*x^2+xまたは2*x^2+3*x)
• 開始の半径rが3以上のときは、tにそれまでに必要なペンキの量を足す
• 解の公式でxを求める
• (math.sqrtを使ったため通らず)
• 整数のsqrtに修正
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1A_A_l.py

Problem B. Manage your Energy

問題

• 初期エネルギーEと、毎日の回復量R、N日分の幸福量Aが与えられる
• 一日のエネルギーはEを超えない
• 消費量×Aの総和の最大を求める

方針 (small)

• Eの最大値が小さいので、その日の消費量を1からEまで全部試す
• next[次の日の残りエネルギー] = 幸福量
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1A_B_s.cpp

方針 (large)

• (終了後)
• どうやら最大のから消費していけばよいらしい
• 次に消費する日はpriority queueで決める
• 日ごとに、少なくともその値以上を保つ必要がある最小値minと、その日に取りうるエネルギーの最大値maxを持っておく
• 初期値はmin=0、max=E
• 消費するときは、その日に消費できる最大値max-minを消費する
• その結果、前日にはmax-R以上、前々日はmax-2*R以上を保つ必要があるので、更新する
• また、消費できる最大値まで消費するので、次の日以降の最大値は、min+R、min+R*2、...となるので、更新する
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1A_B_l.cpp

結果

A small + B small = 23pt 2654th

もっとシンプルに解く必要がある。