競技プログラミングに関するメモ

C++

[C++] STLの型の使い分け - Qiita

競技プログラミングの入力メモ - 2冊の本を3等分

【C++】入出力のメモ - 緑茶思考ブログ

Python

Python3で競技プログラミングめも - くれなゐの雑記

Pythonで競技プログラミングする時に知っておきたいtips(入出力編) - Qiita

AOJ0016

Treasure Hunt | Aizu Online Judge

C++ だと，円周率ってどこに定義されているんだろう？

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    const double PI = static_cast<double>(acos(-1.0));

    pair<double, double> pos = {0.0, 0.0};
    int angle = 90;

    int d, a;
    while (1) {
        cin >> d;
        cin.ignore();
        cin >> a;

        if (d == 0 && a == 0) {
            break;
        }

        pos.first += cos(static_cast<double>(angle) / 180.0 * PI) * d;
        pos.second += sin(static_cast<double>(angle) / 180.0 * PI) * d;

        angle += a;
    }

    cout << -static_cast<int>(pos.first) << endl << static_cast<int>(pos.second) << endl;

    return 0;
}

AOJ0015

National Budget | Aizu Online Judge

boost::multiprecision::cpp_int 的なものを実装する必要あり．

「入力される整数は 100 桁を超えない」ということに注意する．

#include <iostream>

using namespace std;

struct big_int {
    static const int CAPACITY = 80;
    int digits[CAPACITY] = {0};

    big_int() {}
    big_int(const string &s) {
        if (s.length() > this->size()) {
            throw overflow_error("overflow");
        }
        for (int i = 0; i < s.length(); ++i) {
            // convert the character to integer
            digits[i] = (s[s.length() - 1 - i] - '0') % 10;
        }
    }

    static size_t size() {
        return CAPACITY;
    }

    big_int operator+(const big_int &rhs) {
        big_int r;
        bool carry = 0;
        for (int i = 0; i < r.size(); ++i) {
            int t = this->digits[i] + rhs.digits[i] + carry;
            carry = (t / 10) > 0;
            r.digits[i] = t % 10;
            if (carry == 1 && i == r.size() - 1) {
                throw overflow_error("overflow");
            }
        }
        return r;
    }
};

ostream& operator<<(ostream &o, const big_int &a) {
    bool skip = true;
    for (size_t i = 0; i < a.size(); ++i) {
        if (a.digits[a.size() - 1 - i] != 0 || i == a.size() - 1) {
            skip = false;
        }
        if (!skip) {
            o << a.digits[a.size() - 1 - i];
        }
    }
    return o;
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        try {
            string str_a, str_b;
            cin >> str_a >> str_b;
            big_int a(str_a), b(str_b);
            cout << a + b << endl;
        } catch (const overflow_error& e) {
            cout << e.what() << endl;
        }
    }

    return 0;
}

AOJ0014

Integral | Aizu Online Judge

#include <iostream>

using namespace std;

int main() {
    int d;
    while (cin >> d) {
        int s = 0;
        for (int x = 0; x < 600; x += d) {
            s += x * x * d;
        }
        cout << s << endl;
    }

    return 0;
}

AOJ0013

Switching Railroad Cars | Aizu Online Judge

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;

    int n;
    while (cin >> n) {
        if (n != 0) {
            s.push(n);
        } else {
            cout << s.top() << endl;
            s.pop();
        }
    }

    return 0;
}

AOJ 0012

A Point in a Triangle | Aizu Online Judge

外積を用いて判定します．

#include <iostream>
#include <array>

using namespace std;

class point {
public:
    double x, y;
    double operator%(const point &p) const;
    point operator-(const point &p) const;
};

// cross product
double point::operator%(const point &p) const {
    return this->x * p.y - this->y * p.x;
}

point point::operator-(const point &p) const {
    point r;
    r.x = this->x - p.x;
    r.y = this->y - p.y;
    return r;
}

int main() {
    array<point, 4> p;
    while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y >> p[3].x >> p[3].y) {
        double c0 = (p[2] - p[0]) % (p[0] - p[3]);
        double c1 = (p[0] - p[1]) % (p[1] - p[3]);
        double c2 = (p[1] - p[2]) % (p[2] - p[3]);

        if ((c0 > 0 && c1 > 0 && c2 > 0) || (c0 < 0 && c1 < 0 && c2 < 0)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

AOJ 0011

Drawing Lots | Aizu Online Judge

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    int w, n;
    cin >> w;
    cin >> n;

    vector<int> lots(w);
    iota(lots.begin(), lots.end(), 1);

    for (int i = 0; i < n; ++i) {
        pair<int, int> p;
        cin >> p.first;
        cin.ignore();
        cin >> p.second;
        iter_swap(lots.begin() + p.first - 1, lots.begin() + p.second - 1);
    }

    for (auto l : lots) {
        cout << l << endl;
    }

    return 0;
}