kmjp's blog

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

Codeforces #750 Div2 : G. Kuzya and Homework

こちらはちょっとややこしい。
https://codeforces.com/contest/1582/problem/G

問題

整数列Pと、乗算・除算演算子列Qがあったとする。
これらがシンプルであるとは、変数X(初期値1)に対し、
X = X Q[i] P[i]
で表される変数値を並べたとき、すべて整数となるものを意味する。

整数列Aと乗算・除算演算子列Bが与えられる。
これらの部分列のうち、シンプルなものは何通りか。

解法

素因数ごとに、部分列の開始位置に対しどこまで終端を伸ばすと整数でなくなるかを求めよう。
これは素因数の乗算を開き括弧、除算を閉じ括弧とみなし、どこまで終端を伸ばすと閉じ括弧が先行するかをStackを使い求めて行けばよい。

int N;
int A[1010101];
vector<int> V[1010101];
string S;

const int prime_max = 1000;
vector<int> prime;
int NP,divp[prime_max];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

int R[1010101];

template<class V,int NV> class SegTree_2 {
public:
	V nolink;
	vector<V> val;
	SegTree_2(){val.resize(NV*2); clear(); nolink=1<<30;};
	void clear() { for(int i=0;i<NV*2;i++) val[i]=1<<20; }
	
	V getval(int k) {
		int e=k+NV;
		V ret=nolink;
		while(e>=1) ret=min(ret,val[e]), e/=2;
		return ret;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) val[k]=min(val[k],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);
		}
	}
};
SegTree_2<int,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	cin>>N;
	FOR(i,N) {
		cin>>x;
		FORR(p,prime) while(x%p==0) {
			V[p].push_back(i);
			x/=p;
		}
		if(x>1) V[x].push_back(i);
	}
	st.update(0,N,N-1);
	cin>>S;
	
	FOR(i,1010000) if(V[i].size()) {
		vector<int> A;
		FORR(v,V[i]) {
			if(S[v]=='*') {
				A.push_back(v);
			}
			else {
				if(A.size()) {
					x=A.back();
					A.pop_back();
				}
				else {
					x=-1;
				}
				st.update(x+1,v+1,v-1);
			}
		}
	}
	ll ret=0;
	FOR(i,N) {
		x=st.getval(i);
		ret+=(x+1)-i;
	}
	cout<<ret<<endl;
}

まとめ

気付いてしまえば単純だけど、本番とっさに思いつくかなぁ。