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

최근 코포에서 이런 문제가 나왔었다. https://codeforces.com/contest/1687/problem/C 어려운 문제였는데, 아이디어 자체가 발상적이기도 하고 몇번 본거 같아서 적어본다. (사실 대회때는 나올때마다 틀렸음.) 두 수열에 관한 연산을 시행할 때 두 수을 보는게 아니라, 두 수열의 차이를 보자. 라는게 핵심 아이디어 이다. 위의 관찰만 하게 되면, 구간의 연산들이 어떻게 바뀌는지 쉽게 살펴볼 수 있다. 두 구간의 합이 같을 때, Ai=Bi를 시행하는 것은 Ci=Ai-Bi라는 수열을 생각하면, Ci의 구간합이 0이되는 구간에, Ci들을 전부 0으로 바꿔준다는 것이다. 이를 이용하면 문제가 새롭게 바뀌게 되고, 쉽게 풀린다. https://codeforces.com/problems..

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

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들에 관한 글들을 한번쯤 정리하면서 복습하는게 좋겠다는 생각이 들었다. 이 방대한 구글신의 세계에서는 수 많은 알고리즘들과 자료구조를 소개한 좋은 블로그들이 있으니 나는 몇몇 문제 풀이에 적용할 수 있는 특징적인 글들을 한번 적어보도록 하겠다. 사실 응용수학 과제가 하기 싫어서 적고 있는게 맞다.