ABCの終盤の難易度上がってない?
https://atcoder.jp/contests/abc216/tasks/abc216_g
問題
01で構成される文字列Sについて、
- 区間[L[i],R[i]]内に1がX[i]個以上ある
という条件が複数与えられる。
条件を満たすSのうち1の数が最小のものを1つ構成せよ。
解法
貪欲法でも解けるが、Editorialに則りダイクストラ法に持ち込む方法を紹介。
B[i]を、Sの先頭i文字における0の登場数とする。
条件を満たす範囲で、B[|S|]が最小のものを構築したい。
- B[i]は昇順なのでB[i+1]≧B[i]
- iが1つ増えるとき、0は1文字しか追加できないのでB[i]+1≧B[i+1]
- 条件より区間内の0の数は制限がかかりB[R[i]]≦B[L[i]]+(R[i]-L[i]+1)
と書くと、Bは定数の差まで許容される複数の不等式で記述できる。
多数の変数があるとき、2変数x,yに対しy≦x+cの形の条件が多数あるとき、x→yにコストcの辺を張ってダイクストラ法を行うと、条件を満たす各変数の最小値を求めることができる。
これを上記Bの条件に対し適用するとよい。
int N,M; int L[202020],R[202020],X[202020]; vector<pair<int,int>> E[202020]; int D[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) { E[i].push_back({i+1,1}); E[i+1].push_back({i,0}); } FOR(i,M) { cin>>L[i]>>R[i]>>X[i]; E[L[i]-1].push_back({R[i],R[i]-L[i]+1-X[i]}); } FOR(i,N+1) D[i]=1<<20; D[0]=0; priority_queue<pair<int,int>> Q; Q.push({0,0}); while(Q.size()) { int co=-Q.top().first; int cur=Q.top().second; Q.pop(); if(D[cur]!=co) continue; FORR2(e,c,E[cur]) if(D[e]>D[cur]+c) { D[e]=D[cur]+c; Q.push({-D[e],e}); } } FOR(i,N) cout<<1-(D[i+1]-D[i])<<" "; cout<<endl; }
まとめ
最初面倒な貪欲法で時にかかってしまった。これは反省。