✏️ 알고리즘/PS 기록

[AtCoder] ABC295 A~D 업솔빙

안녕하세요 Gliver 입니다. 이번 글은 앳코더 ABC295에 대해 업솔빙하는 글입니다. 이번 대회는 약 60분 정도부터 시작하였다. A번 - 단순 구현 문제이다. B번 - 단순 구현 문제로 $O(R^2 \cdot C^2)$으로 해결할 수 있다. - 조금 더 효율적으로 구현하면 $O(R \cdot C \cdot 9^2)$으로 해결할 수 있다. C번 - 약간의 사고력을 요구하는 문제이다. - sort(정렬)을 이용하여 $O(N \cdot \log N)$으로 해결할 수 있다. - map 자료구조를 이용하여 $O(N \cdot \log N)$으로 해결할 수 있다. D번 - 대회가 끝나고 본 문제이며, prefix xor을 이용하면 $O(N)$으로 해결할 수 있다. A. Probably English $N$개..

2022 ICPC Seoul Regional 후기

안녕하세요 Gliver 입니다. 이번 글은 2022.11.19 에 있었던 2022 ICPC Seoul Regional에 대한 글입니다. 운이 좋게 본선을 나갈 수 있게 되어 지난 예선 글에 이어서 본선 관련한 글을 써볼까 한다. 대회가 끝난 직후부터 시험과 프로젝트 때문에 거의 한 달이 지난 지금에야 글을 쓸 수 있게 되었다.. 이번 대회 또한 예선과 비슷한 전략으로 진행하게 되었다. (나와 α가 주로 키보드를 잡았으며 β는 보조를 주로 하였다) 이번 대회에서는 내가 E, I를 풀었고, α가 F, J를 풀었다. (참고로, 대회 문제는 여기에서 풀어볼 수 있다) J. Parentheses Tree (00:37) [+1] 처음에 나는 β와 I를 풀고, α는 J를 풀기로 했다. α가 J를 처음 제출했을 때 틀..

2022 ICPC Seoul Regional 예선 후기

안녕하세요 Gliver 입니다. 이번 글은 2022.10.08 에 있었던 2022 ICPC Seoul Regional 예선에 대한 글입니다. 이번 대회는 같은 학과 사람들과 함께 나가게 되었다. (편의상 α, β로 칭하겠다) 이번 대회에서 내가 푼 문제는 C, E, F이고, α가 A, K를 풀었다. 이번 대회에서 주로 α와 내가 키보드를 잡고 진행하게 되었다. 그리고 β는 문제에 대한 설명과 조언을 해주었는데 도움이 많이 됐던 것 같다. E. Gift Discount (00:17) 개발환경 세팅을 마치자마자 β가 나에게 설명해 준 문제이다. 보자마자 떠오른 아이디어는 '가장 싼 물건들을 사야겠네'와 '산 물건들 중에서 가장 비싼 물건 $a$개를 할인하면 되겠네' 였다. 이를 prefix sum을 이용하여..

[CodeForces] #819 (Div.2) A~D 업솔빙

안녕하세요 Gliver 입니다. 이번 글은 코드포스 #819 (Div.2) 에 대해 업솔빙하는 글입니다. 이번 대회는 20분 늦게 시작했는데 의외로 잘 한 것 같다..? A번 - 사고력이 조금 필요한 문제이다. B번 - 답이 여러가지 나올 수 있으니 아무거나 출력하면 되는 문제이다. - 이런 문제는 가장 간단한 경우를 기준으로 생각하는 것이 중요하다. C번 - 문제 지문이 무슨 소린지 이해를 못했다. - 대충 테스트케이스를 보고 파악한 뒤, "이렇게 하면 되겠는데?" 했는데 맞았다. D번 - 대회 도중에 문제의 핵심을 파악하지 못했다. - 끝나고 풀어보니, 정말 좋은 문제인 것 같았다. A. Mainak and Array 배열 $a$에 대해 어떠한 operation을 진행할 수 있고, 이를 1번 진행했을..

[CodeForces] #818 (Div.2) A~C 업솔빙

안녕하세요 Gliver 입니다. 이번 글은 코드포스 #818 (Div.2) 에 대해 업솔빙하는 글입니다. 이번 대회는 망했다.. C번을 풀다가 대회가 끝나 버렸다. A번 - GCD와 LCM을 잘 알고 있다면 빠르게 풀 수 있는 문제이다. - 처음에 접근을 잘 못해서 A번부터 말렸었다. B번 - 테스트케이스가 친절해서 쉽게 풀 수 있었다. - 하지만, 증명은 꽤 어려운 문제인 것 같다. C번 - 처음에 잘못된 아이디어를 떠올려서 말린 문제이다. - 결국 끝나고 1분 후에 코드를 완성하였는데 그때는 이미 늦었다. 사실, C번까지 풀었다 해도 잘한 라운드는 아닌듯 하다. A. Madoka and Strange Thoughts $\frac{lcm(a,b)}{gcd(a,b)} \leq 3$ 의미를 어떻게 해석하는..

[CodeForces] ECR 134 (Div.2) A~D 업솔빙

안녕하세요 Gliver 입니다. 이번 글은 코드포스 ECR 134 (Div.2) 에 대해 업솔빙하는 글입니다. 이번 대회는 처음 1시간 10분 정도 A~C를 풀었고, 마지막에 D번을 구현하던 중에 대회가 끝나 버렸다.. A번 - Div.2 A 에서 보기 드문 단순 구현 문제라는 생각이 든다. B번 - Div.2 B 치고는 쉬운 문제였으나, 역시나 효율성을 생각해야 하는 문제였다. C번 - Div.2 C 에 맞는 문제인 거 같았고, 개인적으로 어렵게 푼 거 같다. D번 - Div2.D 에 맞는 문제인 거 같았다. - 핵심적인 로직은 빠르게 파악했는데.. 구현을 잘 못해서 망했다. A. Image $2 \times 2$ 행렬이 주어지고 모든 색이 같아지게 만들 때 드는 최소 시행 횟수를 구하는 문제이다. $..