AtCoder ABC 354 D - AtCoder Wallpaper (1D, 水色, 450 点)

周期性をうまいこと活用してなんとかする問題！

• 問題へのリンク

問題概要

座標平面上で下の図のような白黒模様が与えられる (問題文より)。

左下の頂点が 、右上の頂点が であるような長方形領域内部の黒色部分の面積 (の 2 倍) を求めよ。

制約

• 

考えたこと

負の値にもなるのが結構嫌らしい。

そこで、x 座標と y 座標がともに 4 ずれると同じ構造を繰り返すことに着目して、全体に大きめの 4 の倍数を足して、正の値のみで考えればよいようにした。こうすると、典型テクとして

---

= 左下の座標が 、右上の座標が であるような長方形領域における黒色部分の面積

---

を求めることに帰着させるという方法がある。これが求められれば答えは

と表せるのである。

を求める

x 座標も y 座標も 4 ごとに同じ構造を繰り返すことに着目した (公式解説ではさらに y 座標は 2 ごととしていた)。

また、 の部分の答えをあらかじめ持った配列を用意しておくことで、余った部分を楽に求められるようにした。詳細はコードを参照。

コード

オーバーフローが怖いので 128 ビット整数 (のラッパー) を用いた。

#include <bits/stdc++.h>
using namespace std;

// int 128
struct i128 {
    // inner value
    __int128 val;
    
    // constructor
    constexpr i128() : val(0) {}
    constexpr i128(long long v) : val(v) {}
    i128(const string &s) : val(0) {
        parse(s);
    }
    void parse(const string &s) {
        val = 0;
        for (auto c : s) {
            if (isdigit(c)) val = val * 10 + (c - '0');
        }
        if (s[0] == '-') val *= -1;
    }
    constexpr __int128 get() const {
        return val;
    }
    constexpr i128 abs() {
        if (val < 0) return -val;
        else return val;
    }
    
    // comparison operators
    constexpr bool operator == (const i128 &r) const {
        return this->val == r.val;
    }
    constexpr bool operator != (const i128 &r) const {
        return this->val != r.val;
    }
    constexpr bool operator < (const i128 &r) const {
        return this->val < r.val;
    }
    constexpr bool operator > (const i128 &r) const {
        return this->val > r.val;
    }
    constexpr bool operator <= (const i128 &r) const {
        return this->val <= r.val;
    }
    constexpr bool operator >= (const i128 &r) const {
        return this->val >= r.val;
    }
    friend constexpr bool operator < (long long x, const i128 &y) {
        return y.val > x;
    }
    friend constexpr bool operator > (long long x, const i128 &y) {
        return y.val < x;
    }
    friend constexpr bool operator <= (long long x, const i128 &y) {
        return y.val >= x;
    }
    friend constexpr bool operator >= (long long x, const i128 &y) {
        return y.val <= x;
    }
    
    // arithmetic operators
    constexpr i128& operator += (const i128 &r) {
        val += r.val;
        return *this;
    }
    constexpr i128& operator -= (const i128 &r) {
        val -= r.val;
        return *this;
    }
    constexpr i128& operator *= (const i128 &r) {
        val *= r.val;
        return *this;
    }
    constexpr i128& operator /= (const i128 &r) {
        val /= r.val;
        return *this;
    }
    constexpr i128& operator %= (const i128 &r) {
        val %= r.val;
        return *this;
    }
    constexpr i128 operator + () const {
        return i128(*this);
    }
    constexpr i128 operator - () const {
        return i128(0) - i128(*this);
    }
    constexpr i128 operator + (const i128 &r) const {
        return i128(*this) += r;
    }
    constexpr i128 operator - (const i128 &r) const {
        return i128(*this) -= r;
    }
    constexpr i128 operator * (const i128 &r) const {
        return i128(*this) *= r;
    }
    constexpr i128 operator / (const i128 &r) const {
        return i128(*this) /= r;
    }
    constexpr i128 operator % (const i128 &r) const {
        return i128(*this) %= r;
    }
    
    // bit operators
    constexpr i128 operator >>= (long long r) {
        val >>= r;
        return *this;
    }
    constexpr i128 operator <<= (long long r) {
        val <<= r;
        return *this;
    }
    constexpr i128 operator &= (long long r) {
        val &= r;
        return *this;
    }
    constexpr i128 operator |= (long long r) {
        val |= r;
        return *this;
    }
    constexpr i128 operator << (long long r) const {
        return i128(*this) <<= r;
    }
    constexpr i128 operator >> (long long r) const {
        return i128(*this) >>= r;
    }
    constexpr i128 operator & (long long r) const {
        return i128(*this) &= r;
    }
    constexpr i128 operator | (long long r) const {
        return i128(*this) |= r;
    }
    
    // other operators
    constexpr i128& operator ++ () {
        ++val;
        return *this;
    }
    constexpr i128& operator -- () {
        --val;
        return *this;
    }
    constexpr i128 operator ++ (int) {
        i128 res = *this;
        ++*this;
        return res;
    }
    constexpr i128 operator -- (int) {
        i128 res = *this;
        --*this;
        return res;
    }
    friend istream& operator >> (istream &is, i128 &x) {
        string s;
        is >> s;
        x.parse(s);
        return is;
    }
    friend ostream& operator << (ostream &os, const i128 &x) {
        auto tmp = x.val < 0 ? -x.val : x.val;
        char buffer[128];
        char *d = end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (x.val < 0) {
            --d;
            *d = '-';
        }
        int len = end(buffer) - d;
        if (os.rdbuf()->sputn(d, len) != len) {
            os.setstate(ios_base::badbit);
        }
        return os;
    }
};

const i128 OFFSET = 1LL<<35;
vector<vector<i128>> men = {
    vector<i128>({2, 1, 2, 1}),
    vector<i128>({1, 2, 1, 2}),
    vector<i128>({0, 1, 0, 1}),
    vector<i128>({1, 0, 1, 0})
};

i128 calc(i128 x, i128 y) {
    i128 qx = x / 4, rx = x % 4;
    i128 qy = y / 4, ry = y % 4;
    i128 res = qx * qy * 16;
    
    i128 wx = 0, wy = 0;
    for (int i = 0; i < rx; ++i) for (int j = 0; j < 4; ++j) wx += men[i][j];
    for (int i = 0; i < 4; ++i) for (int j = 0; j < ry; ++j) wy += men[i][j];
    res += wx * qy;
    res += wy * qx;
    
    for (int i = 0; i < rx; ++i) for (int j = 0; j < ry; ++j) res += men[i][j];
    return res;
}

int main() {
    i128 A, B, C, D;
    cin >> A >> B >> C >> D;
    A += OFFSET, B += OFFSET, C += OFFSET, D += OFFSET;
    
    i128 res = calc(C, D) - calc(A, D) - calc(C, B) + calc(A, B);
    cout << res << endl;
}