本番で AC しましたが、証明の誤りがありましたらご指摘をお願いします。
解法
c=a-b をして階差を取ると、次のような問題に帰着できます。
c[0]...c[n] があります。「c[i]+=1, c[j]-=1 (i<j)」を最小回数行って c を mod m で 0 にしてください。
これを左から走査する方法で考えてみます。
すると c[i]+=1 はしたけれども j が決まってない、「未消化の操作」をいくつか貯め込みながら操作を決めていくことになります。
この未消化の操作の個数を rem として、rem の挙動について考えてみましょう。
c[i] を 0 にするには 2 通りの方法があります。
タイプ1: 新たに操作を行い、c[i]+=1 を m-c[i] 回行う、ans+=m-c[i], rem+=m-c[i]
タイプ2: 未消化の操作を消費し、c[i]-=1 を c[i] 回行う、rem-=c[i]
+ と - が混在する場合その 2 操作を結合できることから混在は起きません。
+ や - を m 回以上するなら最後尾に寄せればよく、考慮の必要がありません。
さて、タイプ2 は ans を増加させませんから、出来る限りタイプ2 で済ませたいです。
しかしタイプ2 は rem>=c[i] でしか使えないため、rem が足りない場合タイプ1 を使う必要が出てきます。
そこで、rem が足りなくなった時は過去に行ったタイプ2 をタイプ1 に変更することで rem を補充します (もちろん、i をタイプ1 で処理することも考慮する必要があります)。
k についてタイプ2 をタイプ1 に切り替えると、rem+=m, ans+=m-c[k] の効果があります。
どの k についてタイプを変えるかで rem の増加量は変わらず、ans の増加量は変わることに注意してください。
ここで rem の挙動をよく考えると、「i で rem が足りなくなったならば、i 以前 (i 含む) のタイプ2 のどれかはタイプ1 に切り替えるしかない」が分かります。
これ及び前述した性質から「i 以前のタイプ2 のうち m-c[i] が最小であるものを貪欲に変更すればよい」ことが得られます。
以上より、タイプ2 の i について m-c[i] を priority_queue などで管理することで Ο(NlogN) でこの問題が解けました。
なお、m-c[i] が m 以下の自然数であることから y-fast-trie などのデータ構造を用いて expected Ο(NloglogM) で解くことも可能です。
#include <cstddef> #include <cstdint> #include <functional> #include <iostream> #include <queue> #include <vector> int main() { using usize = std::size_t; using u64 = std::uint_fast64_t; usize n; u64 m; std::cin >> n >> m; std::vector<u64> c(n + 1); for (usize i = 0; i != n; ++i) { u64 a; std::cin >> a; c[i] = a; } for (usize i = 0; i != n; ++i) { u64 b; std::cin >> b; c[i] -= b; } for (usize i = n; i != 0; --i) { c[i] -= c[i - 1]; c[i] = (c[i] + m + m) % m; } std::priority_queue<u64, std::vector<u64>, std::greater<u64>> pq; u64 ans = 0; u64 rem = 0; for (const auto e : c) { pq.push(m - e); if (e > rem) { ans += pq.top(); pq.pop(); rem += m; } rem -= e; } std::cout << ans << std::endl; }
