노력하는 공대생의 공부일지

https://codeforces.com/contest/1516/problem/C 문제요약: 수열에서 합이 정확히 전체 합의 절반인 부분 집합이 존재하지 않도록 만들자. 원소를 하나씩 집합에서 제외하는 연산을 할 수 있다. 풀이: 일단 정확히 합이 절반인 것이 존재하는지를 dp로 판단하자. O(100*2000*100)정도에 알 수 있다. 그렇다면 정확히 절반인 것이 존재한다고 하자. (없으면 0출력후 종료) 전체합이 홀수라면 그런 partition이 불가능함은 자명하다. 따라서 홀수인 원소가 하나라도 있다면 그 원소를 하나 제거하기만 하면된다. 그게 아니라면, 즉 홀수인 원소가 없다면, 이제 중요한 것은, 모든 원소는 짝수가 되고 즉 모든 원소를 동시에 2로 나눈다. 2로 나눈 새로운 수열에서 parti..

공식 해설을 봤는데, 나처럼 푼 사람이 없는거 같아서 올려본다. 보통 아름다운 풀이는 간선을 뒤집는다는 아이디어 이다. 이제 무지성 풀이는 scc/위상정렬을 잘 쓰는 풀이가 있다. 나는 쉬운 무지성 풀이로 풀었는데, 그냥 실제로 그래프에서 사이클 찾아주면 된다. #include //#define double long double //T.erase(unique(T.begin(),T.end()),T.end()); //written by djs100201 #define all(v) v.begin(),v.end() using namespace std; using ll = long long; using P = pair; using PP = pair; const ll n_ = 1e6 + 100, inf = 1e18..

문제요약. 300*300 grid에서 거리의 정의를 manhatan distance로 했을때 정삼각형의 개수를 구하여라. 우선 유클리드 좌표게에서 정수 좌표 3개의 꼭짓점을 가지는 정삼각형은 존재하지 않는다. tan 60이 무리수이기 때문. 따라서 이 문제에서는 맨해튼 거리로 변형되었는데, 접근 방식은 다음과 같다. 일단 점 2개가 일직선인 경우는 예외처리 했다. 이는 간단한 sweeping으로 예외 처리 할 수 있다. 이제 3점의 x와 y좌표는 전부 distinct하다고 가정하자. 우리는 이제 이런걸 생각해보자. 어떤 점 3개를 뽑았을때 이 3개의 점이 정삼각형이 되는지를 어떻게 판정할 지를 생각해보면 되자. 우선 이 3점을 x좌표로 정렬하자. 그렇다면, x좌표로 정렬하고 봤을때, y좌표의 대소관계에 ..

혹시라도 도움 필요한 분 있을까 해서 올립니다. kmp나 실전 문제 풀이 부분은 자료가 미흡하여 뺐습니다. 위는 커리큘럼 이었습니다.

야심한 새벽에 만난 너무 좋은 문제 문제풀이는 크게 2가지로 나뉘어 진다. 1. 관찰 2. dp로 문제풀기 1번이 2번보다 조금 더 어려운거 같기는 하지만 2번도 쉽지는 않다. 일단 결론부터 말하면, k개의 연속한 문자가 한번이라도 등장한다면, 이 문자열은 항상 조건에 따라 만들 수 있다. 나는 이걸 종이에 몇개 써보면서 관찰에 성공했다. 증명은 꽤나 쉬운데, 우리는 k개의 연속된 substring을 골라서 같은 문자로 치환하는 작업을 반복할 것이다. 그러면 이건 순서가 있는 작업이기 때문에 마지막에 결과 string에서는 k개의 연속된 substring이 반드시 존재해야 한다. 그렇다면 k개의 연속된 substring이 존재하는 모든 string은 만들수 있을까? 만들 수 있다. 아이디어는 다음과 같다..

