CCO 2022 Day 1을 돌아 만점을 받았다. 2시간 16분 걸렸는데 상당히 쉬운 셋이라는 느낌이 들었다. [BOJ 25220] Rainy Markets (0:50) 일단 해가 존재하는지부터 판별해보자. 각 사람에 대해, 왼쪽 정류장에 가는 경우를 $L$, 우산을 사는 경우를 $M$, 오른쪽 정류장에 가는 경우를 $R$이라고 한다. 왼쪽부터 보면서 최대한 $L$, $M$, $R$ 순으로 그리디하게 배정한다. 자리가 없는 경우 불가능, 아니면 가능이 된다. 이제 해가 존재할 때, $\sum M$을 최소화시키는 방법을 찾아보자. 이번에는 오른쪽부터 보면서, $L$에 있는 사람을 최대한 $R$로 옮기고, 그래도 자리가 남으면 $M$에 있는 사람을 $R$로 옮기고, 그래도 자리가 남으면 $M$에 있는 사람을..
CCO 2022 Day 2를 돌아 49/75점(7 17 25)을 받았다. 당시 대회 스코어보드가 남아있지 않아 정확한 난이도를 알 수 없지만, 평범한 점수인 것 같다. [BOJ 25224] Good Game (3:26) 세 문제를 처음 읽었을 때 쉬워 보이는 문제가 없어서 열심히 긁었다. 결국 거의 모든 서브태스크를 하나하나씩 긁으면서 시간이 꽤 걸렸는데, 긁다 보니 3번 풀이가 보였다. Subtask 2는 파일 합치기 유형 DP를 이용해 해결할 수 있다. 사실 이거랑 정확히 똑같은 건 아니고, 조금 다른 점이 있긴 하지만 코드가 거의 똑같다. $O(N^3)$에 풀 수 있다. Subtask 3부터는 조금의 관찰이 필요하다. 스택으로 접근하자. 스택에 문자를 계속 쌓다가, 어떤 문자가 맨 위에 2개 이상 ..
CEOI 2017 Day 1 셋을 돌아 245 (100 100 45)점을 받았다. 비교적 쉬운 셋이었는데 1번에서 뇌절하고 2시간 반 정도를 날려서 3번을 생각할 충분한 시간을 확보하지 못했다. [BOJ 15247] B. Sure Bet (0:16) 처음 7분 동안 문제를 읽었다. 이후 B번이 가장 쉬워 보여서 접근했다. $N=1000$으로 잘못 보고 제곱을 짜 60점을 받았는데, 제곱과 $O(N \log N)$ 난이도가 크게 다르지 않아 바로 100점을 받았다. 0에 베팅할 개수를 $A$개, 1에 베팅할 개수를 $B$개라고 하자. $A$와 $B$가 정해지면, 해당하는 베팅 중 가장 큰 것들만을 고르는 것이 이득이다. 따라서 최적의 $A$와 $B$를 정해야 한다. 0이 나왔을 때 버는 돈을 $X_A$, ..
예전에 참가했던 대회 업솔빙은 언젠가는 해야 하는 일이다. 그리고 2023 IOI 선발고사가 가까워진 지금 해보려고 한다. 이미 모든 문제 풀이를 어렴풋이 들은 적이 있지만 기억이 가물가물하기도 하고, 적어도 IOI APIO 기출을 대학에 가기 전에 최대한 풀어놓으려고 한다. 그 뒤로는 OI 문제들보다는 ICPC 문제들에 집중해야 하기 때문에... 간단한 후기 대회 때 사용했던 전략을 간단히 풀어 보자면, IOI 2022 당시 컨디션이 별로 좋지 않았어서 (대회 직후 코로나 확진), 큰 욕심을 내지 않고 섭테주의 전략으로 모든 문제를 풀었다. 사실 컨디션이 좋았어도 섭테 전략으로 가긴 했겠지만, 그랬다면 코딩 속도가 좀 더 빨랐을 것이다. 나는 비교적 구현 속도가 남들보다 빠른 편이라고 생각하기에 평소에..
COI 2021을 세 시간 동안 돌았다. 원래 5시간 셋이었는데 오늘도 5시간을 내기 어려웠다. 3시간 동안 302.4122점을 받았다. 대회 3등에 해당하는 성적이다. A. Autobahn 각 사람이 탑승한 시각, 벌금을 내기 시작해야 하는 시각(다른 조건은 무시하고 $l_i + t_i$ 만 생각), 내린 시각을 정리하면 대략 $3N$개 정도의 구간으로 전체 시간을 나눌 수 있다. 이 구간 내에서는 벌금을 내는 사람의 수와 총 벌금, 탄 사람 수 등이 모든 시각에 대해 똑같다. 그래서 좌표 압축을 하고 시작할 수 있다. 좌표 압축을 하고 나면, 가능한 모든 구간에 대해 해주면 되는데, 이때 가능한 모든 구간은 (1) 좌표압축된 점 중 하나에서 시작해 $X$의 시간 동안 이어지거나 (2) 좌표압축도니 점..
어제랑 비슷하게 3인 팀 5시간 셋을 3시간 (2분) 동안 돌았다. 대회 당시 11솔이 최대였고, 나는 10솔로 4등을 했다. (페널티 1143) 한 문제를 못 풀었는데 남은 문제도 크게 어렵진 않아서, 올솔을 못한 게 조금 아쉽다. A (6분) 가능한 게임 진행 방법이 $2^{21}$가지에 못 미친다는 것을 알 수 있다. 모든 경우에 대해서 가능한지 시도해 보면 된다. 이외에는 크게 언급할 점이 없다. C (24분) B에서 맞왜틀을 좀 당하다가 바로 C로 갔다. 풀이는 단순히 앞에서부터 가질 수 있는 커피 수를 계속 관리하면 쉽다. D (28분) $(r, 1)$이 유효한 답이다. F (1시간 9분) 일단 각 팀명의 길이를 구해야 한다. 1번 팀의 팀명을 $x$로 두면 이후 팀들의 팀명을 $ax+b$꼴로..
선발고사 대비용으로 3시간짜리 셋을 돌았다. OI가 아닌 ICPC 셋을 선택한 이유는, 적당한 3시간 OI 셋을 찾을 수가 없었다. 3인 셋을 혼자 도는 거니까 대략 스코어보드 깠을 때 5등 안에 들자는 마음으로 셋을 쳤다. 대회 당시 9솔이 최대였고, 나는 11솔을 했다. J 빼고는 크게 어려운 문제가 없는 셋이었다. 각 문제에 대해 푼 순서대로 대략적인 풀이를 적어 본다. A (0:02) 문제 해석하는 게 푸는 것보다 더 오래 걸리는 문제다. 예제가 예상과 달라서 10초 정도를 허비하는 바람에 1분째에 맞출 수 있는 문제에서 시간을 날렸다. 답은 $(x \pm r, y \pm r)$의 네 꼭짓점으로 이루어진 정사각형이다. 이 외에도 다양한 답이 있겠지만, 굳이..? B (0:19) 쉬워 보여서 A 다..
BOJ 10848. 팔렘방의 다리 정말 좋은 문제. 직접 풀지 못해서 풀이를 봤는데 놀라웠다. 풀이는 이곳에 적지 않는다. 풀이를 보고 나서 든 생각... 더보기 요즘 식 정리 문제에서 많이 말린다는 생각이 든다. IOI 2022 Circuit, Goodbye BOj 2022 F도 식 정리 문제였는데 못 풀었고, 식 정리만 하면 쉬운 유형들이었다. 이 문제도 마찬가지인 것 같은데, 문제를 풀면서 복잡한 식 정리를 피해가려는 문제풀이 스타일이 지속적으로 발목을 잡는 것 같다. BOJ 10066. 팰린드롬 팰린드롬 조건이 없었다면 LCP 배열을 구하고 나서 DnC로 풀 수 있다. 그런데 팰린드롬 조건이 있다 보니 이것만으로는 안 끝나고, 구간 내에서 가장 긴 팰린드롬을 구하는 쿼리까지 처리해야 한다. 대략적..