読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

TopCoder SRM 707 Div1 Medium MultiplyAddPuzzle

SRM

コーナーケースが面倒。
https://community.topcoder.com/stat?c=problem_statement&pm=14527

問題

整数S,T,A,Bが与えられる。

Sに対し以下の処理を繰り返しTにしたい。

  • Aを加える
  • B倍する

処理を最小何度行えばよいか。

解法

Bの値で大まかに場合分けする。

  • B=1の場合
    • B倍は意味がないので、(T-S)/Aが整数ならその回数だけA加える。
  • B=0の場合
    • 最初に0倍することでS=0にできる点以外はB=1の場合と同じ。両者調べて小さい方を応えればよい。
  • B≧2の場合
    • 乗算の回数を総当たりしよう。仮に乗算をm回使えるなら、Sから生成可能な整数は乗算を使う合間に加算を行う回数をp[i]として \displaystyle (((S+A*p_m)*B+A*p_{m-1})*B+A*p_{m-2}) ... +a_0) = S*B^m + A\sum_{i=0}^m p_iB^iとなる。
    • あとは \displaystyle \sum_{i=0}^m p_iB^i = \frac{T-S*B^m}{A}となるp_iの最小値を求めよう。右辺をB進数とみなし、p[0]から順に決めていけばよい。

途中乗算の過程でオーバーフローを起こして計算ミスしないよう注意。自分も注意してたつもりが1WAやらかした。

class MultiplyAddPuzzle {
	public:
	long long minimalSteps(long long s, long long t, long long a, long long b) {
		
		if(s==t) return 0;
		
		if(b<=1) {
			if(b==0 && t==0) return 1;
			if(a) {
				if(s<=t && (t-s)%a==0) return (t-s)/a;
				if(b==0 && t%a==0) return 1+t/a;
			}
			return -1;
		}
		// a>=1, b>=2
		ll mi=1LL<<60;
		ll cur=1,num=0;
		while(1) {
			if(s*cur/cur!=s) break;
			if(s*cur>t) break;
			
			if(t==s*cur) {
				mi=min(mi,num);
			}
			if(a && (t-s*cur)%a==0) {
				ll left=(t-s*cur)/a;
				ll step=num,r=1;
				int i;
				while(r<cur) {
					step += left%b;
					r*=b;
					left/=b;
				}
				step+=left;
				mi=min(mi,step);
			}
			
			if(cur*b>t || cur*b/b!=cur) break;
			cur*=b;
			num++;
		}
		if(mi==1LL<<60) mi=-1;
		return mi;
	}
}

まとめ

難しくはないが。

広告を非表示にする