Computer_Study

오늘 소개할 것은 Atcoder에서 사용할 수 있는 template 모음이다. ACL은 AtCoder Library로 Atcoder 플랫폼에서 사용할 수 있는 template이다. 처음알게 된 것은 atcoder 90제 문제를 풀어보면서 다른 사람 코드를 볼 때, 확장자 헤더에 atcoder/all이 있고 코드들을 단순하게 잘 작성하길래 찾아보게 되었다. https://atcoder.jp/posts/518 AtCoder Library (ACL) - AtCoderAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp해당 포스트에서 ..

#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #define rep(i, n) for (int i = 0; i pii;typedef pair pll;typedef vector vi;typedef vector vll;const int INF = 2000000000;const double pi = 3.14159265358979;const int MOD = 100000;void yesno(bool a){ if (a) cout arr[20002];bool finished[20002]; stack S;int num = 0;int sccN = 0;int visited[20002]; int scc[20002..

#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #define rep(i, n) for (int i = 0; i dist[cur] + d[cur][next]) { dist[next] = dist[cur] + d[cur][next]; prev[next] = cur; if (!visited[next]) { q.push(next); visited[next] = true; } } } } if (prev[D] == -1) break; int flow = INF; for (int i = D; i !=..

// freopen("input.txt", "r", stdin); #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define rep1(i, n) for (int i = 1; i 0 && d[next] == -1) { d[next] = cur; q.push(next); } } } if..

int arr[100002]; vector tree[4 * 100002]; int N, M, K; void update(int bucket, int start, int end, int node, int x) { if (node < start || end < node) return; tree[bucket].push_back(x); if (start != end) { update(bucket * 2, start, (start + end) / 2, node, x); update(bucket * 2 + 1, (start + end) / 2 + 1, end, node, x); } } int query(int node, int start, int end, int left, int right, int x) { if ..

#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #define rep(i, n) for (int i = 0; i N; for (int i = 0; i > a >> b >> c; graph[a].push_back({ b, c }); graph[b].push_back({ a, c }); } //초기화 depth[1] = 1; visited[1] = 1; dist[1] = 0; //트리 만들기 dfs(1, 0, 0); //par 배열 채우기 for (int j = 1; j < 20; j++) for (..

const int INF = 1000000000;int N, D, C;vector graph[10002];int dist[10002];int a, b, c; vector path[10002];priority_queue > pq; for (int i = 1; i > pq;pq.push({ 0, C });dist[C] = 0;while (!pq.empty()){ int cost = -pq.top().first; int cur = pq.top().second; pq.pop(); if (dist[cur] cost + nCost) { dist[next] = cost + nCost; pq.push(make_pair(-dist[next], next)); } }}

https://www.acmicpc.net/problem/29157 29157번: 폭탄 피하기 성모가 이동할 수 있는 경우의 수를 출력하라. 답이 커질 수 있으므로 $1\,000\,000\,007 (=10^{9} + 7)$로 나눈 나머지를 출력한다. 단, $1\,000\,000\,007$은 소수이다. www.acmicpc.net 이 문제를 읽어보면 먼과거 봤던 격자판에서의 최단경로로 이동할 수 있는 경우의 수가 문득 생각난다. R!C! / (R+C)! 이런 공식인데 뭔가 이를 이용한 문제인것같다. 중요한것은 성모가 모든 폭탄들을 피해서 이동한다는 것이다. 장애물이 있었을때는 해당 점 옆을 지나는 경우의 수를 세줬으면 됐는데 이 문제는 폭탄이 매우 많다. 그렇다면 다른 방법으로 생각을 해보자 전체 가는 경..

https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 모듈러 역원에 대해서 잘 설명해 놓은 문제이다. 핵심은 7/3 과 같은 분수를 답으로 하는 문제들을 판별하기 위해 a × b ^(-1) mod X 형태로 만드는것이다. 여기서 b^-1 이 모듈러 곱셈의 역원이다. ll dq(ll a, ll b) { if (b == 1) return a; if (b % 2 == 1) return a * dq(a, b - 1) % MOD; ll c = dq(a, b / 2); return c * c % MOD; } fo..

#define _CRT_SECURE_NO_WARNINGS #include #include #include #define rep(i, n) for (int i = 0; i > K; rep1(i, N) { cin >> a; arr[i] = a; } init(1, N, 1); rep(i, M + K) { cin >> order; if (order == 1) { cin >> a >> b >> c; update_range(1, N, 1, a, b, c); } else if(order == 2) { cin >> a >> b; cout