読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

天下一プログラマーコンテスト 2016 本戦: E - 串焼きパーティ

Convex Hull Trick

http://tenka1-2016-final-open.contest.atcoder.jp/tasks/tenka1_2016_final_e

解法

串の座標は x=0 から x=L-1 のどれかである。これを全探索することを考える。

串の座標を x としたとき、a[i][j] を x にまで持ってくるコストは $(x-j)^2$ となる。そのため肉 i に関しては $(x-j)^2+a[i][j]$ が最小になる部位を x に持ってくるのが最適となる。

$(x-j)^2+a[i][j]=(-2j)x+(j^2+a[i][j])+x^2$ なので、直線 $(-2j)x+(j^2+a[i][j])$ の最小値を求められればいい。これは convex hull trick(CHT) を用いて効率的に解ける問題である。

今回は傾き単調+クエリ単調なので deque を使えば高速に処理できる。そもそも静的 CHT なので点群に対しての凸包ライブラリがあれば処理できる。

本番中は傾き単調のライブラリを投げたが、以前作った傾き任意のバージョンを確かめたかったので後で投げてみた。わざと追加順序をランダムにして試したところ、1/3ケースほど TLE してしまった。しかし、今回は追加クエリが106近くあるうえに時間制限が 1 秒だったため想定の範囲内といえよう。少なくとも WA はでていないため大方正常に動作しているようだ。

以下は任意順序 CHT に対して単調増加に直線を追加したコード。これはギリギリ930 ms で間に合った。

二項ヒープ風の任意順序 CHT とどのくらいの速度差がでるかを後で確かめてみたい。