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$, ..

이번 멘토링 셋은 JOI 2020으로, 4시간 동안 5문제를 풀어야 했습니다. 전체적인 난이도는 예상했던 것보다는 할 만했던 것 같습니다. 시간대별로 상황을 서술하겠습니다. 3주가 2주보다 먼저 올라오는 이유는... 아직 2주 문제들을 구현해보지 못했기 때문입니다. #1. Just Long Neckties (0:00 ~ 0:06) 만약 $A$와 $B$가 모두 정해진다면, 둘 다 오름차순으로 정렬한 뒤 같은 순서에 있는 것끼리 matching하는 것이 최적임을 쉽게 보일 수 있습니다. 따라서 $A$에서 가장 큰 것을 빼고 나머지끼리 matching시켜 답을 구한 뒤에, $A$의 값을 하나씩 바꿔 주면서 multiset 등을 이용해 계속 가장 큰 값을 찾아내면 됩니다. Time Complexity: $O(N..

이번 주부터 국대 멘토링 교육이 시작되었습니다. 내신 준비로 시간이 충분하지 않아 일부 문제들은 풀이만 생각하고 구현을 아직 해 보지 않았는데, 시험이 끝나는 대로 구현해 볼 예정입니다. 제가 배정받은 문제 세트는 다음과 같습니다. #1. Trous de Loop (BOJ 18368) 조건을 만족하는 가장 긴 구간을 찾는 문제이므로 투 포인터를 이용합니다. 각 구간에서 자기 내부의 길이 $d$ 구간 중 구간 합이 최대인 것을 찾아야 하는데, 이 문제는 사실 누적합을 이용하면 투 포인터를 돌리면서 구간 내의 최댓값을 빠르게 찾는 문제가 되고, 이는 덱으로 해결 가능합니다. 따라서 문제가 쉽게 풀립니다. Time Complexity: $O(N)$ #2. Highway Modernization (BOJ 183..