C - スペースエクスプローラー高橋君 〜意識低めのconvex hull trick〜

Quiz

https://atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_c

Submit

https://atcoder.jp/contests/colopl2018-final-open/submissions/4493568

ステップ１ O(N²)

• まずはO(N²)でいいから解いてみよう
• その場合の提出はこちら https://atcoder.jp/contests/colopl2018-final-open/submissions/4492374
  • TLE
  • サンプルは全て通る
• ここまでで、editorial解法のconvex hull trickを使う前までは正しく理解できていることが確認できる

ステップ２ convex hull trick

• オーダーを下げるために必要
• 初耳
• 理解として http://satanic0258.hatenablog.com/entry/2016/08/16/181331
• こちらを見た。グラフなどで素晴らしいまとめ
• しかし、私に実装はまだ早そう・・・
• convex hull trickクラスを借りてこよう http://d.hatena.ne.jp/sune2/20140310/1394440369
• intをllに書き換えて使ったらAC

感想

• convex hull trickの入り口は覗くことができた
• 実装は保留したが、正しく使うことができたので解ける問題は増えたことになる