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

최근 코포에서 이런 문제가 나왔었다. https://codeforces.com/contest/1687/problem/C 어려운 문제였는데, 아이디어 자체가 발상적이기도 하고 몇번 본거 같아서 적어본다. (사실 대회때는 나올때마다 틀렸음.) 두 수열에 관한 연산을 시행할 때 두 수을 보는게 아니라, 두 수열의 차이를 보자. 라는게 핵심 아이디어 이다. 위의 관찰만 하게 되면, 구간의 연산들이 어떻게 바뀌는지 쉽게 살펴볼 수 있다. 두 구간의 합이 같을 때, Ai=Bi를 시행하는 것은 Ci=Ai-Bi라는 수열을 생각하면, Ci의 구간합이 0이되는 구간에, Ci들을 전부 0으로 바꿔준다는 것이다. 이를 이용하면 문제가 새롭게 바뀌게 되고, 쉽게 풀린다. https://codeforces.com/problems..

gold 에 있는 n binary search 불가 Q : 시작점을 고정시켰을 때 길이가 클 수록 좋은 구간의 값은 커지는가? A : 커진다. 그렇다면 다음 2가지 sub문제로 바꿔보자. 1. 특정 구간이 주어졌을 때 이 구간이 좋은 구간인지를 어떻게 판정할 것인가? 2. 좋은 구간이 주어졌을 때 이 구간의 값을 어떻게 판정할 것인가? 1번은 의외로 쉽게 할 수 있는데, 구간을 정렬하고, 앞에서 부터 합쳐주면서 홀 수 component가 되지 않으면 된다. 이 풀이의 정당성은 쉽게 증명 된다. 2번도 1번에서 파생되어 나온다. 합쳐나가면서 마지막으로 남는 수가 구간의 값이라는 것을 쉽게 알 수 있다. 그렇다면 본 문제를 풀어보자. 이제 핵심 아이디어는 1~39 까지 i를 순회하면서 i가 1일때는 연속된 ..

13536을 풀며 머리를 탁 치고 짠 후 24915를 풀었다. 문제 풀이에 비하인드가 있는데, 24915는 한 이틀정도 고민한 문제였다. 고민했는데 모르겠어서 풀이를 찾아보려 해도 최근 문제라서 풀이가 없다;;; 그래서 포기했었다. 오늘 학회 채점현황에서 20052 가 풀렸는데, 나는 아직 안 풀려 있길래 풀었다. 그래서 세트로 13536을 풀어보려 갔는데, 이것도 안풀림;; 한 1시간 정도 고민하다가 설마 금광 세그? 라는 생각으로 들어갔는데 바로바로 풀려버린다. 13536은 struct로 3개를 관리해주면 된다. 이건 설명이 어려워서 생략하고 24915 중심으로 설명을 해보자면, 어떤 구간 [l , r]을 나타내는 노드에 대해서 1. l> b >> c; if (a == 1)update(b - 1, c..

2022년 3월 26일 즈음 팀연습으로 풀어보았던 셋이다. 일주일이 지난 지금 시점 한 문제 빼고 모든 문제를 업솔빙해서, 풀이를 올려보고자 한다. 개인적으로 에듀케이셔널 한 느낌이 강한 측면이 있었다. 구현/지문이 더럽지 않아서 너무 좋았다. dp가 많이 나오는 듯한 경향은 우리나라랑 잘 맞는듯 하기도 하다. 연습셋 하기 전에 처음이니까 쉬운셋 하자고 해서 골랐고, 연습 때는 C D E I 4문제를 못 풀고 9솔로 마무리 했었다. 연습셋 후기는 귀찮아서 다음에 잘 봤을때 쓰겠다 ㅋㅋ. A. Circle Bounce 이 문제는 마음에 쏙 드는 문제였는데, 풀면서 얻어간 것이 좀 있었다. 우선 확률을 기약분수로 나타내는 문제에 대해서, modulo를 취하면 곱하기를 해도 일정하게 유지된다는 성질이 있는데,..

버츄얼을 했는데, educational 한 셋이어서 풀이를 올려본다. 뭣 같은 에듀코포보다 훨씬 좋다. https://atcoder.jp/contests/abc244 D. 문제 요약 ! RGB로 이루어진 순열 S와 T가 주어진다. S를 T로 만들건데, S의 임의의 원소 2개를 골라서 swap하는 작업을 정확히 1e18번 해서 바꿀 수 있는지 구해라. 잘 알려진 문제이다. S와 T의 inversion의 기우성에 따라 변하는데, segment tree등의 자료구조를 사용하면 O(nlogn)에 구할 수 있다. 근데 n이 3이다. 오버킬이다. 어떻게 할까? 이럴때는, 3C2가지 경우에 대해서 각각의 경우를 모두 따져주면 된다. 즉 S에서 R>G 였는데, T에서 RT로 가는 path 중에서 경로의 길이(사이의 간..

https://www.acmicpc.net/workbook/view/8646 많이 풀어주세요.

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나 실전 문제 풀이 부분은 자료가 미흡하여 뺐습니다. 위는 커리큘럼 이었습니다.