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

재밌는 문제였다. 이 문제를 전날 자기 전부터 고민해서 일어나서 랩실을 가서 풀었는데, 핵심적인 관찰이 재밌고, 그 결과까지의 과정이 재밌는 문제였다. 추천! Support Group에 사람이 포함되면 그 사람에 대응되는 정점을 선택한다고 하자. 관찰 1. 크기가 n인 clique가 있을 때, 그 clique에 포함되는 정점중 n-1개는 무조건 포함해야 한다. 관찰 1번은 나름 쉽게 떠올릴 수 있다. 우선 문제 지문에서부터 clique를 이용해야 하기에, 당연히 떠올릴 수 있고, 만약 n-2개 이하로 포함 한다면 포함되지 않는 새로운 clique가 생겨서 모순이다. 여기까지 생각한 후 생각의 전개는 다음과 같다. 1개만 교체할 수 있다면, 1개를 빼고 새로운 x개로 넣을 텐데, x가 1이라면 편하다.....

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

문제를 요약하면, 수열에서 인접한 두 수를 골라 1빼는 연산을 원하는 만큼 시행하여 수열의 모든 원소를 동일하게 만들 수 있도록 하는 수열의 개수 단 hi는 0이상 Hi이하 정수라는 제한 조건이 달려있다. 저 연산을 뚫어지게 살펴보면 다음과 같은 관찰을 할 수가 있다. h를 결정했다고 치고, 최종적으로 같아지게 되는 수열의 원소 값을 x라고 두면, 이 연산을 시행해서 모든 원소를 x로 만들 수 있는지를 판단하기는 쉽다. a(i)=h(i)와 h(i+1)을 골라 연산을 시행하는 경우의 수. 라고 정의하자 x=h(1)-a(1)가 되어서, a(1)가 고정된다. 그런데, x=h(2)-(a(1)+a(2))이므로, a(1)이 결정되면 a(2)도 결정된다. (지금 상태에서 h와 x는 상수이므로) 마찬가지로 모든 a값들..

사실 별건 아닌데, 내가 애초에 세그 트리를 비재귀로 구현하다 보니가, 레이지가 너무 안 익숙해서 정리한다. 레이지는 대부분 재귀로 구현하고 (비재귀 방식도 있다고는 한다...) 그렇다 보니까 구현도 길어지고 그러는데, 나중에 scpc같은 곳에서 팀노트 없을 때 빠르게 구현해 낼 자신이 없을 때 가끔 써먹어야 겠다... 아 근데 (금광 + 레이지) 세그 비재귀로 짤때는 잘 써먹고 있다. 시간복잡도는 O(nloglogn)인데, 다음과 같은 방식을 이용한다. 1. 업데이트: 구간 [L,R]에 c만큼 더하기. 세그트리 base이기 때문에 최대 특정 길이의 구간은 logN개의 노드로 분할된다. 현재 노드를 x라 하자. 이 노드에 다음과 같은 작업을 할 것이다. 이 노드의 자식 노드들을 업데이트 하지는 않는다. ..

최근 코포에서 이런 문제가 나왔었다. 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 많이 풀어주세요.