Circulation

목표Circulation 문제를 Max Flow(혹은 Min Cost Flow) 문제로 환원시킬 수 있음을 이해한다.Circulation이란Definition주어진 flow graph $G(V, E)$에 대하여,$l(a, b)$: $a$에서 $b$로 가는 flow의 lower bound,$u(a, b)$: $a$에서 $b$로 가는 flow의 upper bound,$l(a,b) \le f(a,b) \le g(a,b)$를 만족하고$inflow(x) - outflow(x) = \sum\limits_{(v, x) \in E} f(v, x) - \sum\limits_{(x, v) \in E} f(x, v) = 0$을 만족한다.$src$와 $sink$가 정의되지 않았음에 유의하라.Min cost Circulatio..

2024.12.22

코드포스 오렌지 달성

https://codeforces.com/profile/Pentagon03  UCPC 2024 직전에 달성하였습니다. 막상 원할 때는 닿을듯 말듯 하던 것이, 힘 빼고 편안하게 코딩하니 결과가 좋게 나오는 경험입니다.   Div.2 2솔 하고 다시는 안 갈줄 알았던 블루도 가봤습니다. 이후 코포를 잘 못한다는걸 인정하고 계속 응시하니 신기하게도 점점 문제가 잘 풀리네요. 항상 에듀 라운드는 등수가 잘 안 나오는 경향이 있어 꺼리다가,UCPC 전 마지막 기회라 생각하고 도전한 것이 좋은 결과로 돌아와서 정말 행복했습니다. 모두 행운을 빕니다!

2024.08.06

문제풀이 흑마법

언제나 그렇듯이 잘 풀리면 상관 없는 것들내적 해시- 존재성만 확인하면 되는 상황이라면 굳이 복잡한 라빈카프가 아니라 랜덤 포인트 N개를 뽑아 내적해시를 사용할 수 있다. https://github.com/Pentagon03/Algorithms/blob/master/Strings/Hasher_Dot.cpp 시간제한만큼만 최선을 다하기최적해를 구해야 하는 상황에서 충분히 빠른 방법이 생각이 안 날 경우, 그냥 가능한만큼만 브루트포스로 찾아본다 ?!적당한 시간 제한을 걸어놓고, 브루트포스 / 백트래킹이 그 시간을 넘었을 경우, 그때까지 찾은 답을 출력한다.예시1 https://codeforces.com/contest/1979/submission/264506642예시2 https://www.acmicpc.ne..

2024.06.07

랜덤디펜스 4일차

https://master.d66dlzauezpcp.amplifyapp.com/pentagon03랜덤디펜스를 더 돌렸다. 요번에는 어려운 문제들이 대거 등장했다.  ---8160Trains플2PASSED,  UPSOLVED 거의 보자 말자 해싱 풀이가 나왔는데, 돌발적인 다른 이슈랑 Hasher struct를 어디서 가져와서 쓰려다가 말려서 실패했다. Rolling Hash를 구현했는데 WA를 받길래 포기하고 Dot Product를 쓴 koosaga님 구현을 가져왔다.RabinKarp(Polynomial Hash)는 이제 문자열을 Shift한다던지, reverse한다던지, 다항식 자체의 성질을 사용하는게 아니라단순히 Array를 저장하고 각 위치를 swap하는 정도의 단순한 연산만 있는 경우 Dot Pr..

2024.05.29

랜덤디펜스 1~3일차

https://master.d66dlzauezpcp.amplifyapp.com/pentagon031~3일차 푼 문제 정리를 해볼까 한다. 티어는 푼 시점 기준이다. 볼드체 해놓은 문제는 어려웠던거나 추하는것.1일차12581Your Rank is Pure (Small)골546분 대망의 첫 문제고 골드가 나와서 당황했다.dp로 잘 비빌 수 있을거 같지만 n이 작아서 비트마스크로 모든 가능한 경우를 다 해보는 쪽으로 방향을 선회했다.Off-by-One error의 심각성을 확연히 알 수 있었던 문제.구현하면서도 계속 헷갈려서 46분을 허비했다. 비트마스크만 나오면 요상한? 최적화를 해서 등수를 높이려는 욕심이 있는데 여기서 이걸 확실히 느꼈다. --- 23884알고리즘 수업 - 선택 정렬 4골414분 다음 문..

