Codeforces Round 1113

ブログにも解説を載せるのは,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 をメモリに置いておくようにすればよいです.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました