AtCoder ARC 007 D - 破れた宿題 (2D, 試験管橙色)

一瞬激ヤバに見えるし、コーナーケースの数もえげつないけど、とりあえず最小の初項はすぐにわかると...

問題へのリンク

問題概要

等差数列があった。
等差数列を concat して得られる文字列から、先頭から何文字かと、末尾から何文字かを削除して得られた文字列 (長さ ) が与えられる。もとの等差数列として考えられるもののうち、(初項, 交差) の辞書順最小値を求めよ。ただし以下の条件を満たすとする

• に残っている文字列は、初項を表す文字列の一部が残っている
• 元の等差数列は、どの項も leading zero を含まない

制約

• 

まずは初項

とてもつらい気持ちになるやつだけど、一つの道しるべとして、「初項」として考えられる最小値だけは一瞬でわかる。

• S[0] != '0' のとき
  • S[1:] の先頭から 文字が 0 であるとき、S[0] + S.substr(1, k) が初項の最小値
• S の先頭 文字が 0 であるとすると、"1" + S.substr(0, k) が初項の最小値
  • のとき (S = "00...0" のとき) も同様 (この場合は交差の最小値は "1")

たとえばこんな感じになる:

• "3421" では、初項は "3"
• "300421" では、初項は "300"
• "00089" では、初項は "1000"
• "0" では、初項は "10"
• "000" では、初項は "1000"

さて、初項がわかってから第二項以降は 2 つの場合がある。

• 第二項がすべて S に含まれる場合
• 第二項が途切れている場合

第二項がすべて S に含まれる場合

こちらは単純に「第二項と第三項の切れ目」を全探索して、整合性をチェックすれば OK

第二項が途切れている場合

こちらは、第二項の候補として、以下の二通りを試せば OK

• 初項 + 1
• (S の初項を削った残りの値) × が、初項より大きくなる最小の値

前者が鬼のコーナーケースとなっている。たとえば

• S = "201" のとき、初項は 20、交差は 80 (第二項が 100)
• S = "202" のとき、初項は 20、交差は 1 (第二項が 21)
• S = "203" のとき、初項は 20、交差は 10 (第二項が 30)

という感じ。

コード

計算量は となる。 この問題のために、多倍長整数ライブラリを整えた！！！

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;

const int DEFAULT_SIZE = 125;
struct bint : vector<long long> {
    static const long long BASE = 100000000;
    static const int BASE_DIGIT = 8;
    int sign;

    // constructor
    bint(long long num) : vector<long long>(DEFAULT_SIZE, 0), sign(1) {
        if (num < 0) sign = -1, num = -num;
        (*this)[0] = num; 
        this->normalize();
    }
    bint& normalize() {
        long long c = 0;
        for (int i = 0;; ++i) {
            if (i >= this->size()) this->push_back(0);
            if ((*this)[i] < 0 && i+1 >= this->size()) this->push_back(0);
            while ((*this)[i] < 0) {
                (*this)[i+1] -= 1;
                (*this)[i] += BASE;
            }
            long long a = (*this)[i] + c;
            (*this)[i] = a % BASE;
            c = a / BASE;
            if (c == 0 && i == this->size()-1) break;
        }
        return (*this);
    }
    friend bint abs(const bint &x) {
        bint z = x;
        if (z.sign == -1) z.sign = 1;
        return z;
    }
    friend ostream &operator << (ostream &os, const bint &x) {
        if (x.sign == -1) os << '-';
        int d = x.size()-1; 
        for (d = x.size()-1; d >= 0; --d) if (x[d] > 0) break;
        if (d == -1) os << 0;
        else os << x[d];
        for (int i = d-1; i >= 0; --i) {
            os.width(bint::BASE_DIGIT);
            os.fill('0');
            os << x[i];
        }
        return os;
    }

