2022-02-07 ABC238 : AtCoder Beginner Contest 238 E - Range Sums を解いた
モノグサプログラミングコンテスト2022 (ABC238 : AtCoder Beginner Contest 238) - E - Range Sums を解いた。
問題: https://atcoder.jp/contests/abc238/tasks/abc238_e
(l, r) = (1, N) があれば Yes 。逆に 1 箇所でもカバーしていない箇所があれば No 。 r - l の短い側から並べて確定範囲を広げるようなことができないか……などと考えていた。
本番では解けなかった。
解説 : https://atcoder.jp/contests/abc238/editorial/3360
解説を踏まえて解き直した。
区間和を扱うことから累積和で考える。基本的なテクニックなのになぜか本番では使わなかった。
累積和 S で考えたとき a_1 + a_2 + ... + a_N は S_n - S_0 にあたる。この 2 つの値が得られるなら Yes になる。
(l_i, r_i) を累積和 S で表すと (S_{l_i - 1}, S_r) になる。 S_i を頂点、情報を辺として考えたとき、ひとつの情報から 2 頂点の距離が分かることになる。 S_0 から S_N までの距離が分かれば良い。要は S_0 と S_N が連結になっていれば良い。
Union-Find 等で同一連結成分であるかを調べれば良い。 Q <= 2 * 10^5 でそれごとに Union-Find を merge しても間に合う。
提出: https://atcoder.jp/contests/abc238/submissions/29137219
実装は ACL から dsu (Union-Find) を持ってくれば簡単だ。区間和から累積和を連想するのも簡単なはず……。惜しいことをした。
今日のコミット。