blog.bouzuya.net

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_NS_n - S_0 にあたる。この 2 つの値が得られるなら Yes になる。

(l_i, r_i) を累積和 S で表すと (S_{l_i - 1}, S_r) になる。 S_i を頂点、情報を辺として考えたとき、ひとつの情報から 2 頂点の距離が分かることになる。 S_0 から S_N までの距離が分かれば良い。要は S_0S_N が連結になっていれば良い。

Union-Find 等で同一連結成分であるかを調べれば良い。 Q <= 2 * 10^5 でそれごとに Union-Find を merge しても間に合う。

提出: https://atcoder.jp/contests/abc238/submissions/29137219

実装は ACL から dsu (Union-Find) を持ってくれば簡単だ。区間和から累積和を連想するのも簡単なはず……。惜しいことをした。


今日のコミット。