■A - Trailing Zeros
下から貪欲に
■B - Make N
これムズいって
chmin(y, a * x);
chmin(z, b * x);
としていいのは明らか
またy*b>x*aならswapしておく。
操作２と操作３の組み合わせを全探索する
aが十分に大きいときaを使える回数は高々n/a回数
n/a<=100000程度なら全探索していい。
aが小さいときはbを使う回数はa以下なので
bを全探索すればいい。
■C - One Three Nine
(a,b) = (3x+y,x+3y)としこれについて考える。
4<=a<=3n+mなのは明らか
aに対応するbの組み合わせを考える
a=3x+y
b=x+3yより
x=(3b-a)/8
y=(3a-b)/8
であり
3b=a mod8
3a=b mod8なので(この２式は同値)
まとめると
b = 3a mod8
1<=(3b-a)/8<=n ⇔ 8<=3b-a<=8n ⇔ (8+a)/3<=b<=(8n+a)/3
1<=(3a-b)/8<=m ⇔ 8<=3a-b<=8m ⇔ 3a-8m<=b<=3a-8
が必要になる。aをmod8ごとに考えると左右がともに単調な区間になるので
小さい方から、貪欲にとればいい。
■D - Priority Queue 2
すぬけさんの解説動画をみるとわかる
