Manga Market が解けるまで -

今日解いた以下の問題がとてもおもしろかったので，解けるまでの思考を書いてみます．解説するというほどではありませんし，めっちゃネタバレするのでご注意ください．

問題概要

店 $i$ に時刻 $t$ に訪れると，買い物するのに $(a_i t + b_i)$ 時間かかります（ $a_i, b_i$ は非負整数）．店間の移動（最初の店の訪問を含む）には $1$ 時間かかります．時刻 $0$ から始めて時刻 $T$ までに買い物を終えるとすると，最大いくつの相異なる店で買い物できますか？

序盤

店の数が $N \le 2 \times 10^5$ と多いので，貪欲で $\mathrm{O}(N)$ or $\mathrm{O}(N \log N)$ か？と疑う．前からか後ろからか，ある時点で最小の所要時間の店とかを選んでいくとうまくいく？所要時間が線形関数なので，なんか Convex Hull Trick みたいなことをすればいいか？と思ったが，使った直線を削除するのは難しそうだしな～と思う．Convex Hull Trick に関してはたとえば以下を参照．（私は EDPC で学習しました．）

中盤

貪欲っぽいのは失敗しそうなので，反例がてら小さい例をいくつか作ってみる．

$a_1 = 3,~b_1 = 0,~a_2 = 1,~b_2 = 1$ だと $1\to2$ で $11$ 時間， $2\to1$ で $16$ 時間．

$a_1 = 3,~b_1 = 10,~a_2 = 1,~b_2 = 1$ だと $1\to2$ で $31$ 時間， $2\to1$ で $26$ 時間．

基本的には傾きが大きい店に先に行った方がよい（後からだととんでもなく時間がかかる）気がするけど，そら初期値にも依るよな～．となって，一般の場合について 2 つの店を回る順番を考えてみたら， $\displaystyle\frac{a_i}{b_i + 1}$ が大きい方に先に行くべきという結論が得られた．

なるほどね，後はこの順で「店を $k$ 個回るために必要な最小時間」を求める DP すればいいだけか．と実装して， $\mathrm{\Theta}(N^2)$ 時間になっていることに気付いて泣いた．

終盤

色々考えたけど計算量が落ちない，無理では？となっていたが，天啓を授かる．「傾きが正の店，そんなにたくさん回れますか……？」と．よく考えてみたら，傾きが正の店で買い物をするごとに，合計時間が倍以上になるので，この部分の DP table は高々 $\log T$ の大きさでよかった．傾きが $0$ の店は，余った時間で最後にまとめて回ればよい．終わった～～～！

まとめ

貪欲にしても DP にしても順番がよくわからんな～というところから始まり，結構綺麗な必要十分条件で特徴付けられるというのが 1 つ目の感動ポイントでした．2 つ目はなんと言っても天啓です．傾き $0$ の扱いを別にするというのは序盤で気付いていたものの，最後まであまり恩恵が分からなかったのですが，逆に考えれば「傾きが正の店をそんなにたくさん回れない」に早く気付けたかもしれませんね．

1 つ 1 つの部品を見てみるとさほど難しくなく，典型の詰め合わせという感じで，とても勉強になりました．こういうのをサクッと解けるようになると，もう少し上へ行ける気がします．