AtCoder Beginner Contest 190

평범한 ABC 라운드였다.

그나마 좋았던 건 F번에 수학 문제가 없었다는 정도?

 

A B C     [ 10분 ]

 

그냥 하라는 대로 하면 된다.

 

D - Staircase Sequences [ 22분 ]

 

수학 문제치곤 나도 빨리 풀 정도로 쉬운 문제였다.

등차 수열 식을 나열한 다음에 $ N*2 $ 의 소인수 중에서 만족하는 값들을 찾으면 된다.

 

E - Magical Ornament [ 38분 ]

 

문제 이해가 더 어려웠음 ㅡㅡ;;

뭐 주절주절 써있지만 요약하자면 인접할 수 있는 보석 쌍들이 주어지고 $C_{i}$ 값들을 잘 배열하여서 만들 수 있는 배열의 최소 길이를 찾는 것이 문제이다.

재배열된 $ C_{i} $ 의 인접한 보석이 인접할 수 없으면 그 사이에 아무 보석이라도 넣어서 연결될 수 있게 해야한다.

$ K $ 가 최대 17개이므로 각 $ C_{i} $ 를 $bfs$ 하여서 그 $ C_{i} $ 기준으로 모든 보석들에 갈 수 있는 경로의 최소 길이를 구한다.

그런 다음 $ dp[bit][cur] $  이란 배열을 정의한 뒤 모든 순서쌍에 대한 dp 를 돌려주면 된다.

 

F - Shift and Inversions [ 44분 ]

 

노잼 자료구조 문제다.

식이 어렵게 써져있지만 그냥 $ a $  배열 두개 합쳐놓고 $ i \, \sim  \, i+N-1 $ 구간에 $ inversion $  개수를 구하면 된다.

어떻게 푸는지 모르겠으면 세그먼트 트리에 대해 공부를 해보자

 

 

 

### 후기

 

 

수학만 집중적으로 공부해야 되나를 요즘 많이 느낀다.

수학이 안되서 쉬운데 늦게 풀거나 못 푸는 경우가 허다하기 때문이다.

 

지금 키보드랑 마우스 둘다 맛이 가버려서 너무 빡친다.

 

33점만 더 올리면 옐로다!! 

옐로 가게되면 앳코더 비기너는 다신 안할 예정이다.