79brue의 PS 블로그

싱가포르 NOI 2022를 돌아 364/500점을 받았다. [BOJ 27288] A. Voting Cities (0:13) 바로 몇 주 전에 동아리에서 랜덤 플래 풀기를 하다가 본 문제라서 바로 풀었다. 기본적인 아이디어는 $K$개의 정점을 시작점으로 두고 한번에 다익스트라를 하면 되는데, 다익스트라에 상태 $d$를 추가적으로 저장한다. $d$는 사용한 쿠폰 목록이다. 아직 쿠폰 가격은 모르므로 쿠폰 가격은 쿼리를 처리할 때 더하도록 하자. 이후 쿼리가 들어올 때는 $32$가지 $d$를 고르는 경우 중 가장 싼 것을 고르면 된다. #include using namespace std; typedef long long ll; struct dat{ int x, d; ll y; dat(){} dat(int x,..

COI 2022 (크로아티아) 를 돌아 네 문제 중 세 문제를 풀어 334점을 받았다. 400점을 받아야 했을 셋인 것 같은데 아쉽다. [BOJ 25447] D. Vingete (00:18) 화성 지도 세그를 알면 매우 쉽게 맞을 수 있다. 사실상 이 세그먼트 트리를 아는지 물어보는 문제기 때문에 더 이상 설명하지 않는다. #include using namespace std; typedef long long ll; struct Edge{ int s, e, l, r; Edge(){} Edge(int s, int e, int l, int r): s(s), e(e), l(l), r(r){} }; struct segTree{ int cnt[2000002], sz[2000002], sum[2000002]; voi..

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$꼴로 나타낼 ..