rhrnald's 코딩

드디어 군생활의 끝을 달리고 있다. 거의 마지막 휴가를 나왔으며 이제 전역일까지 부대안에 있어야 되는 날은 4일 밖에 안남았다. 아마 군대 안에서 치르는 마지막 Codeforces이지 않을까 싶다. Good Bye 군대!! 원래는 군대에서 못보는 시간대였지만 뭔가 마지막이다 하니까 뭉클하기도 하고 해서 중대장님한테 잘 부탁드려서 어찌저찌 시험을 보게 되었다. 평소보다 조금 더 긴 3시간동안 진행되었으며 총 9문제가 주어졌다. 앞 문제들의 난이도는 상당히 낮았다. ABCD까지는 조금 늦긴했지만 수월하게 풀 수 있었다. 하지만 여기까지 풀고 막혀버렸고 EF를 번갈아가면서 고민했다. 다행히 둘다 풀어내긴 했지만 고민하는데 너무 많은 시간을 쏟는 바람에 점수가 좀 낮게 나오긴 했지만 그래도 둘 다 풀었다는 것에..

오랜만에 코드포스를 돌았다. 거의 두달만에 본 시험이라 그런지 속도도 감도 많이 떨어져있었다. 그다지 만족스럽지 못했고 레이팅도 떨어졌다. 요즘 쉬엄쉬엄해서 그런가 다시 좀 열심히 해봐야겠다. ABC의 난이도가 굉장히 낮은 시험이었다. ABC 후딱 해치우고 +a 해주면 적당히 높은 점수를 챙길 수 있는 평범한 시험이었던 것 같다. 아쉽게도 나는 쉬운거에 비해 ABC에서 꽤 말렸다. A와 C에서 각각 두번씩 틀려서 패널티도 꽤 챙겼고 시간도 많이 소비했다. 1시간정도 남겼었는데 이 시간동안 D를 풀었으면 깔끔했을텐데 아쉽게 접근도 못하고 끝냈다. 구현속도가 조금 느리지만 항상 +a로 이득을 취하는 스타일이였는데 +a가 없으니까 등수가 확 낮게 나왔고 레이팅이 떨어졌다. 아직 빨간색이여서 그래도 다행이다. ..

https://www.acmicpc.net/problem/16329 16329번: Space Station The first line contains the number T, representing the number of tests. The first line that describes a test contains the three variables N M K. (1 ≤ N, M ≤ 1000) The following N–1 lines are of the form A B C (1 ≤ A ≤ B ≤ N; 0 ≤ C, K ≤ 106), meaning there www.acmicpc.net 신기한 방법으로 풀어 문제를 포스팅해봅니다. 증명을 못했는데 혹시 증명법이나 관련 정리를 알고 계시면 알려주시면 감사하..

기분 좋게 풀어서 포스팅 해보겠습니다. https://www.acmicpc.net/problem/8229 8229번: Fibonacci Representation The Fibonacci sequence is a sequence of integers, called Fibonacci numbers, defined as follows: Fib0=0, Fib1=1, Fibn=Fibn-2+Fibn-1 for n > 1 Its initial elements are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... Byteasar investigates representations of numbers www.acmicpc.net 특정 수 $n$이 주어졌을 때 $n$을 피보나치 수들의 합과 ..

위의 그림에서 ABCDE를 채울 수 없다. 조건이 너무 부족하여, 위의 그림을 만족하는 예시 여러 개를 충분히 잡을 수 있기 때문이다. 하지만 신문이나 책에 올라와 있는 스도쿠 문제를 풀 경우에는 사용할 수 있는 추가 조건이 하나 있다. 답이 유일하게 결정 된다는 것이다. C가 7인 경우를 생각해보자. 집합 { A, B } = { 8, 9 }={ D, E }가 되어야 한다. 하지만 그렇게 될 경우 답이 유일하지 않게 된다. 순서쌍 (A, B, D, E)=(8, 9, 9, 8)가 해가 되면 (9, 8, 8, 9)도 해가 되며 반대도 마찬가지로 성립하기 때문이다. 따라서 C는 7일 수 없고 자연스럽게 A=8, B=9, C=9, D=7, E=8인 것을 알 수 있다. 스도쿠 자체의 규칙만 본다면 비양심적인 방법..

Suffix Array를 $O(n)$시간만에 구성하는 방법입니다. 해당 논문의 내용을 그대로 옮겨왔습니다. 길이 n인 문자열 $T$가 주어져 있을때(1-base index), Suffix Array는 두개의 배열로 구성되어 있습니다. 첫 번째는 $A_{T}$, sort array입니다. $T$의 suffix $S_{i}$를 $T[i]$에서 시작해서 $T[n]$에서 끝나는 부분문자열로 정의할 수 있습니다. 이 때 이 $A_{T}$는 suffix들을 lexicographic 순서로 정렬 하였을때, index들의 배열입니다. $\{S_{1}, \cdots, S_{n}\}$중 lexicographic 순서로 $i$번째로 작은 suffix를 $S_{j}$라 하면, $A_{T}[i]$에는 $j$가 저장됩니다. 두 ..

다음 세 문제를 살펴보자. 1. Constructing String Cost 문자들의 집합 $L_{1}$, $L_{2}$, ... $L_{n}$이 있다. 각 집합의 크기를 $S_{1}$, $S_{2}$, ... $S_{n}$이라 하자. ($|L_{i}|=S_{i}$) 이제 n자리 문자열을 만들건데 $i$번째 문자는 $L_{i}$에서 선택할 것이다. 총 $S_{1}\cdot S_{2}\cdots S_{n}$ 종류의 문자열이 나올 것이다. 이제 이 모든 문자열들을 찾는데 걸리는 비용을 계산해야 한다. 문자열집합의 곱을 다음과 같이 정의하자. 두 문자열집합 $X$와 $Y$에 대해 $X \cdot Y = \{ a \cdot b | a \in X, b \in Y\}$. 이 때 두 문자열의 곱은 단순히 연결하는 것..

수식과 코드 넣는 법을 찾았다. 앞으로 깔끔한 포스팅을 위해 노력해야겠다. $ F(n) = \sum_{i=1}^{n} \phi(n) $를 $ O(n^{2/3}) $에 구하는 방법이다. 수학적인 지식이 필요하지만 내용이 별로 어렵지 않다. $ \phi(n) $의 정의 : $1$~$n$ 중 $n$과 서로소인 수의 개수 $ \phi(n) = x (1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})\cdots (1-\frac{1}{p_{k}}) $ (단, $ p_{1}, ..., p_{k} $는 $n$의 서로 다른 소인수들) $F(n)$을 쉽게 계산하는 방법으로는 전부 계산해서 더해주는 방법이 있다. $\phi(n)$은 재귀적으로 빠른 시간 내에 계산해 줄 수 있어서 길게 잡아도 $O(n\log..