# 競技プログラミングでミスのないコードを書くためのテンプレート

Feb. 2, 2020, 1:52 p.m.

## 共通テンプレート

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 // C++ 14 #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define Int int #define loop(x, start, end) for(Int x = start; x < end; x++) #define loopdown(x, start, end) for(int x = start; x > end; x--) #define rep(n) for(int x = 0; x < n; x++) #define span(a,x,y) a.begin()+x,a.begin()+y #define span_all(a) a.begin(),a.end() #define len(x) (x.size()) #define last(x) (*(x.end()-1)) using namespace std; #define EPS 0.0000000001 class Vector2 { public: double x, y; Vector2(double x = 0, double y = 0): x(x), y(y) {} Vector2 operator + (Vector2 v) { return Vector2(x + v.x, y + v.y); } Vector2 operator - (Vector2 v) { return Vector2(x - v.x, y - v.y); } Vector2 operator * (double k) { return Vector2(x * k, y * k); } Vector2 operator / (double k) { return Vector2(x / k, y / k); } double length() { return sqrt(norm()); } double norm() { return x * x + y * y; } double dot (Vector2 v) { return x * v.x + y * v.y; } double cross (Vector2 v) { return x * v.y - y * v.x; } bool operator < (const Vector2 &v) const { return x != v.x ? x < v.x : y < v.y; } bool operator == (const Vector2 &v) const { return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS; } }; ostream & operator << (ostream & out, Vector2 const & v) { out<< "Vector2(" << v.x << ", " << v.y << ')'; return out; } istream & operator >> (istream & in, Vector2 & v) { double x, y; in >> x; in >> y; v.x = x; v.y = y; return in; } int main(void) { // code here }

## ライブラリ

### Stack

 1 2 3 4 5 O(1): int size() O(1): T top() O(1): void pop() O(1): push(T x) O(1): bool empty()

### Queue

 1 2 3 4 5 O(1): int size() O(1): T front() O(1): void pop() O(1): push(T x) O(1): bool empty()

### Vector

 1 2 3 4 5 6 7 8 9 O(1): int size() O(1): v[i] O(1) O(1): void push_back(T x) O(1): void pop_back() O(1): iterator begin() O(1): iterator end() O(n): void insert(int p, T x) O(n): void erase(int p) O(n): void clear()

### List

 1 2 3 4 5 6 7 8 9 10 int size() O(1): void push_back(T x) O(1): void pop_back() O(1): void push_front(T x) O(1): void pop_front() O(1): iterator begin() O(1): iterator end() O(1): void insert(int p, T x) O(1): void erase(int p) O(n): void clear()

### Set

 1 2 3 4 5 6 7 8 9 10 set S O(1): int size() O(n): void clear() O(1): iterator begin() O(1): iterator end() O(logn): void insert(T key) O(logn): void erase(T key) O(logn): iterator find(T key) // ---- S.find(10) == S.end()

### Map

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 map M O(1): size() O(n): void clear() O(1): iterator begin() O(1): iterator end() O(logn): void insert((T1 key, T2 value)) O(logn): void erase(T1 key) O(logn): iterator find(T1 key) O(logn): M[T1 key] // ---- T["hoge"] = 1 T.insert(make_pair("key", 100)) pair target = *T.find("key") target.first target.second

## スニペット

### 要素の走査

インデックスを使うと境界判定でミスをする可能性があるのでこちらの記法を使う.

 1 2 3 4 5 6 7 8 vector vec; for (auto el: vec) { cout << el << endl; }; for (auto it = vec.begin(); it != vec.end(); it++) { cout << *it << endl; };

### ソートの比較関数

aが前に来るべきならtrueを、そうでないならfalseを返す.

まずは第１要素で比較して、それで決まらなければ第２要素で比較する.

 1 2 3 4 5 6 7 bool compare (pair a, pair b) { if (a.first != b.first) return a.first < b.first; if (a.second != b.second) return a.second < b.second; return false; } sort(items.begin(), items.end(), compare);