2026년 1월 17일에 진행한 AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes)에 참가했습니다. 퍼포먼스는 1299였고, 레이팅은 7점 상승해 1233점이 되었습니다.
[0:01] A. Black Square [AC]
간단한 조건문으로 통과할 수 있는 문제입니다. 빠르게 AC를 받아 주었습니다.
[0:04] B. Two Languages [AC]
주어진 문자열의 글자 중 Takahashi어나 Aoki어에 존재하지 않는 글자가 있는지 검사한 뒤, 알맞은 답을 출력해 주면 됩니다.
[0:13] C. Sake or Water [AC]
불가능한 경우는 매우 자명하므로 찾기 쉬웠습니다. 문제는 그 다음인데, 가장 용량이 작은 컵 개에만 사케가 있을 때 물이 든 컵을 모두 마셔야 하는지 고민되었습니다. 조금 더 생각하다 더 줄일 수 있는방법이 없다고 생각하여 믿음의 제출을 했고, AC를 받았습니다.
[0:28] D. Paid Walk [AC]
문제를 보고, 구현이 복잡해 보여서 E로 잠깐 갔지만 아이디어를 얻지 못하고 돌아왔습니다. 다시 보니 방문 처리를 하지 않는 BFS처럼 구현해 주면 되겠다는 것을 알게 되었고, AC를 받아냈습니다.
[0:45] F. Must Buy [TLE, MLE]
[0:51] F. Must Buy [TLE, MLE, WA]
이 다음으로 E와 F를 번갈아 보며 어떤 것이 더 풀만할까 고민했고, 냅색 응용으로 보이는 F를 먼저 잡아 보았습니다. 냅색 + 역추적으로 에 구현해 보았으나, Python 이슈 + 최적화 부족으로 TLE와 MLE를 함께 받았습니다. WA는 덤이고요. 결국 F는 포기했습니다.
[1:16] E. A > B Substring [AC]
E를 더 건드려 보기로 했고, 의 누적 합을 사용하면 되지 않을까 하는 생각이 들었습니다. 여기에서 막혀 있다가 Inversion Counting의 반대와 같다는 결론에 도달했고, 세그먼트 트리를 구현하여 AC를 받았습니다.
결과
비록 레이팅이 7점 오르기는 했지만, 여러모로 아쉬웠던 대회였습니다. F에 2틀을 박은 것, E를 조금 더 늦게 잡은 것처럼 말이죠. 앞으로는 빠른 4솔보다 느린 5솔이 필요한 시기임도 알게 되었습니다.
