AIM Tech Round 3 (Div. 1) B. Recover the String

問題

codeforces.com

0, 1 のみから構成される文字列で, 以下を満たすものを作れ。

• 00 の部分文字列が a00 個ある
• 01 の部分文字列が a01 個ある
• 10 の部分文字列が a10 個ある
• 11 の部分文字列が a11 個ある

連続部分文字列ではないことに注意。

解法

0 が n 個あるとすると, 00 の部分文字列は n*(n-1)/2 個あります。これから n がほとんど一意に決められます(n = 0 と n = 1 は区別できない)。
同様に a11 の情報から 1 の個数 m をほとんど一意に決められます。

0, 1 の区別はめんどくさいので, for 文で n+i, m+j を調べることにしましょう。以下では n, m は一意に確定したとします。

01, 10 の部分文字列は合計で n*m 個あります。a01 の個数から考えていくとすると, 0 の後に 1 が m 個続くようなものがいくつあるか, 1 が m-1 個続くようなものがいくつあるか, というように順番に調べていけば必ず所望の文字列が見つかることが分かります。

const string no = "Impossible";

string calc(vi a, int n, int m) {
    if (n*(n-1)/2 != a[0]) return no;
    if (m*(m-1)/2 != a[3]) return no;
    if (a[1] + a[2] != n*m) {
        return no;
    }
    if (n == 0 && m == 0) return "0";
    string ret;
    for (int i = m; i > 0 && a[1] > 0; i--) {
        int x = a[1] / i;
        a[1] %= i;
        for (int j = 0; j < x; j++) {
            ret += '0';
            n--;
        }
        ret += '1';
        m--;
    }
    for (int i = 0; i < m; i++)
        ret += '1';
    for (int i = 0; i < n; i++)
        ret += '0';
    return ret;
}

string solve() {
    vi a(4);
    for (int i = 0; i < 4; i++)
        cin >> a[i];
    int n = 0;
    while (n*(n-1)/2 < a[0])
        n++;
    int m = 0;
    while (m*(m-1)/2 < a[3])
        m++;
    for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
        string t = calc(a, n+i, m+j);
        if (t != no) return t;
    }
    return no;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << solve() << endl;
    return 0;
}