kmjp's blog

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

yukicoder : No.176 2種類の切手

177より難しかったし、しょうがないよね…。
http://yukicoder.me/problems/457

問題

A円の切手とB円の切手が無限枚ある。
これらの切手を用いて、合計T円以上を払う払い方のうち、最小金額を求めよ。

解法

まずは自分の解法を紹介。
B円切手をy枚使うとすると、T円以上払うにはA円切手は最低 \lceil \frac{T-B*y}{A} \rceil枚使うことになる。
よって払う金額は B*y + A * \lceil \frac{T-B*y}{A} \rceilとなる。

あとはyを0から順に総当たりして上記式の最小値を求めていき、B*yがTに到達するか、もしくはyがAに到達した時点で探索を打ち切る。
B円切手A枚以上の探索が不要なのは、B円切手A枚はA円切手B枚で置き換えられるので、結局B円切手を(y-A)枚使う場合と同じ総額になるためである。
探索回数は min(A,\frac{T}{B})なので、最大ケースで A\fallingdotseq B \fallingdotseq \sqrt T の時O(√T)の計算量となる。


Writer解は別方法のようだ。
非負整数x,yを用いて、 A*x+B*yの形で LCM(A,B)+n*GCD(A,B)の任意の数値を表現できる(らしい)。
よって T \ge LCM(A,B)なら、Tを LCM(A,B)+n*GCD(A,B)の形になるよう、Tを GCD(A,B)の倍数まで繰り上げればよい。
 T \lt LCM(A,B)ならyを0~A/GCD(A,B)もしくはB*yがTを超えるまで総当たりすればよい。
こちらのループ回数は min(\frac{A}{GCD(A,B)},\frac{T}{B})となる。
LCM(A,B)に対してTが大きい場合はこちらの解法が有効であるが、今回はそうでもないのでどちらでも良い。

void solve() {
	ll A,B,T;
	
	cin>>A>>B>>T;
	ll mi=1LL<<60;
	
	for(ll y=0; y*B <= T+B && y<=A; y++) mi=min(mi, y*B+ (T-y*B+A-1)/A*A);
	cout<<mi<<endl;
}

解法

時々★2で侮れない問題が出てきて怖い。