AtCoder Beginner Contest 244

코포랑 앳코더가 같이 있었는데, 코포가 테크노컵+앳코더 블루까지 레이팅이 얼마 남지 않았었기 때문에 앳코더를 쳤다. 결과적으로는 괜찮은 선택이었던 것 같다.

 

A. Last Letter (0:00, +) *6

B. Go Straight and Turn Right (0:02, +) *30

생략

 

C. Yamanote Line Game (0:04, +) *165

앳코더에서는 처음 보는 인터랙티브였다. 하지만 인터랙티브인게 별 의미가 있는 수준은 아니었고, set등을 이용해 구현하면 쉽게 맞을 수 있다.

 

D. Swap Hats (0:08, +) *165

D번 정도면 꽤 귀찮다는 인식이 있었는데, 너무 쉬워서 놀랐다. 두 배열의 inversion parity가 일정해야 하는데, n이 3이니 대충 if문으로 구현해주면 된다.

 

E. King Bombee(0:21, +) *1125

\(N\)이 작으므로 \(O(N^2)\) 풀이를 시도해볼 수 있다. 각 정점을 \(K+1\)개 만들어주면 그래프가 DAG로 표현되고, 따라서 DP를 적용할 수 있다. DP식의 정의는 다음과 같다.

\(DP[i][j][k]\) = \(i\)번 정점을 \(j\)번째 순서로 방문했을 때, \(X\)번 정점의 방문 횟수의 홀짝이 \(k\)인 경우

전이는 잘 해주면 되며, 답은 \(DP[T][K][0]\)이 된다.

 

F. Shortest Good path (0:47, +) *1661

E와 거의 유사한 방법을 사용하면 되는데, 각 정점에 대해 state별로 정점을 하나씩 만들어주는 것으로 그래프를 모델링할 수 있다. 이 때 모든 간선의 가중치가 1이기 때문에 BFS를 사용하면 되는데, 나는 불안해서 그냥 다익스트라 썼다.

 

G. Construct Good path (X) *2117

BFS하는 방법을 잘 찾아서 잘 돌리면 된다고 하는데, 나는 센트로이드에 꽂혀서 50분동안 뻘짓했다..

 

블루는 다음 기회에