https://www.acmicpc.net/problem/1665 1665번: 화물열차 첫째 줄에는 화물 열차 A에 연속적으로 컨테이너가 놓여 있는 구간의 개수 N이 주어진다. 이어 N줄에는 Xi와 Yi (Xi ≤ Yi)가 공백을 사이에 두고 주어지는데 이는 화물 열차 A의 Xi칸부터 Yi칸까지 컨 www.acmicpc.net 이렇게 총 5개의 상황이 벌어질 수 있고, 두 시작점이 만나는 시점부터 컨테이너가 만나는 칸 수가 늘어나다가, A의 시작이 B의 끝을 만나거나, A의 끝이 B의 시작을 만나는 경우가 생기면 칸 수가 유지되다가 하락한다. 그러다 두 끝점이 만나는 시점부터는 컨테이너가 만나는 칸 수가 0이 유지된다. 이 기울기 함수들을 누적합으로 관리해서 최대로 컨테이너 끼리 만나는 칸 수가 몇인지 ..
https://www.acmicpc.net/problem/1616 1616번: 드럼통 메시지 첫째 줄에 자연수 K, M이 주어진다. K는 2이상, M은 1이상인 자연수이다. 항상 KM ≤ 10,000,000을 만족한다. www.acmicpc.net 일단 길이가 \(M-1\) 개로 이루어진 모든 메시지에 대해 다음 메시지로 나올 수 있는 메시지들에 대해 간선을 이어준다. 이때, 간선의 가중치에는 추가되는 수가 부여된다. 아래의 경우는 \(K = 2\), \(M = 3\) 인 경우다. 여기서 오일러 경로를 사용해 지나쳐온 모든 간선들의 가중치를 저장해둔다. 저장된 값은 \(11101000\)이고, 놀랍게도, 저장된 메시지는 우리가 찾고자 하는 답이 된다. 시간 복잡도는 \(O(K^{M-1}*K)\) = \(..
www.acmicpc.net/problem/10169 10169번: 안전한 비상연락망 입력의 첫 줄에는 마을의 수 N (2 ≤ N ≤ 100,000)과 도로의 수 M (2 ≤ M ≤ 300,000)이 자연수로 주어진다. 각 마을은 1번부터 번호가 붙은 것으로 생각한다. 이후 M 개의 줄에는 각각 3개의 자연수가 주 www.acmicpc.net 도로 하나가 없어졌을때마다 mst를 구하는 문제다. 일단 두가지 경우로 나눌 수 있는데, i) 기본 mst에 포함되지 않는 도로인 경우 ii) 기본 mst에 포함된 도로인 경우 i)에 대해서는 답이 변하지 않는다는 것을 알 수 있다. 이제 ii)에 대한 처리가 문제인데, 일단 mst로 만들어진 도로로 트리를 만든다. 검은색 : mst에 포함된 도로, 빨간색 : 포함..
www.acmicpc.net/problem/18913 18913번: Graph Coloring You are given a tournament, represented as a complete directed graph (for all pairs $i,j$ of two different vertices, there is exactly one edge among $i \to j$ and $j \to i$), with $n \leq 3000$ vertices. You need to color its edges into $14$ colors. There www.acmicpc.net 내가 푼 문제중에 재밌던 문제의 풀이를 블로그에 올린다. 그래프의 간선들에 \(a\)~\(n\)의 색을 매길건데, 어떤 경로 \(x..
오랜만에 딥3가 나와서 한번 쳐봤다. 올솔이 1시간 컷이 나는거 보니 실력이 늘긴 늘었나 보다 (옛날엔 딥3 4~5솔..) D 까지는 간단하게 설명해 주겠다. (사실 거의 다 간단간단해서 편하게 듣는게 좋을 것 같다) A - Boring Apartments (1분) 그냥 시뮬레이션 문제다. #include #define x first #define y second #define pb push_back #define all(v) v.begin(),v.end() #pragma gcc optimize("O3") #pragma gcc optimize("Ofast") #pragma gcc optimize("unroll-loops") using namespace std; const int INF = 1e9; con..
Codeforces Round #672 (Div. 2) 를 쳤다. 대충 5솔정도 했는데 내 생각으로는 난이도가 A < B < C1 < D < C2 인것 같다. A - Cubes Sorting 순 내림차순인지 확인하고 맞으면 "NO" 아니면 "YES"를 출력하면 된다. #include #define x first #define y second #define pb push_back #pragma gcc optimize("O3") #pragma gcc optimize("Ofast") #pragma gcc optimize("unroll-loops") using namespace std; const int INF = 1e9; const long long mod = 998244353; typedef long lon..
오랜만에 글을 쓰는거 같다. 깔쌈했다. 풀이가 성의 없어 보여도 이해해 주길 바란다... 그냥 간단하게 끄적이는 거라 풀이가 많이 부실 할 수 있다. A - Plural Form 맨 뒷 글자가 's'면 'es'를 붙이고, 아니면 's'를 붙인다. #include #define x first #define y second #pragma gcc optimize("O3") #pragma gcc optimize("Ofast") #pragma gcc optimize("unroll-loops") using namespace std; const long long INF = 1e18; const int mod = 100003; typedef long long ll; typedef long double ld; typed..
일단 이 문제가 왜 다4인지 모르겠다. 풀이 각 좌표 마다 가장 가까운 냄새나는 사람과의 거리를 알아두면, 다익스트라 한번이면 해결된다. 가장 가까운 냄새나는 사람과의 거리는 BFS 돌면 된다. (각 냄새나는 사람마다 퍼지는 식) 솔직히 너무 간단해서 골1 정도 되는거 같다. 빨리 꿀문제를 풀러 가보자! + 이 풀이는 어떤 지인분이 정해가 아닌 꼼수같은 풀이라고 합니다. (하지만 반례가 없ㄷ..) 코드 #include #define x first #define y second using namespace std; typedef long long ll; typedef pair pi; typedef vector vec; int n,m,k,sx,sy,ex,ey; int nx[8] = {1,0,-1,0,1,1,..
Codeforces Round #515 (Div. 3) 버츄얼을 돌았다! 간단간단하게 풀이를 적겠다. Vova and Train $[L/v]-([r/v]-[(l-1)/v])$ 가 답이다. #include #define x first #define y second #pragma gcc optimize("O3") #pragma gcc optimize("Ofast") #pragma gcc optimize("unroll-loops") using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while(T--) { int L,v,l,r; cin >> L >> ..
Codeforces Round #644 (Div. 3) 를 쳤다. 호에엥 Minimal Square Problem - A - Codeforces codeforces.com $a$ > $b$ 라면 swap 해준다. 그러고 나면 한 변의 길이는 $max(2a,b)$ 임을 알 수 있다. #include #define x first #define y second #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef long double ld; typedef pair pl; typedef pair pi; int..
- Total
- Today
- Yesterday
- AtCoder
- 김춘배
- 수열과 쿼리
- PS
- Offline Dynamic Connectivity
- 세그먼트 트리
- 하이퍼
- DP
- 누적 합
- hyper
- combination
- ABC
- 정렬
- 간단한 풀이
- 쿼리
- 비요뜨 존맛
- Constructive
- 앳코더
- 1909
- codeforces
- 스택
- 오일러 경로
- gunwookim
- 냄새 싫어
- BOJ
- 비요뜨
- 알고리즘 문제 풀이
- Rabin-Karp
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |