인터랙티브 문제를 처음 접하면, 틀릴 때 도대체 왜 틀렸는지 모르겠는데 디버깅하는 방법도 알 수가 없어서 굉장히 헤매게 된다. 모든 인터랙티브 문제에서 사용할 수 있는 방법은 아니지만 인터랙터의 구현이 어렵지 않은 경우 쉽게 쓸 수 있는 코드 구조가 있어 간단히 정리해본다. 대부분의 인터랙티브 문제가 인터랙터 구현이 심플하기 때문에 이 방법만으로도 어지간해서는 로컬 디버깅을 어렵지 않게 할 수 있다. 인터랙터 흉내내기 인터랙티브 문제의 로컬 디버깅에서의 어려움은 일단 확실한 해결 방법이 하나 있다. 바로 문제에서 제시된 인터랙터(쿼리에 대한 응답을 하는 프로그램)를 그대로 로컬에 구현한 다음 이걸 이용해서 디버깅을 하는 것이다. 하지만 인터랙터를 별개의 프로그램으로 만든 후 이 인터랙터를 통해서 채점하는..
수학에서 하도 자주 얻어맞아서, 이제 두드려 맞을 때마다 어디서 머리가 깨졌는지 적어놓기로 했다. 오늘은 https://codeforces.com/problemset/problem/757/E 이 문제를 풀다 막혔는데, 어느 정도 성질을 찾은 다음 그걸로 최적화하려고 한참 애쓰다 실패했다. 그리고 힌트를 좀 얻고 싶어서 breakun님에게 수학 찬스를 쓴 결과.. 어느 정도의 사전 지식이 필요하다는 것을 알게 됐다. 이 문제를 해결하기 위해 필요했던 multiplicative function에 관한 성질을 아래에 정리해둔다. 정의 어떤 양의 정수 $n$ 에 대해, $ab = n, gcd(a, b) =1$ 이라고 하자. 이런 모든 $a, b$에 대해 $f(n) = f(a)f(b)$ 가 성립할 경우 함수 $f..
그래프 개형을 이용한 DP 최적화(slope trick)
$N$개의 숫자로 이루어진 배열이 주어진다($N \le 3000$). 각 숫자는 $1$이상 $3000$ 이하의 정수다. 이 때, 한 번의 연산을 통해 배열에서 임의 위치의 숫자 값을 $1$ 증가시키거나 $1$ 감소시킬 수 있다. 연산을 적용한 후에도 배열의 각 위치의 값은 $1$ 이상 $3000$이하여야 한다. 주어진 배열을 오름차순으로 만들기 위해 최소 몇 번의 연산이 필요할까? 예를 들어, 2 3 9 7 9 가 주어질 경우 3번의 연산을 통해 2 3 7 8 9 로 바꿔 오름차순을 만들 수 있고 이 경우가 최소다. 위 문제는 아주 간단한 DP로 풀 수 있다. - $DP(x, k)$ = 배열의 $x$번째 위치의 값이 $k$일 때, 배열의 $1 \dots x$번째 숫자를 오름차순으로 만들기 위한 최소 연산..