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

혹시라도 도움 필요한 분 있을까 해서 올립니다. 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

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

개념 복습용 문제. 방학때는 하루에 한문제씩 정수론 문제를 풀려고 한다. 아마 수학 공부하는 스터디도 할거 같은데... 하게 되면 선대할듯? 문제 풀면서 생각하게 된 점. 공부를 너무 안해서... 개념적으로 더 학습해야겠다고 느꼈다. 소수의 무한성 증명 과정 중에서, 소수가 유한하다는 가정을 하고 시작했는데, 사용되는 오일러 파이 함수가 multiplicative 라는 성질과 산술 기본정리가 소수의 무한성에 기반하고 있는 정리가 아니라는 점을 인지한 상태로 풀이를 작성해야 한다. (뭐 여기서는 자명하지만) 나중에 귀류법할때 오류가 생길 여지도 있다. 맨위의 문제는 솔직히 쉬운 개념문제인데, 개념이 없었던 나에게 개념을 각인시켜준 문제다. 착한 연습문제. 아 그리고 마지막 문제는 학교 과제였는데 과제때는 ..

2021 icpc 본선 문제. 다양한 풀이가 많은 것 같아서 내 풀이를 남기고자 한다. 문제요약. 정렬되지 않는 수열 A, B가 있다. 이때, A에서 딱하나 빼고, B에서 딱하나 빼자. 그리고 적절히 매칭했을때, 매칭된 모든 원소의 차이의 최댓값을 최소화하게 매칭됐을때 A에서 어떤 걸 빼는게 최적인가? 차이의 최댓값을 최소화를 동일하게 할 수 있다면, A중 값이 가장 작은걸 출력하라. 1. 빼는게 없다고 가정하면 정렬했을 때 매칭하는게 최적해다. 이건 well known 입니다. 증명은 넘기겠습니다. 2. 빼는게 있을 때 이런걸 생각해봅시다. 우선 정렬을 하고 matching을 합니다. 그런 상태에서 차이를 전부 계산해줍시다. 이때 최댓값을 dif라고 합시다. 최적으로 A,B를 하나씩 빼면 dif는 절대..