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

버츄얼을 했는데, 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..

문제 요약: 수열의 인접한 원소의 차이가 k이하이면 swap할 수 있다. 위 연산을 마음껏 사용했을 때 얻을 수 있는 lexicoographically smallest 수열은? 뇌절해서 풀긴했는데, 풀어서 기부니가 좋았다. 일단 기본 아이디어는 빨리 나왔는데, 이걸 어렵게 구현해버린거 같다. 나중에 정해도 공부할 생각. 우선 사전순으로 빨른 걸 구하라고 했을 때 아이디어는, 가장 빠른걸 고른다는 그리디를 생각해 볼 수 있다. 즉 우리는 현재 상태에서 맨 왼쪽으로 옮길 수 있는 가장 작은 value를 뽑아와야 된다는 생각을 할 수 있다. 그런데 어떤 ai가 있을때 jk라면, ai는 가장 왼쪽 원소가 될 수 없다.(자명하게도) 그리고 모든 j

공식 해설을 봤는데, 나처럼 푼 사람이 없는거 같아서 올려본다. 보통 아름다운 풀이는 간선을 뒤집는다는 아이디어 이다. 이제 무지성 풀이는 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은 만들수 있을까? 만들 수 있다. 아이디어는 다음과 같다..

문제요약: N개의 pair sequence (ai,bi)가 들어온다. 그 중에 M개를 골라서 ai를 더하고 S개를 골라서 bi를 더할때 최댓값은? 오픈채팅에서 올라온 문제였는데, 재밌어보여서 풀었습니다. 처음에 접근 방식을 약간 수정해서 맞았는데, 그리디 + pq로 해결했습니다. 집합 a를 ai를 더하는 원소의 index, b를 bi를 더하는 원소의 index 이라고 정의합시다. 그렇다면, 어떤 집합 a를 고르던지, b는 고정이 됩니다. 즉 집합 a가 정해지면, a에 포함되지 않은 원소들 중 bi값이 큰 S개를 뽑은게 b가 되는게 항상 최적입니다. 그렇다면 다음과 같은 전략을 생각해볼 수 있습니다. 1. 우선 ai값이 가장 큰 M개를 a로, 그리고 남은 것들 중 bi값이 큰 S개를 b로 하는것을 초기상태..

2022년이 다가왔다. 다가온다. 원래는 글을 적을 마음이 들지 않았다. 주변사람들의 여러글을 (특히 minigb) 보거나, 네이버블로그 이웃분들의 글을 보며 타자를 치고 싶어졌다. 지금 나는 대전 본가에 내려와 있는 상태다. 단기적으로 친구들을 꽤나 여럿 만난 뒤에 올라갈 예정이고, 실제로 지금도 몇몇 친구들을 만나고 왔는데 사실 지금까지 군대에 없고 남아있는 친구들은 3수생들이다. ㅋㅋ 의대를 목표로 하는 친구도 있었고, 지방 국립대를 목표로 하는 친구도 있었다. 후자의 친구와 어제 술을 마셨는데, 전기전자와 컴공중 어디를 갈지 고민해서 나에게 물어보었다. 뜬금없지만 나는 고등학교 때부터 지금까지 삶에는 어떠한 목표에 다가가는 여정이라고 생각하고 살아왔다. 그 목표는 사람마다 다를 수 있고, 단기적일..