돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/7117 문제 풀이 1 직접 푼 풀이이다. 나올 수 있는 모든 숫자의 종류는 대략 3^20 이다. 이는 3486784401 으로 10^9 보다도 크기 때문에 모든 숫자에 대해서 다 해보는 것은 옳지 못하다. 딱 문제와 같은 경우에 쓸 수 있는 방식이 Meet in the Middle 방식이다. 10자리씩 끊어서 생각을 하자. 10자리 수에 대해서 각각 mod n 값을 계산해서 저장해 두자. 특히 n의 제한이 500000이기 때문에 그냥 각 나머지에 대해서 그 나머지를 가지는 최솟값을 저장해 둘 수 있다. 이후 10자리 수에 대해서 10^10을 곱한 후에 mod n 을 취한 값이 x 라고 하자. 첫 10자리는 그대로 쓰고 뒷 열자리는 ..

문제 링크 : https://www.acmicpc.net/problem/8311 문제 풀이 문제를 읽으면 상태가 (1~i 까지 중에서, 부분 배열의 마지막 숫자) 와 같은 식으로 나오기 때문에 DP를 떠올리게 된다. 하지만, $A_i$ 는 단지 수 하나이기 때문에 dp[i-1] 에서 dp[i] 로 넘어갈때 dp[i][$A_i$] 만 바뀌게 되고, 따라서 2차원 DP를 할 필요 없이 그냥 부분 배열의 마지막 숫자만 들고 있으면 된다. DP[$A_i$]에 업데이트 할 값은 $ \sum_{j=1,j\neq A_i}^{N} DP[j] $ 이기 때문에 DP의 모든 칸의 합을 변수로 들고 있으면서 DP[$A_i$] 값만 빼주고 업데이트 하면 된다. 시간 복잡도는 $O(N)$ 코드 1 2 3 4 5 6 7 8 9 1..

문제 링크 : https://www.acmicpc.net/problem/12430 문제 풀이 문제를 딱 읽으면 DP향이 느껴진다. 냅색 혹은 동전으로 낼 수 있는 가격과 비슷한 느낌이지만, 정확히 허기질 때만 다른 음식을 먹을 수 있다. A[x]를 x일 동안 버틸 수 있는 지를 체크하는 것이라면 i번째 음식은 0~$P_i$ 값을 $S_i ~ P_i + S_i$에 더하는 즉, 업데이트를 하는 효과를 가지고 있다. 하지만 동전 문제와 다른 점은 한계인 $P_i$가 존재하기 때문에 업데이트하는 순서에 따라서 나오는 결과값이 달라질 것이다. 업데이트 한다는 것은 그 음식을 먹는 가능성을 주는 것이기 때문에 정답 결과가 나오는 경우 때, 음식을 먹는 순서대로 업데이트를 실시한다면 최댓값을 얻어낼 수 있다. 그렇다..

문제 링크 : https://www.acmicpc.net/problem/17670 문제 풀이 문제에 존재하는 서브태스크이자 작은 경우인 N=2 인 경우를 살펴보자. 두 명이 각각 행복도가 절반이 되는 만족할 수 있는 위치가 $x_1, x_2$ 라고 하자. 그러면 일반성을 잃지 않고, $x_1

문제 링크 : https://www.acmicpc.net/problem/5542 문제 풀이 이 문제에서 쿼리 q개를 제거해보자. 그러면 어떻게 풀 수 있을까? 이 형태의 문제를 해결하기 위해서 생각해야 하는 핵심 아이디어는 바로 결정 문제로 바꾸어서 해결하는 것이다. 목적지까지 이동하는 도중 축제랑 가장 멀리 떨어질 수 있는 거리 x 를 구하는 것은, 축제랑 거리 x이상 떨어진 노드들만 사용해서 목적지까지 이동이 가능한지를 묻는 결정 문제로 바꿔서 생각할 수 있다. 결정 문제는 어떻게 해결할까? 일단 각 노드들이 축제로부터 거리가 얼마나 떨어져 있는지를 알아야 하기 때문에 다익스트라를 먼저 실시해야 한다. 모든 축제 정점은 거리 0으로 해놓고 pq에 넣은 후에 시작하면 모든 노드에 대해서 가장 가까운 축..

