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

팀연습에서 만난, 내가 업솔빙한 것 중에 재밌는 문제들을 모아보았다. 계속 업데이트 할 예정이다. 브라질 문제들은 코포에서 보면 영어로 볼 수 있다. 2020 brazil sub-regional https://www.acmicpc.net/problem/20283 https://www.acmicpc.net/problem/20284 https://www.acmicpc.net/problem/20280 https://www.acmicpc.net/problem/20289 진짜 2020브라질 서브리저널 갓-셋이다. 2019 brazil sub-regional https://www.acmicpc.net/problem/17539 https://www.acmicpc.net/problem/17535 https://www...

매일 매일 2200rating이하들 문제 못푼것중에 하나 골라서 풀고 있다. 2200짜리 문제였는데, 내가 풀이를 보지 않고 푼 것중에 가장 rating이 높은것 같다. 게다가, 정말 educational한 문제인거 같아서 마음에 들어 풀이를 쓰려고 한다. https://codeforces.com/contest/1537/problem/F Problem - F - Codeforces codeforces.com 문제 한줄요약 간선을 골라 양끝점의 가중치에 임의의 정수를 더할 수 있다. 모든 정점들의 가중치를 주어진 배열대로 만들 수 있는가? 사실 내가 최근에 푼 여러 그래프 문제풀이중에 중간에 부분 문제를 coloring으로 환원 시키는 여러가지 문제가 있었다. (이것도 애드혹 중에 하나 인가? 좀 유명한 ..

게임이론 주제는 코포나 ps에 있어서 굉장히 자주 나오는 주제이다. 애초에 수학적으로 재밌는 주제이기도 하고, ps에서는 dp라는 해결방식을 통해, 컴퓨터의 계산능력을 이용해서 무지성으로 뚫어버리는 풀이가 가능하기 때문에 자주 사용하는 것 같다. 우선 이 글에서 스프라그-그런디 정리는 배제하고 설명하겠다. (스프라그 그런디 정리는 궁금하면 꼭 찾아보길 바란다. 코포에 안나오기는 하는데, 백준 연습문제도 많고 icpc셋 돌다가 한 두번 마주친 것 같다.) game 문제를 풀 때 중요하게 생각해야 할 것은 4가지 정도가 있는 것 같다. 1.지는 상태를 회피 할 수 있는가? 2.항상 이기는 전략이 존재하는가? 3.전략은 모르지만 규칙성이 존재하는가? 4.무지성 dp로 해결이 가능한가? 1. 지는 상태를 회피 ..

slope trick 연습문제 이다. 기억이 휘발되기 전에 풀이를 써본다. https://www.acmicpc.net/problem/19693 개인적으로 이 문제는 풀이를 보지 않고 푸는 거를 추천한다. 풀면서 slope trick에 대한 이해가 깊어졌다.. 더보기 기본으로 배웠던 boj수열 문제와는 다르게 함수의 왼쪽 오른쪽 구간을 동시에 관리해야 한다. 우선 $dp(x,y)=min(dp(x-1,y))+|a(x)-x|$가 된다. 단 ($x-k

ㅋㅋㅋㅋㅋㅋ 수많은 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)에 가져오..

올림피아드 문제는 난이도보다 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..