kmjp's blog

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

TopCoder SRM 671 Div2 Medium BearDartsDiv2

これDiv2 Medにしては嫌らしくない?自分もまんまとひっかかったし、本番正答率11%だと。
http://community.topcoder.com/stat?c=problem_statement&pm=13479

問題

N要素の数列wが与えられる。
0≦a<b<c<d≦(N-1)かつw[a]*w[b]*w[c]=w[d]となる(a,b,c,d)の組み合わせが何通りあるか求めよ。

解法

最大3つの値の積を持っておけばよく、かつその積はw[d]以下まで考慮すればよいので、
dp[積を計算した要素の数(最大3)][要素の積(最大max(w)=10^6)] := そのような要素の積の組み合わせ数
を要素の頭から順次計算していき、dp[3][w[d]]を答えに足しこんでいけばよさそうに見える。

ただ、この場合O(N*max(W))の計算が必要で、最悪ケースだと(自分の場合)5s位かかりちょっと足りない。

そこでDiv1 Medの要領で、w[a]*w[b]=w[d]/w[c]であることを用いて処理する。
w[a]*w[b]の登場回数をカウントしておき、c,dを総当たりしてw[a]*w[b]=w[d]/w[c]となるa,bの数を求めよう(逆にa,bを総当たりしてもよい。)

cを0から昇順で総当たりする。
まずdを(c+1)~(N-1)で総当たりし、w[a]*w[b]=w[d]/w[c]となるa,bの登場回数を答えにカウントする。
cをインクリメントしていくと、そのcは以後bとして利用される可能性がある。
よってcをインクリメントする前にaを0~(c-1)で総当たりし、w[a]*w[c]の登場回数をインクリメントする。

w[d]は10^6以下なので、w[a]*w[c]が10^6以下の時だけインクリメントすればよい。

ll num[1010101];

class BearDartsDiv2 {
	public:
	long long count(vector <int> w) {
		int N=w.size();
		ZERO(num);
		int a,b,c,d;
		
		ll ret=0;
		FOR(c,N) {
			for(d=c+1;d<N;d++) if(w[d]%w[c]==0) ret+=num[w[d]/w[c]];
			FOR(a,c) if(1LL*w[a]*w[c]<=1000000) num[w[a]*w[c]]++;
		}
		
		return ret;
	}
}

まとめ

500ptのDiv2 Mediumなら、前者のDP解で通る制限でも良い気がする…。