Atcoder Grand Contest 011 E. Increasing Numbers
Atcoder Grand Contest 011 E. Increasing Numbers
E: Increasing Numbers - AtCoder Grand Contest 011 | AtCoder
感想
数論の問題などでたまに見かけるレピュニットの性質をうまく利用した問題で少しおもしろかった。
解法
増加的な数を9個以下のレピュニットの和で表してやると解ける。
レピュニットを$\ R\ $とすると、$\ 9R + 1\ $がきれいになることを利用するのは下の問題でも同じである。
実装1
#include "bits/stdc++.h" using namespace std; //----------------------------------------Library--------------------------------------------- class Bigint { public: static const int BASE = 100000000, LEN = 8; bool negative; std::vector<int> a; Bigint& normalize(); public: Bigint(int x = 0); Bigint(const std::string& s); Bigint& operator = (const Bigint& x); Bigint& operator = (int x); Bigint& operator = (const std::string& s); const bool operator < (const Bigint& x) const; const bool operator > (const Bigint& x) const; const bool operator <= (const Bigint& x) const; const bool operator >= (const Bigint& x) const; const bool operator != (const Bigint& x) const; const bool operator == (const Bigint& x) const; Bigint operator -() const; Bigint& operator += (const Bigint& x); Bigint& operator -= (const Bigint& x); Bigint& operator *= (const Bigint& x); Bigint& operator /= (const Bigint& x); Bigint& operator %= (const Bigint& x); const Bigint operator + (const Bigint& x) const; const Bigint operator - (const Bigint& x) const; const Bigint operator * (const Bigint& x) const; const Bigint operator / (const Bigint& x) const; const Bigint operator % (const Bigint& x) const; friend std::pair<Bigint, Bigint> divmod(const Bigint& lhs, const Bigint& rhs); friend std::istream& operator >> (std::ostream& is, Bigint& x); friend std::ostream& operator << (std::ostream& os, const Bigint& x); friend const Bigint abs(Bigint x); }; Bigint& Bigint::normalize() { int i = a.size()-1; while (i >= 0 && a[i] == 0) i --; a.resize(i + 1); if (a.size() == 0) negative = false; return *this; } Bigint::Bigint(int x) : negative(x < 0) { x = abs(x); for (; x > 0; x /= BASE) a.push_back(x % BASE); } Bigint::Bigint(const std::string& s): negative(false) { int p = 0; if (s[p] == '-') { p ++; negative = true; } else if (s[p] == '+') p ++; for (int i = s.size() - 1, v = BASE; i >= p; i --, v *= 10) { int x = s[i] - '0'; if (x < 0 || 9 < x) { std::cerr << "error: parse error:" << s << std::endl; exit(1); } if (v == BASE) { v = 1; a.push_back(x); } else { a.back() += x * v; } } normalize(); } Bigint& Bigint::operator = (const Bigint& x) { negative = x.negative; a = x.a; return *this; } Bigint& Bigint::operator = (int x) { return *this = Bigint(x); } Bigint& Bigint::operator = (const std::string& s) { return *this = Bigint(s); } const bool Bigint::operator < (const Bigint& x) const { if (negative != x.negative) return negative < x.negative; if (a.size() != x.a.size()) return (a.size() < x.a.size()) ^ negative; for(int i = a.size()-1; i >= 0; i --) if (a[i] != x.a[i]) return (a[i] < x.a[i]) ^ negative; return false; } const bool Bigint::operator > (const Bigint& x) const { return x < (*this); } const bool Bigint::operator <= (const Bigint& x) const { return !(x < (*this)); } const bool Bigint::operator >= (const Bigint& x) const { return !((*this) < x); } const bool Bigint::operator != (const Bigint& x) const { return (*this) < x || x < (*this); } const bool Bigint::operator == (const Bigint& x) const { return !((*this) < x || x < (*this)); } Bigint Bigint::operator -() const { Bigint ret(*this); if (a.size()) ret.negative = !ret.negative; return ret; } Bigint& Bigint::operator += (const Bigint& x) { if (negative != x.negative) return *this -= -x; if (a.size() < x.a.size()) a.resize(x.a.size()); int up = 0; for (int i = 0; i < a.size(); i ++) { a[i] += (i < x.a.size() ? x.a[i] : 0) + up; up = a[i] / BASE; a[i] %= BASE; } if (up) a.push_back(1); return *this; } Bigint& Bigint::operator -= (const Bigint& x) { if (negative != x.negative) return *this += -x; std::vector<int> b(x.a); if ((*this < x) ^ negative) { a.swap(b); negative = !negative; } for (int i = 0, up = 0; i < a.size(); i ++) { a[i] += BASE - (i < b.size() ? b[i] : 0) + up; up = a[i] / BASE - 1; a[i] %= BASE; } return this->normalize(); } Bigint& Bigint::operator *= (const Bigint& x) { negative ^= x.negative; std::vector<int> c(a.size() * x.a.size() + 1); for (int i = 0; i < a.size(); i ++) { long long tmp = 0; for (int j = 0; j < x.a.size(); j ++) { long long v = (long long)a[i] * x.a[j] + c[i+j] + tmp; tmp = v / BASE; c[i + j] = (int)(v % BASE); } if (tmp) c[i + x.a.size()] += (int)tmp; } a.swap(c); return this->normalize(); } Bigint& Bigint::operator /= (const Bigint& x) { return *this = divmod(*this, x).first; } Bigint& Bigint::operator %= (const Bigint& x) { return *this = divmod(*this, x).second; } const Bigint Bigint::operator + (const Bigint& x) const { Bigint res(*this); return res += x; } const Bigint Bigint::operator - (const Bigint& x) const { Bigint res(*this); return res -= x; } const Bigint Bigint::operator * (const Bigint& x) const { Bigint res(*this); return res *= x; } const Bigint Bigint::operator / (const Bigint& x) const { Bigint res(*this); return res /= x; } const Bigint Bigint::operator % (const Bigint& x) const { Bigint res(*this); return res %= x; } std::pair<Bigint, Bigint> divmod(const Bigint& lhs, const Bigint& rhs) { if (!rhs.a.size()) { std::cerr<<"error: division by zero"<<std::endl; exit(1); } Bigint x(abs(rhs)), q, r; for (int i = lhs.a.size() - 1; i >= 0; i --) { r = r * Bigint::BASE + lhs.a[i]; int head = 0, tail = Bigint::BASE; if (r >= x) { while (head + 1 < tail) { int mid = (head + tail) / 2; if (x * Bigint(mid) > r) tail = mid; else head = mid; } r -= x * head; } q.a.push_back(head); } reverse(q.a.begin(), q.a.end()); bool neg = lhs.negative ^ lhs.negative; q.negative = neg; r.negative = neg; return std::make_pair(q.normalize(), r.normalize()); } std::istream& operator >> (std::istream& is, Bigint& x) { std::string tmp; is >> tmp; x = Bigint(tmp); return is; } std::ostream& operator << (std::ostream& os, const Bigint& x) { if (x.negative) os << '-'; if (!x.a.size()) os << 0; else os << x.a.back(); for (int i = x.a.size()-2; i >= 0; i --) { os.width(Bigint::LEN); os.fill('0'); os << x.a[i]; } return os; } const Bigint abs(Bigint x) { x.negative = false; return x; } std::string str(Bigint x) { stringstream st; st << x; return st.str(); } //------------------------------------------------------------------------------------------ bool check(Bigint n, int k) { string s = str((Bigint)9 * n + (Bigint)(9 * k)); int sum = 0; for (int i = 0; i < s.size(); i ++) sum += s[i] - '0'; return sum <= 9 * k; } int main() { Bigint n; cin >> n; int lb = 0, ub = 500000; while (ub - lb > 1) { int mid = (lb + ub) / 2; if (check(n, mid)) ub = mid; else lb = mid; } cout << ub << endl; return 0; }
下の実装はboostの多倍長整数ライブラリによるすっきりした実装。boostはの多倍長演算は遅いっぽく（要検証）、ほとんど$\ TLE\ $してしまった。
実装2
#include "bits/stdc++.h" #include <boost/multiprecision/cpp_int.hpp> #define Bigint boost::multiprecision::cpp_int bool check(Bigint n, int k) { Bigint t = 9 * (n + k); std::string s = t.str(); int sum = 0; for (int i = 0; i < s.size(); i ++) sum += s[i] - '0'; return sum <= 9 * k; } int main() { Bigint n; std::cin >> n; int lb = 0, ub = 500000; while (ub - lb > 1) { int mid = (lb + ub) / 2; if (check(n, mid)) ub = mid; else lb = mid; } std::cout << ub << std::endl; return 0; }
