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

ㅋㅋㅋㅋㅋㅋ 수많은 try와 함께 결국 맞췄다. https://www.acmicpc.net/problem/2209 솔루션은 의외로(?) 쉽게 나온다. 근데, 내가 좀 바보짓을 해서 TLE가 계속 떴는데.... 두 중심지 H1,H2이 있다고 가정을 하면 1. H1끼리 연결된 곳에서 최대거리가 나오는 경우 2. H2끼리 연결된 곳에서 최대거리가 나오는 경우 3. 둘 사이를 가로지르며 최대거리가 나오는 경우 3가지 경우가 있는데, 두 노드를 중심으로 둘중에 노드를 골라서 연결한다고 가정을 하면, bruteforcing시 $O(2^N*N^2)$이된다. 조금 최적화를 해보면, H1에 A번째 노드를 연결을 해서 노드의 최장거리가 나올때의 경우로 생각을 하면, H1과의 거리가 A보다 긴녀석들을 전부 H2에 연결을 하..

https://www.acmicpc.net/problem/5484 문제설명은 힌트로 대체한다. 우리는 겹치지 않는 두개의 직사각형을 골라야 한다. 각각의 직사각형 내부에, 장미가 k개 있으면 된다! 요즘 ps에 대한 자신감이 하락하고 있었는데, 어떻게 갑자기 플레1을 내힘으로 풀었다! 어려운 문제 푸는게 확실히 구현력, 사고력에 도움이 되는듯. 정해는 모르겠는데 나는 $O(logN*N^2)$에 해결했다. 어떻게 풀까? prefixsum+binary_search+dp로 해결 가능하다. 우리가 1번 직사각형을 선택한다고 해보자. 그럼 전체 꽃밭에 있어서, 1,2,3,4,5로 나누어진다. (각각 겹치는 부분이 있다.) 1. 2차원 prefix_sum으로 우리가 원하는 범위에 꽃이 몇개있는지를 O(1)에 가져오..

사전적 의미로 생각해보면, 내 등뒤에 물이 있다. 즉, 강가를 등지고 진영을 잡는다는 의미이다. 전쟁이 활발하던 시절, 나온 용어이다. 후퇴하게 되면, 강 때문에 분명 추격당하고 말것이다. 후퇴라는 방법은 없고, 싸우는 길말고는 없도록 만들어내, 반드시 이기겠다는 각오에서 나온 말이다. 어느정도 인생에서 배수의 진을 쳐야 한다. 어제 갑자기 학점을 극도로 잘받고 싶다는 생각을 했다. 취업을 잘하기 위해? 대학원을 가고 싶어서? 장학금을 받고 싶어서? 모두 아니다. 그냥 독한 자기만족이 필요했다. computer science에 대한 전반적인 지식이 월등했으면 좋겠고, 모두가 평가당하는 이 시점에서, 성적에 대한 압도적인 우월성을 뽐내고 싶다. 어줍잖은 가식보다는 나은 동기 아닌가 배수의 진을 쳐야 한다...

올림피아드 문제는 난이도보다 1.5배정도 더 어려운거 같다. 골드 3문제인데 쉽지 않았다. 그래도 올림피아드 문제들이 질이 너무 좋은듯. 핵심적인 관찰은 원래상태에서 어떻게 변화하는지를 관찰하는 것이다. 여기서 원래 상태라고 함은, 기본적으로 정렬되어 있는 상태 즉, $1,2,3.....n$ 에서 어떻게 변화하는지를 관찰하는 것이다. 해보자! $swap(i,i+1)$은 이 문제에서 매우 매우 중요하다. 즉 인접한 원소를 swap하는 연산이 중요 접근법이다. 인접한 원소를 정렬하게 되면, (i,i+1)순서쌍이 추가되고, 끝이다. 중요한 점은 swap한번에, 순서쌍이 1개씩 추가된다는 점이다! 여기서 조금 발상적으로 중간 과정을 생략하면 주어진 순서쌍들이 (a,b)로 주어지고 a로 들어올때마다 A[a]++를..

0. counting pairs라고 이름을 붙이긴 했는데, 조건이 있고 조건을 만족하는 $(i,j)$ 쌍들을 찾아주면 된다. 조건을 변형시켜서, map으로 count해주는 방법을 최근에 많이 사용하였다. map이라는 방법론적인 측면은 제껴두고, 어떻게 문제를 접근할 건지를 위주로 살펴보자. 우선 기본문제부터 가져와봤다. https://codeforces.com/contest/1520/problem/D Problem - D - Codeforces codeforces.com 1. div3의 D번 문제이다. $a_j-a_i=i-j$ 를 만족하는 pair들을 찾는 간단한 문제. 그냥 brute force 하면 $O(n^2)$의 시간복잡도를 가질 것이고 매우 비효율적이다. 그런데 식을 이렇게 바꿔보자. $a_j+..

