codeFlyer 予選 : E - 祝日

本番途中で離脱してしまったけど、ちゃんと出てたら解けたのかなぁ。
https://beta.atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_e

問題

この国では１年はY週間からなり、１週当たりW日ある。
以下の２つの形で祝日が与えられる。

• 1年の始まりからA[i]日目が祝日
• 1年のうちB[j]回目のC[j]曜日が祝日

なお、この国では祝日が(D+1)以内に２つあるとその間もすべて祝日となる。
１年の始まりが1～W番目の曜日だった場合、祝日はいくつあるか求めよ。

解法

まず部分点である後者のみ考える。
１年の始まりを１日ずつずらしていくということは、w曜日始まりが(w+1)曜日始まりに切り替わると、実質y回目のw曜日は到達が１週遅くなるのでw日遅くなるようなものである。
よって、曜日の集合をmultisetで管理し、曜日をずらすごとに削除・追加して、その際隣接する祝日との距離が(D+1)以下かどうかを踏まえて間が埋まるか考え、祝日の総数の差分を適用していけばよい。

前者の祝日に関しては、毎回１日ずれると考えて同様に追加・削除するだけ。
両祝日がかぶるケースだけ気をつけること。

ll Y,W;
ll N,M,D;
ll A[51],B[101010],C[101010];
vector<ll> CC[101010];
ll ret;
multiset<ll> MM;

void del(ll c) {
	auto it=MM.find(c);
	auto pr=it,ne=it;
	if(MM.count(c)==1) {
		ll le=*--pr;
		ll ri=*++ne;
		if(ri-le>D+1) {
			ret--;
			if(c-le<=D+1) ret-=c-le-1;
			if(ri-c<=D+1) ret-=ri-c-1;
		}
	}
	MM.erase(it);
}
void add(ll c) {
	auto it=MM.insert(c);
	auto pr=it,ne=it;
	ll le=*--pr;
	ll ri=*++ne;
	if(MM.count(c)==1) {
		if(ri-le>D+1) {
			ret++;
			if(c-le<=D+1) ret+=c-le-1;
			if(ri-c<=D+1) ret+=ri-c-1;
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Y>>W>>N>>M>>D;
	MM.insert(-1LL<<60);
	MM.insert(1LL<<60);
	
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		ret++;
		MM.insert(A[i]);
	}
	FOR(i,M) {
		cin>>B[i]>>C[i];
		B[i]--,C[i]--;
		CC[C[i]].push_back(B[i]*W+C[i]);
		if(MM.count(B[i]*W+C[i])==0) ret++;
		MM.insert(B[i]*W+C[i]);
	}
	auto it=MM.begin();
	auto it2=it;
	it2++;
	while(it2!=MM.end()) {
		if(*it2>*it && *it2-*it<=D+1) ret+=*it2-*it-1;
		it++;
		it2++;
	}
	FOR(i,W) {
		cout<<ret<<endl;
		//FORR(m,MM) cout<<m<<"  ";
		//cout<<endl;
		FOR(j,N) del(A[j]);
		FORR(c,CC[i]) del(c);
		FOR(j,N) add(++A[j]);
		FORR(c,CC[i]) add(c+W);
		
	}
	
}

まとめ

大晦日間際に祝日があり、元旦直後に祝日がある場合、その間は祝日にならないのか気になった。
いや、問題文を厳密に読めば年はまたがないことはわかるんだけどさぁ。