    // operation
    bint operator - () const {
        bint res = *this;
        bool allzero = true;
        for (int i = 0; i < this->size(); ++i) {
            if (res[i] != 0) {
                allzero = false;
                break;
            }
        }
        if (!allzero) res.sign = -res.sign; 
        return res; 
    }
    bint& operator += (const bint& r) {
        while (size() < r.size()) this->emplace_back(0);
        if (sign == r.sign) {
            for (int i = 0; i < r.size(); ++i) (*this)[i] += r[i];
        }
        else {
            if (sign == 1 && abs(*this) < abs(r)) sign = -1;
            else if (sign == -1 && abs(*this) <= abs(r)) sign = 1;
            if (abs(*this) >= abs(r)) {
                for (int i = 0; i < r.size(); ++i) (*this)[i] -= r[i];
            }
            else {
                for (int i = 0; i < size(); ++i) (*this)[i] = -(*this)[i];
                for (int i = 0; i < r.size(); ++i) (*this)[i] += r[i];
            }
        }
        return this->normalize();
    }
    bint& operator -= (const bint& r) {
        while (size() < r.size()) this->emplace_back(0);
        if (sign == -r.sign) {
            for (int i = 0; i < r.size(); ++i) (*this)[i] += r[i];
        }
        else {
            if (sign == 1 && abs(*this) < abs(r)) sign = -1;
            else if (sign == -1 && abs(*this) <= abs(r)) sign = 1;
            if (abs(*this) >= abs(r)) {
                for (int i = 0; i < r.size(); ++i) (*this)[i] -= r[i];
            }
            else {
                for (int i = 0; i < size(); ++i) (*this)[i] = -(*this)[i];
                for (int i = 0; i < r.size(); ++i) (*this)[i] += r[i];
            }
        }
        return this->normalize();
    }
    bint& operator *= (long long r) {
        if ( (sign == 1 && r >= 0) || (sign == -1 && r < 0) ) sign = 1;
        else sign = -1;
        if (r < 0) r = -r;
        for (int i = 0; i < size(); ++i) (*this)[i] *= r;
        return this->normalize();
    }
    bint& operator *= (const bint& r) {
        int tx = (int)size()-1, ty = (int)r.size()-1; 
        for (tx = size()-1; tx >= 0; --tx) if ((*this)[tx] > 0) break;
        for (ty = r.size()-1; ty >= 0; --ty) if (r[ty] > 0) break;
        bint res(0);
        res.resize(tx+ty+2);
        if (sign == r.sign) res.sign = 1;
        else res.sign = -1;
        for (int i = 0; i <= tx; ++i) {
            for (int j = 0; j <= ty && i+j < (int)res.size()-1; ++j) {
                long long val = (*this)[i] * r[j] + res[i+j];
                res[i+j+1] += val / bint::BASE;
                res[i+j] = val % bint::BASE;
            }
        }
        return (*this) = res.normalize();
    }
    friend bint pow(const bint& a, long long n) {
        bint res(1), b = a;
        while (n > 0) {
            if (n & 1) res = res * b;
            b = b * b;
            n >>= 1;
        }
        return res;
    }
    bint operator + (const bint& r) const { return bint(*this) += r; }
    bint operator - (const bint& r) const { return bint(*this) -= r; }
    bint operator * (long long r) const { return bint(*this) *= r; }
    bint operator * (const bint& r) const { return bint(*this) *= r; }

    // divide
    bint& operator /= (long long r) {
        long long c = 0, t = 0;
        for (int i = (int)size()-1; i >= 0; --i) {
            t = bint::BASE * c + (*this)[i];
            (*this)[i] = t / r;
            c = t % r;
        }
        this->normalize();
        return (*this);
    }
    long long operator %= (long long r) {
        long long c = 0, t = 0;
        for (int i = (int)size()-1; i >= 0; --i) {
            t = bint::BASE * c + (*this)[i];
            (*this)[i] = t / r;
            c = t % r;
        }
        return c;
    }
    bint operator / (long long r) const {
        return bint(*this) /= r;
    }
    long long operator % (long long r) const {
        return bint(*this) %= r;
    }
    friend pair<bint, bint> divmod(const bint &a, const bint &r) {
        bint zero = 0, s = 0, t = 0;
        if (abs(a) < abs(r)) return {zero, a};
        bint ar = abs(r);
        s.resize((int)a.size()), t.resize((int)r.size());
        int tx = (int)a.size()-1;
        for (;tx >= 0; --tx) if (a[tx] > 0) break;
        for (int i = tx; i >= 0; --i) {
            t = t * bint::BASE + a[i];
            long long lo = 0, hi = bint::BASE;
            if (t >= ar) {
                while (hi - lo > 1) {
                    int mid = (hi + lo) / 2;
                    if (ar * mid > t) hi = mid;
                    else lo = mid;
                }
                t -= ar * lo;
            }
            s[i] = lo;
        }
        return make_pair(s.normalize(), t.normalize());
    }
    bint operator / (const bint& r) const {
        return divmod((*this), r).first;
    }
    bint operator % (const bint& r) const {
        return divmod((*this), r).second;
    }
    bint& operator /= (const bint& r) { return (*this) = (*this) / r; }
    bint& operator %= (const bint& r) { return (*this) = (*this) % r; }