올해는 leecs0503, Lawali, 이렇게 두 분과 함께 하게 되었다. 아마도 큰 이유가 없으면 ICPC까지 함께 하게 될 정말 든든한 팀원들이라고 생각한다. Before 본선 올해는 작년과 다르게 예선 후기를 작성하지 않았다. 그 이유는 내가 진짜 개 못해서... 그래도 지금까지 팀 대회에서 이 정도로 못한 적은 없었는데, 나의 존재 여부가 팀에 솔브 수에 1도 더하지 못했을 정도였다. 그래도 무난하게 진출할 수는 있었다. 팀명은 aHR0cDovL2Vyci5vLXIua3Iv. 팀원 명도 비슷했다. 모두 행운의 편지를 인코딩한 내용이었다. 운영진이 디코딩 하고서 굉장히 화났다 카더라... 예선 팀명 정하기 예선 등록, 본선 등록, 팀노트 관련 이야기, 노트북 키보드 지참 등등의 대화와 진행이 모두 ..

NYPC 2022가 어느덧 코 앞으로 다가왔다. 많은 사람이 이미 알고 있을 테지만, 혹시 참가 신청을 안하려고 하거나 모르고 있는 사람들을 위해서 설명을 하려고 한다. Chap 1. 대회의 의미 사람들은 프로그래밍 대회에 참여한다. 정확히는 프로그래밍 대회에 참여하는 사람들이 있다.공부를 왜 하는가라는 물음에 시험에 통과하고 싶기 때문이라고 하는 사람도 있고, 자기 만족이라고 하는 사람도 있지만, 대회에 나가서 수상을 목표로 하는 사람도 적지 않다. 하지만 목표로서의 대회가 아닌 조금 다른 시선으로 바라보자. 대회는 굉장히 좋은 자기 검증 수단이자 공부 방법이다. 대회를 참가함으로써 자신이 얼마나 잘하는지, 무엇을 잘하고 무엇을 못하는지릉 알 수 있다. 또한, 정해진 시간에 동일한 문제를 같이 고민하는..

문제 링크 : https://www.acmicpc.net/problem/25351 문제 풀이 part 1 이후로 f(p)는 구간 p에 대한 중간 원소 인덱스 합을 의미한다. 또한 (a,b) 는 닫힌 구간 [a,b] 를 의미한다. 선공과 후공이 고를 수 에 대해서 생각해보자. T번째 판은 [a,b] 에서 진행된다. 두 개의 구간 p와 q에 대해서 p가 q에 속한다면 f(p)

문제 링크 : https://www.acmicpc.net/problem/10350 문제 풀이 맨처음에 문제를 딱 보고서 떠오른 생각은 가장 작은 값에서 "행동" 을 실행하는 것을 반복하면 될 것이라고 생각했다. exchange argument에 의해서 가장 작은 값의 위치에서 실행하는 것이 더 손해를 볼 일은 없다고 생각했다. 그래서 좀 더 고민을 해보다가 다른 생각이 떠오르지 않아 구현을 시작했고, 결과는 pq에 담으니 mle가 뜨게 되었다. 이를 보고서 절댓값의 감소량을 추적해보니 얼마 되지 않는다는 것을 알 수 있었다. 따라서 답은 굉장히 크다는 것을 알 수 있었고, 어떻게 해도 직접 "행동"을 한 번씩 해가면서 변화를 보는 것은 답이 될 수 없겠다고 판단하였다. 이 상황에서 내가 나아갈 수 있는 ..

요즘 codeforces 에서 문제를 푸느라고 한동안 블로그 글을 쓰지 않았다... 다시 백준에서 문제를 조금 풀게 된 만큼 한 번씩 글을 써야겠다. 문제 링크 : https://www.acmicpc.net/problem/9208 문제 풀이 (의식의 흐름) ※ 제 풀이는 intended solution에서 좀 벗어난 풀이입니다. 관련 개념 및 의도 된 풀이를 보고 싶으시면 https://qwerasdfzxcl.tistory.com/11 를 참고해주세요. 문제의 첫 방향성을 잡는 것이 힘들었다. 관찰의 실마리도 별로 보이지 않았으며, 무엇을 사용해야겠다는 감도 잡히지 않았다. 그렇기 때문에 일단 문제를 직선에서 풀기로 생각하였다. 원형 문제는 보통 길이를 두 배로 하여 직선으로 바꿀 수 있기 때문에, 그리..