作れる数 [yukicoder No.680] - はまやんはまやんはまやん

考察

1. サンプルを考える（操作を独立に考えられないかに着目して見てみよう）
1+3+6=1+(2+1)+(4+2)=(1+2+4)+(1+2)
2. 初項1公比2の等差数列の最初の部分列で構成される
3. あとは大きい方から貪欲に取っていくいつものやつ？
4. submit証明

解法

https://yukicoder.me/submissions/254279

サンプル1を見てみると
10 = 1+3+6=1+(2+1)+(4+2)=(1+2+4)+(1+2)
となり、初項1公比2の等差数列の最初の部分列で構成されることが分かる。
なので、このように分解できるかを判定すればいいが、大きい要素数の部分列から順に使えるか判定していく貪欲をしよう。
なんでこんな貪欲で良さそうかという話であるが、構築問題などでも割とよくある方針である。
典型として覚えよう。

int N;
//---------------------------------------------------------------------------------------------------
ll f(int x) {
    ll res = 1;
    rep(i, 0, x) res *= 2;
    return res - 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    rrep(i, 30, 1) {
        ll x = f(i);
        if (x <= N) N -= x;
    }

    if (N == 0) printf("YES\n");
    else printf("NO\n");
}