    // equality
    friend bool operator < (const bint &x, const bint& y) {
        if (x.sign < y.sign) return true;
        else if (x.sign > y.sign) return false;
        else {
            int tx = (int)x.size()-1, ty = (int)y.size()-1; 
            for (tx = x.size()-1; tx >= 0; --tx) if (x[tx] > 0) break;
            for (ty = y.size()-1; ty >= 0; --ty) if (y[ty] > 0) break;
            if (tx < ty) return true;
            else if (tx > ty) return false;
            else if (x.sign == 1) {
                for (int i = tx; i >= 0; --i)
                    if (x[i] != y[i]) return x[i] < y[i];
                return false;
            }
            else {
                for (int i = tx; i >= 0; --i)
                    if (x[i] != y[i]) return x[i] > y[i];
                return false;
            }
        }
    }
    friend bool operator > (const bint& x, const bint& y) { return y < x; }
    friend bool operator <= (const bint& x, const bint& y) { return !(x > y); }
    friend bool operator >= (const bint& x, const bint& y) { return !(x < y); }
    friend bool operator == (const bint &x, const bint& y) {
        if (x.sign != y.sign) return false;
        int tx = (int)x.size()-1, ty = (int)y.size()-1; 
        for (tx = x.size()-1; tx >= 0; --tx) if (x[tx] > 0) break;
        for (ty = y.size()-1; ty >= 0; --ty) if (y[ty] > 0) break;
        if (tx != ty) return false;
        for (int i = tx; i >= 0; --i)
            if (x[i] != y[i]) return false;
        return true;
    }
    friend bool operator != (const bint& x, const bint& y) { return !(x == y); }
};

bint toBint(const string &s) {
    bint res = 0;
    for (int i = 0; i < s.size(); ++i) {
        res += (long long)(s[i] - '0');
        if (i != s.size()-1) res *= 10;
    }
    return res;
}

string toStr(const bint &r) {
    stringstream ss;
    if (r.sign == -1) ss << '-';
    int d = (int)r.size()-1; 
    for (; d >= 0; --d) if (r[d] > 0) break;
    if (d == -1) ss << 0;
    else ss << r[d];
    for (int i = d-1; i >= 0; --i) {
        ss.width(bint::BASE_DIGIT);
        ss.fill('0');
        ss << r[i];
    }
    return ss.str();
}



// 初項が syoko, 第二項を niko とすることが可能かどうか
// S の先頭は niko の先頭から始まる
bool isValid(const string &S, const bint &syoko, const bint &niko) {
    if (niko <= syoko) return false;
    int N = (int)S.size();
    string sniko = toStr(niko);
    int si = 0;
    for (int i = 0; i < sniko.size() && si < N; ++i) {
        if (sniko[i] != S[si++]) return false;
    }
    if (si == N) return true;

    bint prev = syoko, cur = niko;
    while (si < N) {
        if (S[si] == '0') return false;
        bint next = cur * 2 - prev;
        string snext = toStr(next);
        for (int i = 0; i < snext.size() && si < N; ++i) {
            if (snext[i] != S[si++]) return false;
        }
        if (si < N) prev = cur, cur = next;
    }
    return true;
}

// 試す
void judge(const string &S, const bint& syoko, const bint& niko_koho, bint& niko) {
    if (!isValid(S, syoko, niko_koho)) return;
    if (niko == 0) niko = niko_koho;
    else if (niko_koho < niko) niko = niko_koho;
}

// 解く
void solve(string S) {
    // 初項
    if (S[0] == '0') S = "1" + S;
    int zeronum = 0;
    for (int i = 1; i < S.size(); ++i) {
        if (S[i] != '0') break;
        ++zeronum;
    }
    bint syoko = toBint(S.substr(0, zeronum + 1));
    S = S.substr(zeronum+1);
    int N = (int)S.size();
    if (N == 0) {
        cout << syoko << " " << 1 << endl;
        return;
    }

    bint niko = 0;
    for (int i = 1; i <= N; ++i) {
        bint niko_koho = toBint(S.substr(0, i));
        if (niko_koho <= syoko) continue;
        judge(S, syoko, niko_koho, niko);
    }

    // +1 が valid か
    judge(S, syoko, syoko + 1, niko);

    // 0 を繋げていく
    bint niko_koho = toBint(S);
    while (niko_koho <= syoko) niko_koho *= 10;
    judge(S, syoko, niko_koho, niko);

    // 出力
    cout << syoko << " " << niko - syoko << endl;
}

int main() {
    string S;
    while (cin >> S) solve(S);
}