taki["blog"] = 2020 (R3)

社会人6年目(東京3年目)の日常

2019/2/24 ABC119

最近プロコンの練習しているので,ABC119に出ました.やる気が無かったけど通知が飛んできたので,悩んだけどやった.とりあえず最近の目標は練習しているCまで解いて,Dを眺めるあたりまで時間内にいくことなんだけど,今回はDは分かったけどCは実装できなかった.どうも探索系が弱い気がするが,鍛えようと思っても鍛えられない.

  • Aはそのまま実装するだけ

  • Bもそのまま実装するだけ

  • Cはわからず放置して,途中で「ん?」って思って実装したけど答えが合わなかった.N=8なのでたぶん全探索だろうとは思ったけど,最終的に解説を読んで意味が分かった(弱)

    • 思いついた偽の解法(誤り): 一致しないA, B, Cの入力の和を取り,これをgreedyに持っているリストLとabsするものがコスト,と最初思ったけど,こうするとMP10の魔法を多く見積もり過ぎて正しい解にならない
  • Dは最初読んだときよく意味が分からなかったけど,lower_boundとupper_boundで実装できそうな気がしたので,実装してみたらいけた.例に対してうまく値が返ってこなかったけど,intじゃなくてlongにしたらいけたので通った.

f:id:takilog:20190224230938p:plain