kmjp's blog

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

yukicoder : No.1330 Multiply or Divide

ARCあたりに出そう?
https://yukicoder.me/problems/no/1330

問題

N個の正整数A[i]と、正整数M、素数Pが与えられる。
変数x=1に対し、以下のいずれかを行う。

  • xがPの倍数ならPで割る
  • そうでないとき、1つA[i]を選んでxに掛ける

xがM以上になるのにかかる処理回数は何回か。

解法

xがMに到達にする最後の1手は最大のA[i]を掛ければよいので、それまでの手数を考える。
A[i]=P^a*Q (QはPを素因数に含まない)とすると、A[i]を掛けてxがMに到達しない場合、結局(a+1)手かけてQを掛けるのと同じ。

そこで
f(a+1) := A[i]のうちP^a*Qと表現できるもののQの最大値
とする。
コスト(a+1)でxにQを掛けられることになるので、あとはDPで手数に対し構築できるxの最大値を求めよう。

int N,M,P;
int A[202020],B[202020];
int C[61];

ll dp[1000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>P;
	int ma=0;
	FOR(i,N) {
		cin>>A[i];
		ma=max(ma,A[i]);
		x=1;
		while(A[i]%P==0) A[i]/=P, x++;
		C[x]=max(C[x],A[i]);
	}
	
	dp[0]=1;
	FOR(i,900) {
		if(1LL*dp[i]*ma>M) {
			cout<<i+1<<endl;
			return;
		}
		for(j=1;j<=31;j++) dp[i+j]=max(dp[i+j],dp[i]*C[j]);
	}
	cout<<-1<<endl;
}

まとめ

Pが素数じゃないと難易度どれぐらい変わるかな。