kmjp's blog

競技プログラミング参加記です

AtCoder ABC #216 : G - 01Sequence

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;
	
}

まとめ

最初面倒な貪欲法で時にかかってしまった。これは反省。