Hello 2023

A번은 문제를 처음에 잘못 읽어서 조금 헤멨다. L과 R이 자기 자신도 포함해서 불빛을 밝혀 주는 줄 알았는데 아니었다. 아무튼 문자열에 R 다음에 L이 나오면 0이고 RL 문자가 있으면 R의 위치고 그게 아니라면 -1이다.

 

B번은 구성적 문제고 배열을 만드는 문제다. 짝수일 땐 -1 0 -1 0 반복해서 출력해 주면 되고 홀수일 땐 식 잘 세우면 답이 나온다.

 

C번은 또 배열 문제인데 관찰이 생각보다 간단해서 순조롭게 풀었다. m번째 원소 포함 왼쪽 구간에서 어떻게 두 개로 자르던 m번이 포함된 조각이 음수가 되게 해야 한다. m번째 원소 다음부터 끝까지 구간에서는 구간을 어떻게 두 개로 자르던 m번째 다음 원소가 포함된 구간이 양수여야 한다. 이 사실을 알았으면 우선순위 큐를 써서 잘 구현하면 된다.

 

D번은 최댓값 세그먼트 트리와 멀티 셋 그리고 재귀를 사용하여 풀었다. 내가 관찰했던 특징은 먼저 가위를 사용할 때 최대의 길이로 사용하는 것이 이득이다. 그리고 항상 최대인 머리카락 먼저 확인하면서 자르는 것이 이득이다. 백준에서 히스토그램에서 가장 큰 직사각형이 생각나서 비슷하게 구현하고 해결했다. 풀이를 보니 스택으로 푸는 더 간단한 방법이 있는 것 같다. 나중에 다시 풀이를 확인해 봐야겠다. 그리고 세그먼트 트리 템플릿을 만들어 사용하는데 항상 사용할 때마다 너무 수정을 많이 해서 안 쓰는 것보다 못하는 것 같다. 이것도 한번 손봐야겠다.

 

E번 봤을 때 1시간 정도 남았었는데 최종적으로 아무것도 못 했다. 노드끼리 갈 수 있는 간선을 연결하고 한 노드에서 모든 노드로 갈 수 있다면 1 없다면 0 인건 알겠는데 사실 이렇게 푸는 건지도 잘 모르겠다. 대회 끝나고 태그를 보니 그다지 어려운 태그는 없는데 이 문제도 나중에 다시 풀이를 확인해 봐야겠다.

1/8 풀이 확인 완료 : Codeforces Round #841 (Div. 2) E. Graph Cost (tistory.com)