ブログにも解説を載せるのは,2026/08 中くらいにします.ちょっと管理や,自分のための検索資産としていまいちなので.
カテゴリページ → https://maspypy.com/category/codeforces
のお知らせも見てください.
コンテストは寝坊したので,AC人数の少なそうなラス問だけ書いておきます.
G. No Balance Left
あまり内容がない?
すべての入力の max を $s$ として.
途中で $s$ より多きな金額を経由する可能性はあると思うんですが, $2s$ 以下でいいはず.
とりあえず $c_i$ は部分和集合だけが問題なので $2s$ 以下の金額全体にできます.入力を bitset を使って変換するだけでいい無駄パートみたいな感じだけど,解法ヒントかな?
すると次に,「支払, 戻り額」の組が全列挙できます.
これをもとに,残金 $0$ の状態から逆向きに探索して全状態を生成するようにします.bfs, dfs など.
「 $v$ から到達可能な頂点のうちで未訪問の点を列挙」ができればよいです.これで $O(s^2)$ 的な計算量になります.
支払い $a$,戻り $b$ というのは $v\geq b$ ならはじめて使える遷移という形です. $v$ が増えていくと可能な遷移も単調に増えていきます.これを bitset で持って,未訪問集合との AND をとればよいです.
ただし,bitset は単調に inplace に差分更新するのに対して,それを使う順番は単調とは限りません.これは,適当なブロック分割をして,ブロック境界のところでの bitset をメモリに置いておくようにすればよいです.