2024.05.27

Min Cut과 Max Flow와의 관계

Link to original note: [[Flow Graph]]Cut은 Flow Graph에서 정점 s에서 t까지 가는 유량이 없도록 어떤 간선들을 자를 때, 그 간선들의 집합을 의미한다.  이때 Min Cut이란 간선 용량의 합이 최소가 되는 집합을 의미한다.   세줄 요약: 1) 먼저 임의의 $cut$에 의한 간선 용량의 합($|cut|$)은 $flow$의 합($|flow|$)보다 항상 크기 때문에 모든 $|cut|$은 $max(|flow|)$ 이상이다.2) 임의의 Max Flow를 흘린 다음의 그래프에서, 유량을 조금 더 흘릴 수 있는 Residual graph에서, src로부터 도달할 수 있는 정점들의 집합을 $S$라 할 때, $S$에서 $V \setminus S$까지 가는 모든 간선을 끊는 ..

2024.04.29

[요약] ICPC 전략 가이드

https://people.cs.uchicago.edu/~borja/pubs/sigcse2016-programming-contests.pdf 이 글은 Aaron Bloomfield와 Borja Sotomayor의 "A Programming Contest Strategy Guide"를 읽고 한국어로 요약한 내용입니다. 핵심을 간단하게 전달하기 위해 필자의 해석이 담겨 원문과 다른 내용이 있을 수 있습니다. 세줄 요약 저자는 북미 대학 ICPC 코치들이다. 1999년 이후로 한 번도 북미 출신 대학이 우승 못하고 항상 러시아 / 중국 / 폴란드만 우승한다는 사실에 안타까움을 금치 못한다. 따라서 "어떤 팀들이 ICPC에서 활약하는가"를 자신들의 월드파이널(줄여서 월파) 코치 경험을 통해 사례 기반 연구하여 ..

2024.04.02

USACO US Open 2009 Gold 3 - Tower of Hay

USACO US Open 2009 Gold 3 - Tower of HayBOJ 6116 케이크1st StepFirst, we can consider a greedy approach.By the following perspective: "lower the last floor, better it is"So we greedily choose the lowest last floor possible. (e.g. the last floor consists of only one bale)ex) 9 1 2 4 7 => 9 / 1 2 4 / 7 However we can find out this is wrong.Consider "3 3 1 2".choosing only '2' at the last eventually m..

2024.02.23

백준 17399 트리의 외심 - 정당성 증명

https://acmicpc.net/problem/17399트리 위 노드 a,b,c의 외심을 찾는 문제.외심은 정의는 다음과 같다.1. 동일성 -> dist(a,b) = dist(b,c) = dist(c,a) 2. 최소성 a와 b의 가장 가까운 중점을 M이라 해보자. M에서 a와 b쪽이 아닌 다른 방향 (부모 혹은 자식)으로 간 것들도 모두 a와 b의 중점이 될 것이다. 거리를 d라 하자. dist(M,c) = d라면 정답은 그대로 M이된다. (다른 방향으로 옮기면 d가 증가한다.) dist(M,c) != d라면 M을 적당히 옮겨서 c와의 거리를 맞춰야 한다. 적당히 옮겨서 외심 M이 존재한다고 가정하자. 놀랍게도 이때의 M은 (a와 c의 중점) 혹은 (b와 c의 중점) 중 하나다. 만약 M이 (a,b)..

2024.02.11

백준 단계별로 풀어보기 완.

컨벡스헐부터 정체되어 있던 백준 단계별 풀어보기를 2024-02-05 오늘 끝냈다. PS를 제대로 하기로 다짐한 사람이라면 단계별로 풀어보기부터 강의 듣듯이 빠르게 배운 후 OI / ICPC 스타일 문제를 풀어보는 것도 하나의 가장 효율적인 방법이라고 생각한다. 하나의 Tool Box를 다 채우고 시작하는 느낌.

2024.02.05

2023년 PS 생각

보호되어 있는 글입니다.

