naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Grand Contest 030

12/29(土) 21:00 - 22:50
200-800(300)-1000-1000-1400-1600(B300早解き回...)
B(300)まで通して380位、パフォ1882で1679→1702(+23)

A - Poisonous Cookies (200)

最後に毒入りクッキーを食べてから解毒せず放置してもいい?まさかね、と思ってて出遅れた
→AC 6:03
https://atcoder.jp/contests/agc030/submissions/3892613

B - Tree Burning (800,部分点300)

とりあえず300通しに行くか
立ち入れない区間がだんだん狭まっていく感じだよね
DPで(ちょっとややこしかったけど)
→部分AC 69:37
https://atcoder.jp/contests/agc030/submissions/3895112

これをN=2\cdot10^5で通すには…?

  • どこを終点にするかを全部試す?向きも含めて
  • 遠回りに往復しながら半分ずつ行くけど、残りは…連番で行くしかないか
  • とすると、最初に反時計回りに何個連番で燃やしていくかを決めれば行ける?
    • 回転方向が逆のケースについては…reverseして同じことをすればいい
  • 1つずつの遷移をO(1)で求められそうな気が(ちょっとややこしいけど)

その辺りまで実装して試合終了。あと10分あれば解けたかな…

終了後

遷移がうまく計算できてなくてデバッグに時間かかった(10分では無理だった)けど
→AC
https://atcoder.jp/contests/agc030/submissions/3897539

Bの1st ACのUm_nikさんの実装を見てなんでXの累積和を?と思って図を書き直したらなるほどすぎた:

L=10, X=[1,2,3,6,7,9] の時
0/1\9/2\7/3\6 = 2(1+2+3) + 2(10-9+10-7+10-6) - (10-6)
0/12\9/3\7/6 = 2(1+2+3+6) + 2(10-9+10-7) - 6
0/123\9/6\7 = 2(1+2+3+6) + 2(10-9+10-7) - (10-7)
規則的だ…

なので1から書き直して改めてAC
https://atcoder.jp/contests/agc030/submissions/3897654

C以降

開いてない