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

어제 있었던 라운드의 D번을 한번 풀어 보겠다. 어제는 셋이 매우 어려웠다. A,B,C,D모두 애드혹으로 발상이 힘들었다. 하지만 퀄리티 자체는 좋은듯... 어렵긴 해도... 풀이의 핵심은 절대 0이 될 수 없는 ai를 배제하자는 것에서 나온다. a,b,c 세 수가 있다고 하자. 그리고 gcd(a,b),gcd(a,c),gcd(b,c)를 알 때, 0이 될 수 없는 수를 어떻게 찾을까? 어떤 변수 x에 대해서 gcd(0,x)=x라는 사실을 이용하자. val[a]=gcd(a,b)+gcd(a,c) val[b]=gcd(b,a)+gcd(b,c) val[c]=gcd(c,a)+gcd(c,b) 라고 정의하자. 세 수 a,b,c중에 0이 존재한다면, val이 가장 큰 것이 0이된다. 그것도 strictly 하게 크다. 이..

이렇게 쉬운걸 왜 본대회 때는 못 풀었지 ㅡㅡ... 아마 긴장해서 그런가 보다. E번 같은 유형은 내가 잘 못하는 유형이었는데 빠르게 F로 넘어갔다면 조금 더 침착해서 풀 지 않았을까... 일단 $s_c \leq n_c^2$ 라는 조건을 잘 해석해야 한다. 그런데 degree가 큰 정점 부터 살펴본다고 했을 때, x라는 정점에 degree(x)번 쿼리를 날린다고 하면, 우리는 (degree(x)+1)개의 정점으로 이루어진 connected component를 알게된다. 이들을 모두 같은 색으로 색칠하면 항상 조건을 만족한다. 왜나면, degree가 가장 큰 정점을 뽑았기 때문에 $s_c$는 degree(x)(degree(x)+1)이하이고, $n_c$는 (degree(x)+1)(degree(x)+1)이기 ..

2300 짜리 다익스트라 문제이다. https://codeforces.com/contest/1422/problem/D 풀이가 바로 보였는데 원트에 짜서 맞아서 기분이 좋았다. 일단 좌표 차이가 곧 cost인 다익스트라는 꽤 자주 나오는 유형이다. 나는 코포에서 예전에 쳐맞고 배웠는데, 즉 무슨 말이나면 abs(xi-xj)가 곧 cost인 다익스트라는 모든 정점 쌍에 대해 간선을 잇는게 아니라 x좌표가 가장 인접한 쌍에게만 간선을 이어주면 된다. 이 문제는 위 테크닉을 연습하기 좋은 문제라고 볼 수 있다. m개의 정점쌍들에 대해 x좌표 y좌표를 정렬한 후 살펴보면서 인접한 정점 쌍들에 대해서만 간선을 잇는 것이다. 그리고 다익스트라를 돌리고 나서 f와 각각의 정점 사이의 맨해튼 거리를 더해준 것 중 최소값..

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

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

정수론 문제다. 본대회때는 못풀었는데 똑같은 풀이를 "잘"구현하면 되는데 구현을 못해서 틀렸다. $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은 짝수이므로) 이거 진짜 멋..

처음으로 div2 2자리수에 2000을 뚫었습니다. 부부캐가 본캐보다 높네요. orange에 가는 그날까지... keep going...

매일 매일 2200rating이하들 문제 못푼것중에 하나 골라서 풀고 있다. 2200짜리 문제였는데, 내가 풀이를 보지 않고 푼 것중에 가장 rating이 높은것 같다. 게다가, 정말 educational한 문제인거 같아서 마음에 들어 풀이를 쓰려고 한다. https://codeforces.com/contest/1537/problem/F Problem - F - Codeforces codeforces.com 문제 한줄요약 간선을 골라 양끝점의 가중치에 임의의 정수를 더할 수 있다. 모든 정점들의 가중치를 주어진 배열대로 만들 수 있는가? 사실 내가 최근에 푼 여러 그래프 문제풀이중에 중간에 부분 문제를 coloring으로 환원 시키는 여러가지 문제가 있었다. (이것도 애드혹 중에 하나 인가? 좀 유명한 ..

무친 점수가 나와버렸다. 이 글을 쓰는 이유는 E번 게임이론 문제가 재밌어서 쓴다. codeforces.com/contest/1162 A번 처음에 h로 초기화 해 놓은 후, 쿼리마다 업데이트 해주면 된다. 왜 그런지는 조금만 생각해보면 된다. #include #include #include #include #include #include #include #include #include #include #define all(v) v.begin(),v.end() using namespace std; using ll = long long; const ll n_ = 2050, inf = 1e18, mod = 1e9 + 7; ll n, m, a, b, c, d, x, y, t, k, u, v, h; int mai..

그냥 오랜만에 심심해서 쓴다. 확실히 예전보다 실력이 는거 같다. 1700점대 실력은 나오는거 같다. 이번 라운드는 진짜 실수가 너무 많았다... 복귀해보도록 하자. A번 수열에서 어떤 원소 하나를 수열 내부의 적당한 원소 2개의 합으로 바꿀수 있다. 이때 입력으로 주어진 값 이하로 모든 수열을 바꿀 수 있는지를 묻고 있다. 당연히, 제일 작은 2개의 합으로 바꾸는것이 이득이므로 그리디하게 먹는다. 그런데 이제, 수열내의 최댓값이 주어진 값 이하이면 항상 성립한다. #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; co..