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

문제 요약: 수열의 인접한 원소의 차이가 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수생들이다. ㅋㅋ 의대를 목표로 하는 친구도 있었고, 지방 국립대를 목표로 하는 친구도 있었다. 후자의 친구와 어제 술을 마셨는데, 전기전자와 컴공중 어디를 갈지 고민해서 나에게 물어보었다. 뜬금없지만 나는 고등학교 때부터 지금까지 삶에는 어떠한 목표에 다가가는 여정이라고 생각하고 살아왔다. 그 목표는 사람마다 다를 수 있고, 단기적일..

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

문제 요약. 트리에서 게임을 진행할건데, 라는 조건을 만족할때만 $u$ 에서 $v$로 움직일 수 있다. 못움직이면 질때, 선공이 이기는 정점이 최대화 하도록, 정점의 번호를 재배열 하여라. 3번 조건을 단순화 하자. $u \leq v$라고 가정해도 일반성을 잃지 않는다. u의 켜져 있는 bit 중 가장 큰 bit 를 bit_u, v의 켜져있는 bit 중 가장 큰 bit을 bit_v라고 하면 1.bit_u u 이다. 따라서 모순 2. bit_u>bit_v라면 u>v이다. 모순 따라서 bit_u = bit_v일수밖에 없고, bit_u =bit_v라면 u^v > n; if (n == 1) { cout a >> b; v[a].push_back(b); v[b].push_back(a); } a = 1, b = 0;..

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