2023.03.25

[BOJ 17371] 이사 | 증명

BOJ 17317 이사의 증명 문제: 점 $P_1$, $P_2$, ... $P_N$이 주어질 때 $f(X)$를 점 $X$에 대해 $P_i$중 가장 먼 점과 가장 가까운 점의 거리의 합으로 정의하자. $min(f(X))$를 구하시오. Claim) $min(f(P_i)) = min(f(X))$ = $X$를 $P_i$ 중 하나로 정해도 그 최솟값은 전체 최솟값과 같다. Proof) $f(P_{opt}) = min(f(P_i))$ $f(X_{opt}) = min(f(X))$ $X_{opt}$에 대해 가장 가까운 점 $P_i$와 가장 먼 점 $P_j$. 삼각부등식에 의해 $\overline{X_{opt} P_i} + \overline{X_{opt} P_j} \geq \overline{P_i P_j}$ 증명은 $X..

2023.01.07

VS Code C/C++/Python 설정 방법 - PS를 위한

- UPD20241022: 스트레스 테스트 방법 컴퓨터를 초기화할 때마다 필자도 이 글을 켜고 설정한다.Python은 공식 홈페이지에서 설치 + Step A 만으로 완료된다. 목차A. 에디터 설정B. 컴파일러 설정C. C/C++ 버전 설정D. 실행방법 및 주의점E. 추가적으로 설치하면 좋은 것  A. 에디터 설정1. VSCode 다운로드 https://code.visualstudio.com/2. Code Runner 설치 https://marketplace.visualstudio.com/items?itemName=formulahendry.code-runner 3. Extension 설정에서 Run in Terminal 사용 가능 체크4. 파일> 새 파일로 .c 파일을 만들면 C/C++ 관련 확장 프로그램..

2022.10.22

Master Theorem

*The content is based on 2022 Fall EE205 MasterMethod Lecture. Master Method is a powerful black box for solving recurrences such as Divide and Conquer Method. Assumption: All subproblems have equal size. $T\left(n\right)$ is the function to analyze operation costs to solve problem size of $n$. Settings 1. Base Case: $\forall$ sufficeiently small $n$, $T\left(n\right) \le$ a constant 2. Recurren..

2022.09.14

Computing Fibonacci Sequence with Matrix Multiplication

Fibonacci Sequence as Recursive Formula $F_0 = 0$ $F_1 = 1$ $F_n = F_{n-1} + F_{n-2}, \quad ^\forall n \ge 2$ Fibonacci Sequence as Matrix Multiplication Form $\begin{vmatrix} F_n \\ F_{ n-1} \end{vmatrix} = \begin{vmatrix} 1 & 1 \\ 1 & 0 \end{vmatrix}^{n-1} \cdot \begin{vmatrix} F_1 \\ F_0 \end{vmatrix}, \quad ^\forall n\ge 1$ Fast Recursive Powering for elements of Monoid Suppose we are calcul..

2022.09.06

Full Diamond

상위 100개 문제를 다이아 이상의 문제로 채웠다! 공부하고 연습한 기록이 이만큼 쌓여서 뿌듯하다. 이제는 사고력을 키워보자. 스스로 사고해서 문제를 풀어내는 것이 재밌어지는 그날까지 연습!

2021.06.11

5월 25일 #금광, 전개도

보호되어 있는 글입니다.

2021.05.25

5월 22일 #JOI 깃발

보호되어 있는 글입니다.

2021.05.22

Slope Trick - 함수 개형을 이용한 최적화

Special Thanks to Cgiosy Slope Trick: 함수 개형을 이용한 최적화 백준 13323 BOJ 수열 1 풀이 백준 13324 BOJ 수열 2 풀이 *20210513 수정#1 2021/05/13 정보과학세미나 시간에 보고서 및 발표자료의 내용으로 사용함. WhiteBoard Tutorial BOJ수열1 BOJ수열2

2021.05.13

Centroid Decomposition - 센트로이드 분할

