AtCoder Beginner Contest 215

 

A~B는 따로 적지 않겠다.

 

C. One More aab aba baa (00:05, +) *178

next_permutation() 함수를 이용하면 쉽게 구현할 수 있다.

 

D. Coprime 2 (00:37, +3) *736

에라토스테네스의 체의 메커니즘을 이용한다. 모든 \(A_i\)에 대해 소인수를 구해준 후, 구한 소인수들로 에라토스테네스의 체 배열을 채워주면 된다. \(O(Nsqrt(N)\)에 문제를 해결할 수 있다.

 

E. Chain Contestant (00:84, +1) *1413

비트마스크 DP이다. \(DP[i][j][k]\)를 \(i\)번째까지의 원소를 이용해 집합 \(j\)에 해당하는 색을 사용해 끝 색을 \(k\)로 하는 경우의 수로 정의하면 DP 갱신을 \(O(10 2^{10})\)에 할 수 있고, 총 시간복잡도 및 공간복잡도는 \(10N2^{10}\)이 된다.