imos法

ABC309C Imos 法で OK． 結局，大事なのは区間の端だけであり，それ以外は答えに影響しないから． 大事な場所だけ全探索するということ． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, k ; cin >> n >> k; map<ll,ll> ev; rep(i,n){ ll a,b; cin >> a >> b; // a--; ev[0] += b; ev[a] -= b; } ll s = 0; ll d = 0; for(auto [x,y]:…

C - ハイスコア 0-indexed で考える． で を表す． imos法区間 に対して得点 が対応している．もしからまでの全ての値を，選んだ区間で覆うと得点は0.また，0点より大きい得点が欲しければ，一か所でも覆えていなければよい．この場合，選んだ区間のたちの和が得点として入る．よって，どこで途切れるかを場合分けして全探索． を途切れさせるとすれば，を含まない区間は全て使うのが最善．また，( を覆わない区間全体 ) = ( の区間 ) - (を覆う区間全体)となるので，たちの和も同様の等式が成り立つ． ( の区間 )のの和は前計算で．( を覆う区間全体 )のの和はimos 法で． type…

atcoder.jp ケーキをパラメータの合計値でグループ分けする、という考察までは進んだが、そこで詰まった。 【問題】 1各パラメータの昇順に並んでいる。K番目の(a,b,c)の値を出力せよ。 【典型ポイント】 辞書順Ｋ番目を求める問題は、各パラメータごとにグループ分けして考える(よくDPが使える) 【知らなかったこと】 一様の値を一定区間に連続して配る時は、DPだろうがimos法が使える 【解法1】 まず、Ｋ番目のa+b+cの合計値を知りたい。 これは、DP + imos法 で求められる。 dp[i][j]:先頭からi個のパラメータを決めたときの、パラメータの合計値がjである場合の数 とす…