센트로이드 분할 1. 존재의의 센트로이드 분할 = 트리에서의 분할 정복 기법 트리에서 어떠한 문제( i.e.) 길이가 K인 경로의 개수를 구하라)를 해결해야 될 때 트리를 크기가 더 작은 서브 트리들로 분할하여 문제를 적용한다. 이때 효율적인 분할의 대표적인 기법이 센트로이드 분할이다. 2. 센트로이드란 트리의 무게중심인 정점. 트리를 어떤 정점을 기준으로 차수만큼의 서브트리들로 나눌 수 있다. 이때 모든 서브트리의 크기가 전체 트리 크기의 절반 이하일 때, 그 정점을 Centroid라 한다. Q) 센트로이드는 항상 존재하는가? A) 그렇다 증명 1) 센트로이드 탐색 알고리즘 임의의 노드를 고르자. 그 노드를 루트로 하는 트리를 생각한다. 모든 서브트리의 크기가 조건을 만족한다면 그 노드가 센트로이드다...

2021.02.28

Codeforces Round #704 Div.2

이정도로 망친건 꽤나 오랜만이다.애드혹, Case-Work 연습이 부족함을 절실히 느낀 라운드A 잔실수와 C 뇌절이 결정적인 악재로 작용했다.D,E를 봤을 때는 이미 시간이 30분밖에 안 남은 시점이었다.C에서 D,E로 빨리 넘어가면 라운드를 살릴 가능성이 더 높아졌을 거라 판단된다.A. x in {a,b,c}에 대해 min( (t+x-1)/x*x )를 구하여 출력하면 된다. 함수를 만들었는데 함수 인자를 int로 하는 실수를 저질렀다. 교훈: 간단한 함수는 lambda + auto 타입 인자를 사용하자. define도 좋은듯B. 쉬운 constructive.  뒤에서부터 큰 수 기준으로 배열을 자르면 된다.C. 파라메트릭, dp 뇌절로 쉬운 애드혹을 1시간 20분 가량 붙들었다. 펑파라메트릭이 성립할 ..

2021.02.23

Codeforces Round #703 Div.2

codeforces.com/contest/1486 총평: 전체적으로 문제 셋이 재밌었고 선방했다. 정확히 1달만에 즉흥적으로 친 코포라 걱정 반 설렘 반이였는데 오히려 더 나은 결과를 얻었다 A -> B -> C1 -> C2 -> E 순으로 풀었다. A는 직관적으로 생각하면 쉬울 것을 너무 성급하게 찍어버렸다. i -> i+1 단방향만 가능하므로 i=0->n-1까지 따라가면서 가능한지 검사하는게 중요 포인트 B는 수학. 무난히 빨리 풀었다. C1, C2는 재미있는 인터랙티브 문제이니 꼭 풀어보는 것을 추천한다. 로그를 붙이는 다양한 알고리즘에 관하여 숙고한 경험이었다. C1 구현에 오래 걸리고, C2는 자칫 못 풀 뻔 했지만 관점을 완전히 바꾸니 시간 투자 후 해결할 수 있었다. E는 다익스트라 문제인데..

2021.02.19

Solved.ac 경험치 시스템 개편

최근 Solved.ac 티어 계산 시스템이 바뀌었다. 1번 항목과 2번 항목은 푼 문제를 어려운 순으로 정렬해 상위 100개 문제를 합산하는 것으로 수정되었다. 솔브드 Slack에서 얻은 정보들이다. 첨언 하자면 푼 문제 수에 따른 값은 최대 175이며, 거의 증가하지 않는다. 675문제 푼 내가 169점이고, 9000문제 가량 푸신 구사과님이 175점인 것을 보면 된다! 기여 수에 따른 값은 최대 25이고 135문제 기여 -> 25, 8문제 기여 -> 14인 것을 보면 티어와 거의 무관한 수치다. 티어와 가장 유관한 것은 푼 문제들 중 가장 어려운 것과 클래스가 되시겠다. 다이아, 루비를 많이 풀자 의도

2021.02.08

If you are a Newbie in Competitive Programming

There was a question in Codeforces recently. Talking about "I'm such a Newbie in Codeforces.. What should I do?" This is a quite boring question since there are tons of same questions. So it got many downvotes, obviously. However, I wanted to reply him because I was once a Newbie too. My Reply If you are thinking Codeforces as a 'tutorial' site, you are in the wrong place. That's why you are get..

