taki["blog"] = 2020 (R2)

社会人5年目(東京2年目)の日常

2019/6/9 ABC129

今晩のABCについて.今日は日中にAtCoderの過去問とLeetCodeでDPと累積和について過去問を解いていた(そこではそんなに上手く解けなかったが)のが,かなり効いてきて,最近では会心の出来だった.

  • Aはそのままで,maxを引けば早かったかも

  • Bは少し考えて,問題が小さかったのでO(N2)の全探索をした

  • Cはメモ化だとわかった(過去問のおかげ).最初はDPのどっち方向かなと少し考え,大きい方から逆に埋めるのか?と変なことを考えたけど,小さい方から埋めた.埋めている途中にフィボナッチだなこれは,と気付き,故障階段を飛ばすようにフィボナッチして完了したと思ったけど,割り算の関係で答えが合わず少し考える.最終的に実装を少し直してOK

  • Dに移動.Cまで順調に解けたのでDを見た.雰囲気は全探索かな?と思ったけど,サイズが2000×2000で,この上で更に2000移動すると109だから「むむー」となったところで累積和を考える.右方向と左方向に両方向の累積和(スペースの場所)が分かっているとき,これと自分自身からマスの空きが計算できる.上下も同じ実装すれば良い.このメモを計算することができるか?と悩んだけど,左右と上下に同時にスイーと行くだけだったので,たぶんO(HW)で吸収されると信じて提出したら珍しく通った(奇跡)

  • Eを見る.XOR,やめた.

f:id:takilog:20190609234020p:plain