바쁘기보다는 게을러서 PS를 안했다. 또 수학 PS 연습을 팠는데, 슬슬 머리가 터질 것 같고 진짜 PS가 하고 싶어졌다.
2주간 진행한 연습에서 6/12문제를 해결하였다. 그 중 단순한 사전지식 문제도 꽤 포함되어 있다.
아래에 소개한 내용 외에도 5월에는 Project Euler 715를 풀었는데, 5등을 기록했고 만족하고 있다.
Thread에도 꽤 유의미한 내용을 두 개 제공해서 kudos도 많이 받고 기쁘다. 이 기회에 Eulerian 랭킹 상위권을 시도하려고 한다.
GCJ Round 2도 쳤고 작년보다는 등수가 많이 떨어졌고 뇌절도 많이했지만 아무튼 티셔츠는 받아서 다행이다.
감이 엄청 떨어진 것 같으니 시간나면 플레티넘 문제부터 다시 차근차근 푸는 연습을 해야겠다.
또한, 지금 진행되고 있는 대회인 Semi-Game Cup의 검수를 맡아서 몇 문제 풀었다. :)
BOJ 18465 Horrible Cycles (K, Ruby V)
더보기 접기
Vertex Simple Cycle을 구성하기 위해서, 왼쪽의 점 몇 개에서 각각 간선 두 개를 선택하는 것을 반복하자.
왼쪽의 점을 순서대로 보면서 사이클을 구축하는데, 이 과정에서 여러 사이클 조각들이 (연결 컴포넌트) 만들어진다.
생각을 해보면 각 컴포넌트들은 어쨌든 완전한 사이클 하나이거나 (이 경우 답에 해당하는 사이클 하나를 얻는다) '일직선' 형태의 컴포넌트가 된다.
이러한 컴포넌트를 연결하려면 끝점 두 개를 연결해야 한다. 기본적 아이디어는 이게 전부다.
이를 이용하여 동적 계획법을 할 수 있다. $dp[i][j]$는 왼쪽 $i$번째 점까지 고려했을 때, 컴포넌트가 $j$개인 경우의 수다.
식을 세우려고 해보면, 은근 중복 카운팅을 피하기가 어려움을 알 수 있다. 중복 카운팅을 피하기 위해서는 살짝 생각의 방식을 바꿔야 한다.
왼쪽의 점을 순서대로 보면서, 다음을 순서대로 한다고 생각해보자.
1. 이 점에서 '처음으로 도달 가능한' 오른쪽 점들이 있을 것이다. 이 중 사이클에 포함될 점들을 선택한다. 이들은 크기 1의 컴포넌트가 된다.
2. 만약 그 점을 사이클에 포함할 것이라면, 간선 두 개를 긋는다. 이 두 간선으로 컴포넌트 두 개를 잇는다. 이때, 잇는 점은 컴포넌트의 끝점 중 하나다.
이러면 중복 카운팅이 없어짐을 알 수 있다. 이제 문제는 '컴포넌트의 끝점' 문제다.
컴포넌트의 크기가 1인 경우는, 끝점이 하나 존재하게 된다. 그래서 '컴포넌트의 끝점 두 개를 고르는 방법'에 대한 혼란이 온다.
이를 위해서는 그래프에 방향을 주면 된다. 모든 것을 방향 그래프로 보면, 들어가는 컴포넌트와 나가는 컴포넌트를 고르기면 하면 된다.
이제 컴포넌트의 크기가 1인 경우를 특별히 처리할 이유가 없고, 계산 마지막에 같은 사이클을 두 번 세는 것만 처리하면 된다.
접기 BOJ 18630 Lati@s (J, Ruby IV)
더보기 접기
우선 각 tuple에 대해서 게임이 독립적이므로, 각각의 Grundy Number를 구한 다음 XOR 하면 된다.
게임이 굉장히 복잡해보이는데, 사실 이 게임은 단순히 Nimber Multiplication에 대한 게임 해석이다.
그러니 실제로는 각 tuple에 해당하는 Nimber Product를 모두 XOR하면 된다.
Nimber Field가 characteristic $2$임을 생각하면, 결국 주어진 행렬에서 determinant를 계산하라는 문제가 된다.
Nimber Multiplication이 꽤 시간이 오래 걸려서, 단순하게 가우스 소거를 하면 안되고 적당한 전처리를 해야 한다.
이 전처리의 구체적 내용은 Nimber Multiplication의 기본적 성질을 공부하면 파악할 수 있을 것이다. 찾아보는 것 추천.
접기 BOJ 18461 Disjoint LIS (I, Ruby IV)
더보기 접기
RSK Correspondence 에 대한 내용을 공부하면 (일단 증명은 공부 안했다 ㅠㅠ) 해결할 수 있다.
내용을 좀 읽다보면 굉장히 도움이 되는 내용을 찾을 수 있고, 그러면 문제를 Young Tableaux에 대한 것으로 바꿀 수 있다.
이제 문제는 Hook Length Formula 및 재귀를 통해서 해결할 수 있다. RSK는 제대로 한 번 봐야할듯.
접기 BOJ 10057 Pachinko (L, Ruby V)
더보기 접기
이런 문제는 기본적으로 행렬로 표현하는 것이 도움이 많이 된다.
전이행렬을 $M$이라고 하고 초기 확률분포를 $v$라 하면 $k$번의 움직임 후 확률분포는 $M^kv$가 된다.
그러니, 각 타겟에서 시행이 끝날 확률은 단순히 $v + Mv + M^2 v + \cdots $를 계산하여 얻을 수 있다.
수렴성이 보장되므로, $I+M+M^2 + \cdots = (I-M)^{-1}$을 사용할 수 있고, $(I-M)^{-1}v$를 구하면 된다.
이는 식 $(I-M)x = v$를 풀면 얻을 수 있다. 대응되는 matrix가 banded이므로, 효율적으로 가우스 소거를 하면 된다.
각 행에 영향을 주는 행이 위/아래 두 개 뿐이므로, 총 3개의 행에 대한 계수를 각 행에 대하여 저장하면 편하다.
접기 BOJ 18622 Dedenne (H, Ruby IV)
더보기 접기
DP 식 자체는 간단하고, cost 함수인 $\displaystyle \sum_{i=1}^n \left( 1 + \lfloor \log_2 i \rfloor \right)$ 및 실제로 구하고자 하는 값이 $n$에 대하여 볼록함은 쉽게 추측할 수 있고 증명도 수학적 귀납법으로 어렵지 않다. 그런데 $n$ 범위가 $10^{15}$로 매우 높고, 아마도 출제자가 답이 long long int 범위를 넘어가도록 문제를 만들지는 않았을 것이므로, 답이 증가하는 폭이 꽤 작을 것이라고 유추할 수 있다. 즉, 실제로 답의 기울기가 변화하는 점이 적을 것이라고 생각하는 것이다. 이제 기울기가 변화하는 점을 이분탐색/삼분탐색을 잘 섞어서 찾아나가면 된다. 이 아이디어만 잡으면 그 뒤는 어렵지 않은데 아이디어 잡기가 굉장히 어려운 문제인 것 같다.
접기 BOJ 17160 Traffic Blights (G, Ruby IV)
더보기 접기
갓문제. 풀이는 월파 당시 어느 정도 스포를 당해서 100% 내가 생각한 풀이는 아니다. 다음 관찰을 순서대로 한다.
1. 만약 모든 주기가 서로소라면, 중국인의 나머지 정리처럼 생각하면 결국 각 신호등이 독립적이라고 봐도 무방하다.
2. 또한, 기본적으로 두 신호등이 있으면 순수히 그 두 신호등만 봤을 때 결과는 주기의 LCM을 주기로 갖는다.
3. 그러니 한 신호등의 주기가 다른 신호등의 주기의 배수라면, 두 개를 동시에 처리할 수 있다.
4. 조금 더 생각하면, 결과적으로 주기들이 모두 prime power인 경우에 문제를 효율적으로 풀 수 있다.
$T = 2520$이라하면, 각 $1 \le u \le 100$에 대하여 $u/\text{gcd}(u,T)$가 모두 prime power가 된다.
그러니, $t \in \{0, 1, \cdots T-1\}$을 보고, 시간대가 $t \pmod{T}$인 경우만을 생각하자.
이 경우, 각 신호등에 대한 결과의 주기가 위 관찰에 의해서 prime power가 되고, 문제를 효율적으로 풀 수 있다.
이걸 각 $t$에 대해 반복한 다음 결과를 합쳐주면 문제를 해결할 수 있다. $T$를 잡는 아이디어가 미친 것 같다.
접기
