SRM 664 div1 easy:BearPlays - mayoko’s diary

SRM 664に参加しました。easyを通してレート上昇です。うれしいけどmed解きたい…

問題

TopCoder Statistics - Problem Statement

解法

結論から言うと
tmp = min(A, B) * 2^K mod (A+B)
として,min(tmp, A+B-tmp)が答えです。(2^K mod (A+B))はO(log K)で高速に計算ができるのでこれで時間内に答えを得られます。

理由を考えてみます(N=A+Bとする)。

(A, B)の大小関係関係なくAを2倍することを考えます。

AがB以下の場合は当然この操作は正しいです。
一方AがBより大きい場合は,問題文中の操作ではBを2倍することになるので,この操作を素直にやると,A = N-2*Bとなります。

一方で,Aを2倍してmod Nをとる操作は,2*A-N = 2*(N-B)-N = N-2*Bとなり,上記の操作と一致します。

よって,この「2倍してmod Nをとる」という操作をK回やることは問題文中の操作をやることと一致します。ゆえに,上に書いた解法は正しいです。

ll pow_mod(ll x, ll p, ll mod) {
    if (x == 0) return 0;
    if (p == 0) return 1;
    if (p == 1) return x;
    if (p%2) return (pow_mod(x, p-1, mod) * x) % mod;
    ll tmp = pow_mod(x, p/2, mod);
    return (tmp*tmp)%mod;
}

class BearPlays {
public:
    int pileSize(int A, int B, int K) {
        ll N = A+B;
        ll mi = min(A, B);
        ll ans = pow_mod(2, K, N);
        (ans *= mi) %= N;
        return min(ans, N-ans);
    }
};