[Atcoder] ABC 360

A번 - A Healthy Breakfast (2:40, +, AC)

'R', 'M', 'S'가 각각 하나씩 들어있는 길이 3짜리 문자열이 주어질 때 'R'이 'M'보다 왼쪽에 있으면 'Yes'를 아니면 'No'를 출력하는 문제.
순간 당황했으나. 'R', 'M', 'S'로 만들 수 있는 모든 문자열의 개수는 6개 밖에 안되고, 이중 'Yes'를 만들 수 있는 문자는 'RSM', 'RMS', 'SRM' 총 3개 이므로 여기에 해당하는 문자열이라면 'Yes'를 출력하도록 하면 된다.

B번 - Vertical Reading (14:11, +, AC)

두 문자열 $S$와 $T$가 주어지면 $S$를 길이 $w$마다 쪼개어 배열했을 때 세로로 읽으면 문자열 $T$가 나타나는지의 여부를 판단하는 문제.
살짝 까다로웠다. 체감상 실버 5정도? 브론즈 1정도? 되는 구현 문제다.
그대로 구현해주면 맞을 수 있다. for문을 잘 사용하면 쉽게 구현할 수 있다.

C번 - Move It (24:29, +, AC)

하나의 박스에 하나의 물건만 존재하도록 만들고 싶고, 각 박스마다 각 물건이 놓여있는 상황과 한 물건을 다른 박스로 옮길 때의 비용이 나와있을 때 비용의 최솟값을 구하는 문제.
그리디적으로 생각하면 되는 문제이고, $B$번보다 오히려 더 쉬웠던 문제이다.
하나의 박스에 여러 개의 물건이 있다면, 그 박스에 담겨있는 가장 무거운 물건을 제외한 나머지 물건들을 모두 빈 박스에다 넣으면 된다.
따라서 이를 그대로 구현하면 된다.

D번 - Ghost Ants (44:40, +1, AC)

유명한 개미문제의 변형인데, 이전에 맷코컵에서 비슷한 문제를 풀었어서 그 코드를 조금 변형시켜서 문제를 해결했다.
어차피 왼쪽으로 움직이는 개미들은 서로 만나지 않으므로 왼쪽으로 움직이는 모든 개미들은 고정시키고, 오른쪽으로 움직이는 개미는 왼쪽으로 움직이는 개미에 비해 상대적으로 $2T$만큼 더 움직이므로, $2T$만큼 갔을 때 왼쪽으로 움직이는 개미를 몇 마리 만나는지를 체크하면 된다.
이때 $N$의 제한이 매우 크므로 오른쪽으로 움직이는 개미 한마리 한마리마다 체크하면 $\mathcal{O}(N^2)$의 시복도라 시간초과가 나므로, 이분탐색을 사용해서 해결하면 된다.
한번 제출해서 틀린건 bisect_left랑 bisect_right를 같이 사용해야 하는데, bisect_right만 사용해서 틀린 것이다.

E번 - Random Swaps of Balls (Not Solved)

문제를 해결하지 못했다. D번을 해결하고 시간이 넉넉하게 남아서 문제를 잡았는데, 기댓값 DP문제인 것을 보고 어려운 것을 직감.
이전에 기댓값 DP문제들을 해결했었던 기억을 되살리며 풀어보려 이리저리 애썼으나 실패했다.
(업솔빙 예정)

F번 - InterSections (Not Solved)

(업솔빙 예정)

G번 - Suitable Edit for LIS (Not Solved)

(업솔빙 예정)