Points and Powers of Two [Codeforces Round #486 D]

http://codeforces.com/contest/988/problem/D

N個の配列Xがある
この配列の以下の条件を満たす部分列を答えよ

• 任意の2つの要素の大きさの差が2の累乗
• その中で部分列の大きさが最大

考察

1. 任意の2つの要素というのが結構厳しい
2. 2^d+2^d=2^(d+1)が使えそう
3. 2^d+2^d+2^dは2の累乗とならないので、要素数が4つ以上とはならないっぽい

解説

http://codeforces.com/contest/988/submission/38869516

答えの候補は要素数が3か2か1の三択であると推測。
要素3の場合はx,x+2^n,x*2^(n+1)の組があればOK。
要素2の場合はx,x+2^nの組があればOK。
要素1は適当な数でよい。
　
下の実装だとO(N(logN)^2)なのでTLE怪しい

int N; ll X[201010];
set<ll> Y;
//---------------------------------------------------------------------------------------------------
int isd(ll x) {
    while (1 < x) {
        if (x % 2) return 0;
        x /= 2;
    }
    return 1;
}
//---------------------------------------------------------------------------------------------------
vector<ll> solve() {
    fore(y, Y) {
        ll x = 1;
        rep(i, 0, 32) {
            ll a = y;
            ll b = y + x;
            ll c = b + x;

            if (Y.count(b) and Y.count(c)) return { a,b,c };
            x *= 2;
        }
    }

    fore(y, Y) {
        ll x = 1;
        rep(i, 0, 32) {
            ll a = y;
            ll b = y + x;

            if (Y.count(b)) return { a,b};
            x *= 2;
        }
    }

    return { X[0] };
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i];
    rep(i, 0, N) Y.insert(X[i]);

    auto ans = solve();

    int n = ans.size();
    printf("%d\n", n);
    rep(i, 0, n) {
        if (i) printf(" ");
        printf("%lld", ans[i]);
    }
    printf("\n");