최근 코포 virtual과 본 라운드를 진행 하면서, 비슷하게 봤었던 문제들이 너무 많이 보였다. 내 짬이 찬건지 최근 경향이 그런건지 모르겠지만 말이다. 각설하고 well known ad-hoc들에 관한 글들을 한번쯤 정리하면서 복습하는게 좋겠다는 생각이 들었다. 이 방대한 구글신의 세계에서는 수 많은 알고리즘들과 자료구조를 소개한 좋은 블로그들이 있으니 나는 몇몇 문제 풀이에 적용할 수 있는 특징적인 글들을 한번 적어보도록 하겠다. 사실 응용수학 과제가 하기 싫어서 적고 있는게 맞다.

시험공부하기 시러서 쓰는 중 3월 31일에 문제추천 한번 하고 19일간 풀었던 골플 문제 괜찮은걸 한번 써보겠다. cf) ★는 추천도 기준입니다! 일반적으로 여기 올린건 다 재밌었던 문제들입니다 :) ★ 우주정거장 (Platinum5) 더보기 suapc모의고사 문제 스위핑 + 유니온 파인드 멋진 문제다. 스위핑에 익숙하다면 체감 난이도는 골2~골1정도라고 생각한다. ★★ 원섭동 사람들 (Platinum4) 더보기 넘무 넘무 좋은 문제 위상정렬 idea + cycle에서의 따로 판정에 대해 곰곰이 생각해보면 풀린다. 진짜 갓 문제다. 처음에 scc인가? 하고 틀리고 위상정렬 + pq에서 맞왜틀하다가 풀이를 아예 바꿔서 맞았다. ★ 특이한 수열 (Gold1) 더보기 constructive 연습 난이도는 co..

그냥 좀 괜찮은 백준 문제 모음 + 간단한 설명(숨겨 놓음) 2주마다 괜찮은 문제 대충 올릴 생각 21319 더보기 그리디 +pq 연습,hard는 아직 안품 hard는 세그인듯? 1781,2109 더보기 also 그리디 + pq 15732 더보기 이분탐색으로 푸는 좋은 문제 18316 더보기 dp연습용 문제 난이도가 뻥튀긴된 감이 있다 10938 더보기 기댓값 dp 신촌에 나온 문제 역시나 난이도가 뻥튀긴 듯? 20188 더보기 tree dp, koi문제 문제 좋다 근데 맞은 사람들 보니까 다양한 방법으로 접근한듯 나보다 좋은 풀이 많을듯 17720 더보기 좋은 문제는 아니나.. tree가 forest임을 간과한 문제 11917 더보기 좀 재밌었던 수학문제 13941 더보기 비트 dp 이정도는 되야 플레..

결론부터 말하자면 7등 장려상을 받았다. 남들이 다 푸는 문제만 맞추고 적당히 J번 뇌절하다가 죽은 대회였던거 같다. likelon,jkroll87(이하 박건)으로 팀을 짜서 나갔다. 아마 내가 올해부터는 다른 팀에서 할거 같기에(아직 팀원은 못 구했지만서도..) 이 팀으로 진행하는 마지막 대회였다. 팀 연습은 한두번했나? 어쨌든 거의 못한 상태로 대회에 들어갔다. 코로나땜에 랩실이 폐쇄된 관계로, 10시반에 만나서 신촌 스터디룸을 잡으러 갔다. 적당히 잡고 12시에 시작한다! 우리팀의 문제 풀이 전략은 이렇다. 사실 supac는 컴퓨터가 3대라 전략이 다들 비슷비슷 할 거 같지만, 내가 앞에 4문제, 건이가 중반 4문제, likelon이 후반 4문제를 잡는다. 그리고 풀이가 보이면 바로 풀고, 할만한 ..

무친 점수가 나와버렸다. 이 글을 쓰는 이유는 E번 게임이론 문제가 재밌어서 쓴다. codeforces.com/contest/1162 A번 처음에 h로 초기화 해 놓은 후, 쿼리마다 업데이트 해주면 된다. 왜 그런지는 조금만 생각해보면 된다. #include #include #include #include #include #include #include #include #include #include #define all(v) v.begin(),v.end() using namespace std; using ll = long long; const ll n_ = 2050, inf = 1e18, mod = 1e9 + 7; ll n, m, a, b, c, d, x, y, t, k, u, v, h; int mai..