못풀고 에디토리얼 봤다. 보자마자 이거쓰면 풀리겠네 라고 바로 생각하게 되는 문제. https://codeforces.com/contest/1516/problem/D 풀이는 sparse table이다. 저 단어 하나만 떠올려도 문제를 풀 수 있다. sparse table문제를 진짜 오랜만에 만났는데, 복습해야 할 거 같다. dp도 유형이 많다. 곱이 lcm이라는건 결국 구간내의 모든 원소들이 서로소여야 한다. 그럼 투포인터로 dp[x][0]-> x번째 원소부터 출발했을때 갈 수 있는 최대 거리 로 정의를 하면 sparse table로 처리할 수 있고, 구간 쿼리를 logn에 처리할 수 있다. 처음에 보자마자 mo's로 잘짜면 되겠는데? 라는 생각을 했다. 이제 업데이트 없는 구간 쿼리는 스파스 테이블로 ..

강의용 + 복습용 리스트. 계속 추가 예정 https://atcoder.jp/contests/abc230/tasks/abc230_f https://codeforces.com/problemset/problem/1613/D https://codeforces.com/problemset/problem/1614/D2

정수론 문제다. 본대회때는 못풀었는데 똑같은 풀이를 "잘"구현하면 되는데 구현을 못해서 틀렸다. $f(n)=n*(n+1)/2$라고 하자. 고른 $k$개의 sequence $a_1$ ~ $a_k$의 합을 적절히 0으로 만들수 있다는 것은, $gcd(a_1,a_2,\cdots,a_k)$가 $f(a_1)+f(a_2)+\cdots f(a_k)$ 를 나눈다는 것과 정확히 동치이다. (옮긴 수를 옮기면 되므로) 그래서 우리는, gcd를 구해서 합을 나눌 수 있는지를 살펴보는 문제로 바뀌는데, 홀수가 있는 경우에는 항상 가능하다. 따라서 모든 수가 짝수인 부분 수열 중에 $gcd$가 $f(a_i)$합을 나누는지를 살펴보자. 그런데 $(n*(n+1)/2)=n/2$ (mod n) 이다. (n은 짝수이므로) 이거 진짜 멋..

2021 icpc 본선 문제. 다양한 풀이가 많은 것 같아서 내 풀이를 남기고자 한다. 문제요약. 정렬되지 않는 수열 A, B가 있다. 이때, A에서 딱하나 빼고, B에서 딱하나 빼자. 그리고 적절히 매칭했을때, 매칭된 모든 원소의 차이의 최댓값을 최소화하게 매칭됐을때 A에서 어떤 걸 빼는게 최적인가? 차이의 최댓값을 최소화를 동일하게 할 수 있다면, A중 값이 가장 작은걸 출력하라. 1. 빼는게 없다고 가정하면 정렬했을 때 매칭하는게 최적해다. 이건 well known 입니다. 증명은 넘기겠습니다. 2. 빼는게 있을 때 이런걸 생각해봅시다. 우선 정렬을 하고 matching을 합니다. 그런 상태에서 차이를 전부 계산해줍시다. 이때 최댓값을 dif라고 합시다. 최적으로 A,B를 하나씩 빼면 dif는 절대..

어제 2021 ICPC가 끝났고, 하고 싶은 이야기를 좀 해보려 한다. 정말 너무 떨려서 풀었어야 할 문제를 못푼거 같다. 19등을 했고, 아마 수상컷이 16~18정도일거 같아서 올해목표였던 수상은 못할거 같아 너무 아쉽다 ㅠㅠ gumgood 1bin 일단 수고하셨습니다! 타임라인을 저장해놓지는 않아서, AC받은 시간대 순서대로 작성하려 한다. 존댓말과 반말이 섞여서 써 있을 수 있다. 대회가 너무 어렵다고 생각이 들었는데, 스코어 보드에서 위에팀이 E,G를 전부 푼걸 보면서 좀 현타가 왔었다. 특히 E번은 지금보면 풀 거 같은데, 내가 잡고있을때 진짜 너무 멍을 때려 버렸다. Problem B Double Rainbow (11min +1) O(n^2)이 되기 때문에 실버 문제인데, 내가 잡았고 배열 초..