ABC 184

AtCoder Beginner Contest 184

AtCoder Beginner Contest 184 - AtCoder

 

A : 하면 된다.

 

B : string, cin 쓰면 공백 처리 편해서 좋다.

 

D : C번보다 관찰이 쉬웠다. 기댓값 DP

 

C : 사람에 따라 헷갈릴 수 있는 문제.  두 점이 주어지는데, 한 점을 원점으로 하도록 평행이동하는게 구현상 편하다. 대부분 2번만에 게임을 끝낼 수 있음을 관찰하면 문제가 쉽게 풀린다.

 

F : Meet in the Middle. 20개씩 쪼개고 각 ${2}^{20}$개씩 가능한 합들을 구한다. 한 배열을 정렬하고 다른 배열의 원소를 하나씩 iterating 하면서 T-x보다 작으면서 가장 큰 원소를 이분탐색하면 된다.

 

E : 알파벳 마다 set 만들어서 하나씩 지워나가는 방식으로 풀었다. set 없이는 알파벳에 한 번 도착한 순간 모든 알파벳의 최단 거리가 정해지는 것을 이용한다(고 한다).