Codeforces Round #308 (Div. 2) C. Vanya and Scales

明後日からまた暇になるのでたくさん解けそうです。

問題

codeforces.com

解法

2 通り紹介します。

まずひとつ目。
w が 2 と 3 の時は m がどんな値であろうと OK です。よって, それ以外の場合について考えればよいですが, m が 10^9 以下で w が 4 以上の場合は使う可能性のあるおもりの数が少ないので, 全探索でいけちゃいます。

ちゃんと計算量解析をすると, 4^n が 10^9 を超えるのは n が 15 のときで, 3^15 は 2*10^7 で抑えられる程度なので, 各おもりを無視/プラス/マイナス　で場合分けしても十分計算が間に合います。

次にふたつ目。こっちが想定解っぽいですね(なら 10^18 にしろよと思いますが)

いつも 2 進数で数をつくるような要領で, 各 w の累乗の要素を求めていきます。

その値が 0 ならそれは無視して良いということなのでスルーです。値が 1 ならその値は m の要素の一つなので 要素として入れれば良いです。値が w-1 だったら その要素はマイナス要素として入れてひとつ w をかけた回数がおおいのを追加すれば良く, 値が w だったら単純に次の要素を追加すれば良いです。
これを上手いこと調べるだけですね。

ll pp[103];
int maxindex = 0;

bool dfs(int index, ll now, ll tar) {
    if (now == tar) return true;
    if (index > maxindex) return false;
    if (dfs(index+1, now, tar)) return true;
    if (dfs(index+1, now+pp[index], tar)) return true;
    if (dfs(index+1, now-pp[index], tar)) return true;
    return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll w, m;
    cin >> w >> m;
    if (w <= 3) {
        cout << "YES" << endl;
        return 0;
    }
    {
        ll tmp = 1;
        int index = 0;
        while (tmp < m) {
            tmp *= w;
            index++;
        }
        pp[0] = 1;
        for (int i = 1; i <= index; i++) pp[i] = pp[i-1]*w;
        maxindex = index;
    }
    if (dfs(0, 0, m)) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

int a[40];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int w, m;
    cin >> w >> m;
    int cnt = 0;
    while (m) {
        a[cnt++] = m%w;
        m /= w;
    }
    for (int i = 0; i < 40; i++) {
        if (a[i] <= 1) continue;
        else if (a[i] == w-1 || a[i] == w) a[i+1]++;
        else {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}