🗂

ABC188 D - Snuke Prime

2021/02/17に公開

考えたこと

各日についてかかるコストはその日に使っているサービスのコストの合計値とCのminを取ったものになる。
各日についてのコストを配列で管理できればimos法を使って区間の足し算は高速に処理することができるので解けそうにみえる
しかし今回は管理する期間が長すぎるため、単純にimos法で解くことができない

端点だけを管理する

コストが増えたり、減ったりする場所だけ考えることにする
$a_i$ において $+c_i$ されて、 $b_i+1$ において $-c_i$ されるということを以下のように一括で管理する

(t_i, c_i): この日からコストが+c_iされる

$(t_i, c_i)$ を $t_i$ の値で昇順にソートして、その日のコストを変数 $s$ でもっておくことにする
ある $t_i$ から次の $t_{i+1}$ までのコストは一定なので、その間にかかるコストの合計値は $min(C, s) \times (t_{i+1} - t_{i})$ となる

座標圧縮

こういう座標が広すぎて配列に入れられないというシチュエーションで使われる手法として座標圧縮というものがある
値の大小関係を保ったまま、区間の長さを縮めることができる

\{4, 3, 1, 7, 3, 6, 1\} \rightarrow \{2, 1, 0, 4, 3\}

この問題では $a_i$ と $b_i + 1$ という値を入れた配列を座標圧縮して長さを縮める
この圧縮した後の座標に対して、imos法を適用することで計算量を抑えることができる

提出コード

端点だけを管理

座標圧縮

考えたこと

端点だけを管理する

座標圧縮

提出コード

Discussion