소프트콘 할 때는 항상 다른 일이 있는 상태로 도서관에 있게 되더라... 최근 친 대회중에 가장 돌돌 말린 것 같아서 간단하게 후기를 쓰기로 했다. 눈을 준 건 ABCDE. 그 중 ABCD를 풀었고 등수는 13등이다. 도서관에서 굳이 서브태스크까지 긁고 싶지는 않아서 더 건드리진 않았다. A. 스승님 찾기 (n,m) = (0,0)인 경우 답은 0이다.gcd(n,m) = 1인 경우 정의에 따라 1번만에 갈 수 있다.gcd(n,m) != 1인 경우 (0,0) -> (n-1,1) -> (n,m)으로 2번만에 갈 수 있다. B. 명상 방해꾼 그냥 brute force + prefix sum...이라기보단 모든 방해꾼을 다 더한 놈을 가지고 다니면 된다.지문 독해를 잘못해서 쫄았다. 교내경시의 트라우마가 스멀스멀..

백준 링크 This section is intentionally left blank. 굉장히 좋은 문제라고 생각한다. 처음에 필요한 관찰들도 좋았고, 구현도 잘만 하면 깔끔한 문제. 정수 \(x\)의 자릿수 곱을 \(p(x)\)라고 하자. 첫 번째 관찰은 \(p(x) 0\)이므로 0이 있는 경우는 제외한다) 가능한 소인수는 \(2,3,5,7\) 뿐이고, \(2^{e_1}3^{e_2..

imeimi, Diuven과 함께 unofficial contestant로 참가했다. 팀명은 InDexedTree로 정했었는데 강제로 Challenge-SSHS로 변경당했다. 결과는 9solve + 52팀 중 7등. (스코어보드엔 반영되지 않았다)페널티를 신경썼으면 바로 앞의 TCG를 잡을 수도 있었을 것 같고, 또 반대로 바로 뒤의 DeltaMAX 팀이 무리하게 기만만 안했어도 우리가 질 수 있었다는 생각이 든다.온사이트 대회는 정말 꿀잼이었고 팀 조합도 괜찮아서 대학 가서도 계속 시도해보고픈 팀이었다. 민폐가 되지 않을 수 있다는 전제 하에 말이지 ㅁㄴㅇㄹ 전략도 괜찮았고, 팀 전체적으로 봤을 때는 성공한 운영이었지만 개인 Contestant로는 조금 아쉬운 마음이 남아서 후기를 작성하기로 했다. 의..

(17.11.23 시작)푼 거라곤 D 하나지만... (그것마저도 솔루션 까봄) 앞으로 업데이트됩니다. BOJ 번호는 3405 ~ 3415. A. Kingdoms B. Who wants to live forever? C. Chemist's vow Tag : Implementation, Dynamic Programming http://icpc.me/3408 주기율표 원소들을 웹에서 긁어서 스트링 배열에 저장한다. 한 글자 원소는 14개, 나머지 원소는 100개가 나온다. (2016년에 추가된 Nh, Mc, Ts, Og는 사용하면 안된다!) 입력 문자열을 \(S\)라고 두고,\(dp[x][i]\)를 \(x\)글자짜리 원소를 사용해서 \(S_{1}\cdots S_{i}\)를 만들 수 있는가? 와 같은 boole..

BOJ 링크 내가 아는 풀이만 3개다. 3개 다 멋진 풀이라서 공유하기로 한다. 3개 풀이 모두 다익스트라 전처리가 필요하다. 대신 시작 정점이 축제가 열리는 K개의 정점 모두다! 다익스트라는 시작 정점이 꼭 하나일 필요가 없다. 납득이 가지 않는다면 시작 정점들을 모두 하나의 큰 정점으로 연결한다고 생각해 보자. 시작 정점이 1개인 다익스트라로 바뀐다. 구현도 간단하다. 맨 처음 heap에 (cost = 0, vertex = 시작 정점)을 넣을 때 K개를 다 넣고 일반적인 다익스트라를 돌리면 된다. 이 과정이 끝나면 모든 정점 \(v\)에 대해 축제가 열리는 정점까지의 최단거리인 \(d[v]\)를 얻는다. 이제 쿼리를 오프라인으로 처리할 건데, 처리 방법이 3개의 풀이에서 모두 조금씩 다르다. 1. S..

문제 링크 : http://boj.kr/14869 This section is intentionally left blank. Tag : Dynamic Programming, Sliding window, Deque, Pigeon hole principle(...) \(dp(i,j)\) : 학원 \(i\)에서 \(j\)번째 강좌를 들었을 때의 최소 비용. 즉 우리가 구하고자 하는 답. \(S(i,j)\) : 학원 \(i\)에서 강좌를 \(1\)부터 \(j\)까지 다 들을 때 드는 비용의 총합. 즉, 비용 배열의 부분합.\(B_i\) : 학원 \(i\)의 불허용 학원. 다음과 같은 dp 식이 성립한다. (엄밀히는 예외가 좀 있지만 뒤에서 처리하자)$$ dp(i,j) = \min_{\begin{cases} k\..