Eau de Cologne

내가 PS로 돈을 벌어왔던 방식은 문제 세팅, 바운티 헌터, 튜터링이 있다. 하나씩 써보면... 문제 세팅은 (특히 기업이 주최하는) 대회에 문제를 내고 데이터를 만들고 이에 대한 보수로 돈을 받는다. 내가 PS로 돈을 벌었다고 함은 대부분은 이쪽이다. 문제 검수와 세팅을 8년 정도 해왔고 9자리 정도의 돈을 벌었던 것 같다. 전업으로 받았다면 많지 않은 금액일 거고 학교에 다니면서 틈틈이 할 수 있다는 점에서는 많은 금액이다.바운티 헌터는 (특히 기업이 주최하는) 대회에 참가해서 상금을 받아오는 방식이다. 이렇게 받았던 상금 규모가 정확히는 기억이 안 난다. 지금 내가 쓰고 있는 아이패드도, 차고 있는 애플워치도 대회에서 받았다. 한동안 오래 썼던 키보드도, 모니터도, 지금 입는 티셔츠도 대회에서 받은..

문제와 풀이 간략하게만 작성합니다.1. 연속 1$0$과 $1$로 구성된 수열이 주어집니다. 수열에 있는 $0$을 $1$로 바꾸는 데에는 한 번에 비용 $S$가 들고, $1$을 $0$으로 바꾸는 데에는 한번에 비용 $E$가 듭니다. 수열의 값을 바꿔서 $1$이 연속으로 나오는 부분이 $1$개 이하가 되도록 하고 싶습니다. 이 때의 최소 비용을 계산하세요.풀이수열을 앞에서부터 보고 다음과 같이 정의합니다.앞 $i$개의 원소에 대해 수열을 모두 $0$으로 만드는 비용: $X_i$수열을 $0...01...1$의 꼴로 만드는 비용: $Y_i$수열을 $0...01...10...0$의 꼴로 만드는 비용: $Z_i$이 때 $X_{i+1} = X_i + V_i \times E; Y_{i+1} = \min(X_{i+1},..

https://www.acmicpc.net/problem/15126https://www.acmicpc.net/problem/2378https://www.acmicpc.net/problem/3680https://www.acmicpc.net/problem/3605저작권을 사오면 문제가 나올 수도 있지 않을까?rounded up to nearest integer를 가장 가까운 정수로 "반올림"이라고 잘못 번역하지 않았으면 좋겠다

문제와 풀이 간략하게만 작성합니다.1. A보다 B가 좋아A와 B로만 이루어진 문자열이 주어질 때, 연속이고 길이가 2 이상인 어떤 부분에서도 A의 개수가 B의 개수보다 많지 않기위해 문자열에 끼워넣어야 하는 B개수의 최솟값은?풀이두 A사이의 간격을 살펴봅시다. 두 A사이에 B가 0개 혹은 1개 있으면 AA, ABA 문자열에 대해 A의 개수가 B의 개수보다 많게 됩니다. 두 A사이에 B가 2개 이상 있으면, $n$개의 A가 있는 부분문자열을 고르려고 할 때 B를 $2n-2$개 이상 골라야해서, $n \ge 2$에 대해 항상 B의 개수가 A의 개수 이상이 됩니다.2. 배달$N$개의 수를 4개씩 $\frac{N}{4}$개의 그룹으로 묶어서, 각 그룹 점수의 합을 최대화 하려고 한다. 그룹 ${a, b, c, ..

흔히 등장하는 동적계획법 아이디어들을 정리하기 위해서 만들었습니다. 다뤄볼 주제는 다음과 같습니다. 아마 난이도 순으로 정리할 것 같습니다. 일단 생각나는것 부터 쓰겠습니다: 동적계획법이란 무엇인가 냅색 Floyd-Warshall 게임 이론과 동적계획법 자릿수 동적계획법 Deque 트릭과 동적계획법 서로 다른 부분수열의 개수 CYK 알고리즘 비트DP 트리DP 끼워넣는 DP 원형 구간 DP DP와 행렬 제곱 Bostan Mori / Kitamasa Connection Profile SoS DP (Zeta Transform) 동적계획법 최적화 아이디어들 CHT Monotone Queue Divide and Conquer Lagrange Method 쓸거 너무 많네...

https://atcoder.jp/contests/abc341/tasks/abc341_g G - Highest Ratio AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 풀이: 문제를 결국 어떤식으로 바꿀 수 있냐면 누적합을 $S$라고 하면, $\frac{S_j - S_i}{j-i}$가 최대가 되는 $j$를 모든 $i = 0, \cdots, N-1$에 대해서 구해야 한다. 생각하기 편하게 수열을 뒤집어서 생각하면, $i$번째 단계에서는 $(0, S_0); \cdots; (i-1, S_{i-1})$에 대해 선을 그었을 때 ..