Codeforces ECR #156 : F. Diamond Theft

シンプルな問題設定ながら、かなり手間取った。
https://codeforces.com/contest/1886/problem/F

問題

2つのダイヤモンドを、N個のカメラが監視している。
各カメラは、いずれか片方、または両方を監視しており、各カメラの監視状況が与えられる。
また、各カメラは一度ハックすると数秒間停止し、その時間はカメラごとに与えられる。

1秒毎に、以下のいずれかの行動をとれるとき、ダイヤモンドを2つ順番に盗めるか。

• ダイヤモンドを盗む。その際、そのダイヤモンドを監視するカメラはすべて停止していなければならない。
• いずれかのカメラをハックする。

解法

取る順番は以下の通り。
(1つ目のダイヤだけを監視するカメラと、両方のダイヤを監視するカメラと、2つ目のダイヤだけを監視するカメラの一部を止める)→1つ目のダイヤを盗む→(両方のダイヤを監視するカメラの一部と、2つ目のダイヤだけを監視するカメラの一部を止める)→2つ目のダイヤを盗む。

1つ目から2つ目のダイヤを盗むまでの時間と、後半で止める2つ目のダイヤを監視するカメラの数を総当たりすることを考える。
ホールの定理より、盗むまでにx秒猶予があるなら、x秒以下の停止時間のカメラはx個以下でなければならない。
この条件のもと、SegTreeを使い2つ目のダイヤ及び両方のダイヤを監視するカメラを、前半後半どちらのタイミングまたは両方で停止するか貪欲に求められる。

これだとO(N^3logN)かかるので、2つ目のループ(2つ目のダイヤを監視するカメラの数)に対しては差分だけSegTreeを更新するようにしよう。

int N;
vector<int> V[4];

static ll const def=0;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val;
	vector<pair<V,int>> ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2);
		FOR(i,NV) ma[NV+i]={0,-i};
		for(i=NV-1;i>=1;i--) ma[i]=max(ma[i*2],ma[i*2+1]);
	};
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r||y<=x) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k].first+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=max(ma[k*2],ma[k*2+1]);
			ma[k].first+=val[k];
		}
	}
};
SegTree_3<int,1<<12> sta,stb;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		V[x].push_back(y);
	}
	FOR(i,4) sort(ALL(V[i]));
	int mi=1<<20;
	
	FOR(i,3030) {
		sta.update(i+1,1<<12,-1);
		stb.update(i+1,1<<12,-1);
	}
	
	FORR(v,V[1]) sta.update(v,1<<12,1);
	
	for(int lenb=1;lenb<=V[2].size()+V[3].size()+1;lenb++) {
		int vis[1515]={};
		multiset<pair<int,int>> M;
		
		FORR(v,V[2]) stb.update(min(lenb-1,v),1<<12,1);
		FOR(x,V[3].size()) {
			int v=V[3][x];
			sta.update(v-lenb,1<<12,1);
			vis[x]=0;
			if(sta.ma[1].first>0) {
				sta.update(v-lenb,1<<12,-1);
				vis[x]=1;
				stb.update(min(lenb-1,v),1<<12,1);
				sta.update(v,1<<12,1);
			}
			if(vis[x]==0) M.insert({v,x});
		}
		
		for(int a2=0;a2<=V[2].size();a2++) {
			int lena=V[1].size()+a2+V[3].size()+1;
			int b2=V[2].size()-a2;
			
			if(a2>0) {
				int v=V[2][V[2].size()-a2];
				stb.update(min(lenb-1,v),1<<12,-1);
				sta.update(v-lenb,1<<12,1);
			}
			
			while(sta.ma[1].first>0) {
				auto it=M.lower_bound({-sta.ma[1].second+1,0});
				if(it==M.begin()) break;
				it--;
				x=it->second;
				M.erase(it);
				int v=V[3][x];
				vis[x]=1;
				sta.update(v-lenb,1<<12,-1);
				stb.update(min(lenb-1,v),1<<12,1);
				sta.update(v,1<<12,1);
				
			}
			
			if(sta.ma[1].first<=0&&stb.ma[1].first<=0) {
				mi=min(mi,lena+lenb);
			}
			
		}
		FOR(x,V[3].size()) {
			int v=V[3][x];
			if(vis[x]==0) sta.update(v-lenb,1<<12,-1);
			else {
				stb.update(min(lenb-1,v),1<<12,-1);
				sta.update(v,1<<12,-1);
			}
		}
		
		FORR(v,V[2]) sta.update(v-lenb,1<<12,-1);
	}
	
	
	if(mi==1<<20) mi=-1;
	cout<<mi<<endl;
	
}

まとめ

こういうの時間内に解ける気しないな。
なんとなくJOIに多そうなイメージ。