내가 치르게 되는 마지막 APIO는 코로나19의 영향으로 인해 집에서 치르게 되었다. 이틀 동안 대회를 열어 두고, 각 나라의 참가자들이 자신이 원하는 시간에 참가 버튼을 누르면 5시간 타이머가 켜지고 5시간 동안 3문제를 푸는 대회를 치르는 timeframe 방식으로 진행되었다. 대회가 끝나도 각 문제에 대한 답안 제출 시각을 확인할 수 있어서, 이걸 보면서 타임라인별로 내 생각과 문제에 대한 내용을 정리해보려고 한다. 문제는 여기서 확인할 수 있다. A. 벽 칠하기 B. 자매 도시 C. 즐거운 행로 ~43:55 대회를 시작하기 전에, 나는 다음과 같은 전략들을 세우고 지키려고 노력했다. 대회가 시작하면 모든 문제를 정독하기 구현 시간을 제외했을 때, 모든 문제를 1시간 이상 고민하기 부분점수라도 빨리..
2020 Google Code Jam Round 2 후기
A. Incremental House of Pancakes 대소 관계가 한 번 바뀐 후에는 양쪽에서 번갈아가며 가져가면 된다는 사실을 관찰하고 나면, 대소 관계가 언제 처음 바뀌는지, 언제 끝나는지를 각각 이분탐색해서 문제를 해결할 수 있다. 급하게 짜느라 식이 꼬여서 자꾸 Off by one 에러가 생겼다. 결국 45분이 되어서야 첫 제출을 했고, 틀렸다. 두 번의 제출을 더 한 끝에 56분쯤에 AC를 받을 수 있었다. A에서 1시간이나 사용했기 때문에 여기서 멘탈이 좀 나갔다. 이런 유형의 문제에서 자꾸 말리는 경향이 있는데, 빨리 풀지는 못해도 AC는 한 번에 받을 수 있게 노력해야겠다. B. Security Update Hidden까지 풀려면 케이스 노가다를 많이 해야 할 것 같아서 Visible..
https://codeforces.com/contest/1284 A. New Year and Naming 한국인이라서 문제 안 읽고 예제만 본 다음에 풀었다. ㅋㅋㅋ $A_{(y-1) \mod n} + B_{(y-1) \mod m}$을 출력하면 된다. B. New Year and Ascent Sequence Ascent가 없는 수열들을 개수를 세면 더 쉽다. 수열 자체에 Ascent가 있는 수열은 걸러내고, Ascent가 없다면 그 수열은 최댓값과 최솟값만 중요하다는 것을 알 수 있다. $\min s_i \geq \max s_j$인 (i, j) 쌍의 수를 세면 되는데, 이는 부분합 배열을 사용하면 해결할 수 있다. C. New Year and Permutation [l, l+c]를 수의 범위로 가지는 f..
작년 추석 즈음에 BOJ 슬랙에서 jwvg0425님이 같이 대회를 열 분들을 찾고 있다는 말을 들었다. 나도 문제를 출제해보고 싶어서 대회 출제를 하게 되었다! 7문제 중 3문제를 출제했다. 이 글은 그제 대회가 끝나고 후기 겸 작성하는 글이다. (스포일러도 약간 있다!) 대회 URL풀이 K-균등 문자열이 문제는 내가 전부터 생각해 놓았던 문제였고, 어렵지 않게 디스크립션, 데이터와 솔루션을 만들 수 있었다. 커팅 풀이가 통과할 일이 거의 없어서, (O(NM) 다음에 빠른 풀이가 O(NM * 2^N)이었다) 랜덤으로 거의 모든 데이터를 만들었다. 유니언 파인드에서 경로압축을 안 한 풀이가 시간초과가 나는 걸 확인하고 데이터는 더 이상 만들지 않았다. 대회에서 그것 때문에 TLE 난 제출도 있었는데, 뭔가..