これ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解で通る制限でも良い気がする…。