2021.01.21

Persistent Segment Tree 구현 메모

난 이 글의 마지막 부분을 보고 퍼시스턴트 세그먼트 트리를 익혔다. 일단 내 나름대로 퍼시스턴트 트리를 떠올려 보았다. 과거 기록을 모두 가지고 있는 트리. 때마침 수쿼22가 그런 컨셉의 문제였고, 나는 스스로 이 문제를 풀어보았다. 어떤 원소를 업데이트할 때 그 원소로 인해 업데이트 되는 세그먼트 트리의 노드는 최대 O(log N)개다. 그럼 각 쿼리마다 log N개의 '기록'만 추가된다는 것. 세그먼트 트리의 각 노드를 '벡터'로 만들어서 k번째 쿼리에는 이 값을 가지고 있었다는 사실을 저장하면 되지 않을까? 별도로 인덱스 배열을 만들어서 나는 'x번째 쿼리'때 이 값으로 변경되었어요~를 저장하면 추후 이분탐색으로 2번 쿼리를 처리할 수 있다. 구현 성공! 업뎃 쿼리는 O(log N), k번째 업뎃 ..

2021.01.18

Tree DP

www.secmem.org/blog/2019/02/10/TreeDP/ Tree DP 문제 해결 목차 1. 개요 2. 기본 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 알고리즘 공부를 하면서 오랫동안 다이나믹 프로그래밍을 그것도 트리에서 해결하는 문제를 꽤 안풀었음을 www.secmem.org codeforces.com/blog/entry/20935 DP on Trees Tutorial - Codeforces codeforces.com www.commonlounge.com/discussion/8573ee40c4cb4673824c867715a5bc7b Dynamic Programming on Trees (or Tree DP) | CommonLounge In this tutori..

2020.12.14

BFS 메모리 줄이는 방법

BFS에서 visit 배열을 거리 저장 용도로 사용하고는 한다. int vis[N][M]={}, dr[] = {1,0,-1,0}, dc[] = {0,1,0,-1}; queue q; q.push({sr,sc}); vis[sr][sc] = 1; while(!q.empty()){ auto t = q.front(); q.pop(); int r = t.first, c = t.second; for(int i=0;i0 ; sz--){ auto t = q.front(); q.pop(); int r = t.first, c = t.second; if(r==er && c==ec) return dist; for(int i=0;i0; sz--) 이 for문이 dist 값을 가진 노드들만이 큐에서 빠지게 해준다.

2020.11.18

Li Chao Tree 공부

어떤 기술 X의 사용 범위를 R(X)라 나타내자. R(Convex Hull Tree ) > 1; /* m에서 high가 더 크면 왼쪽에 high 넘기고 오른쪽 업데이트 */ if(cmp(high,low,m)) { tree[nd].v=high; if(tree[nd].r==-1) {..

2020.11.14

Knuth Optimization

DP Optimization Technique 정의 $ cost[i][j] $가 특정 조건을 만족할 때 아래 dp에서 최적화를 적용할 수 있다. $ dp[i][j] = \min_{i

2020.11.12

KOI에 등장하는 DP 문제들 #2

2020.09.29 1. 부동산 투자 codeup.kr/problem.php?id=3724 정수 수열에서 연속된 1부분 또는 2부분을 골라 합을 최대화하는 문제. 수열 길이 N 0 : Left[N] = dt[N-1] else : Left[N] = N dtR[N] : N번째 수를 시작으로 하는 구간을 고를 때, 구간합의 최대 dt[N]과 똑같이 구한다. mdt[N]을 dt[1]~dt[N] 중 max로 정의하자. mdtR도 마찬가지. dt[N] 중 최대를 구한 후 모든 합최대구간 중 max( mdt[left[N]-1] , mdtR[N+1] , 0)을 구해 2번째 합최대 구간을 구한다. 구현! 놀랍게도 반례가 있었다. 합최대구간을 고르지 않는게 최대일 수도 있다. 위 증명에서 A1,A2중 적어도 하나는 X와 ..

2020.09.29