競技プログラミング

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

競技プログラミングでミスのないコードを書くためのテンプレート
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 <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#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<T> begin()
O(1): iterator<T> 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<T> begin()
O(1): iterator<T> 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<T> S
O(1): int size()
O(n): void clear()
O(1): iterator<T> begin()
O(1): iterator<T> end()
O(logn): void insert(T key)
O(logn): void erase(T key)
O(logn): iterator<T> 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<T1, T2> M
O(1): size()
O(n): void clear()
O(1): iterator<T> begin()
O(1): iterator<T> end()
O(logn): void insert((T1 key, T2 value))
O(logn): void erase(T1 key)
O(logn): iterator<T> find(T1 key)
O(logn): M[T1 key]
// ----
T["hoge"] = 1
T.insert(make_pair("key", 100))
pair<string, int> target = *T.find("key")
target.first
target.second

スニペット

要素の走査

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

1
2
3
4
5
6
7
8
vector<int> 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要素で比較する.

1
2
3
4
5
6
7
bool compare (pair<Int, Int> a, pair<Int, Int> 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);