[Codeforces] Round #483 (Div. 1)

http://codeforces.com/contest/983

 

Div. 1 Only 라운드는 처음으로 쳐봤습니다. 객관적으로 아직 Div1C를 풀 실력은 되지 않아서 A와 B를 빠르게 푸는게 중요할 것 같네요.

 

A - Finite or not?

 

p/q(p, q는 서로소)가 base b에서 유한소수일 조건은 p가 0이거나, q의 모든 소인수가 b의 소인수일 때입니다. 이를 확인하려면 q=1이거나 gcd(b,q)=1일 때 까지 q를 gcd(b,q)로 나누면 됩니다. 끝난 후에 q=1이면 finite, q!=1이면 infinite입니다. 살짝의 최적화가 필요한데 코드를 확인하면 될듯합니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20483/A.cpp

 

B - XOR-piramid

 

언뜻 보면 segment tree를 써야할 것 같지만 DP로 해결이 가능합니다. $D1[i][j] = f(a_i, a_{i+1}, ... , a_j)$라고 하면 $D1[i][j] = D1[i+1][j] \oplus D1[i][j-1]$이므로 DP 테이블을 $O(N^2)$으로 채울 수 있고, $D2[i][j] = max(D1[i][i], D1[i][i+1], ..., D1[i][j])$또한 $O(N^2)$으로 구할 수 있고 최종적으로 $D3[i][j] = max(D2[i][j], D2[i+1][j], .., D2[j][j])$은 $D3[i][j] = max(D2[i][j], D3[i+1][j])$으로 $O(N^2)$에 구할 수 있어 입력받은 쿼리의 $i,j$에 대해 $D3[i][j]$를 반환하면 됩니다. 저는 $O(NQ)$로 짰는데 정말 간신히 (1.8s) 통과했습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20483/B.cpp

 

A, B를 푼 사람이 다들 고만고만하게 모여있었는데 hack 2번을 성공해서 등수가 확 올라갔습니다. 어떻게 보면 운이 좀 좋았네요. 장기적으로 Div1C를 풀어낼 실력이 갖추어져야 오렌지를 안정적으로 갈 수 있을 것 같습니다.