https://www.acmicpc.net/problem/17697 17697번: Railway Trip JOI Railways is a company operating one railway. In the railway of JOI Railways, there are N stations on a straight line numbered from 1 to N. For each i (1 ≤ i ≤ N − 1), the station i and the station i + 1 are connected by a railway track. JOI Railw www.acmicpc.net $N$개의 역이 일렬로 있으며, $i$번 역의 등급은 $A_i$이다. 모든 $A_i$에 대해 $1 \le A_i \le K$가 성..
곧 있을 2023 함수컵을 대비해 2019 함수컵을 풀어 보았다. 굿바이 한별(79brue, flappybird, lisifu) 팀 연습 세션으로 5시간 동안 돌아 1068/1200점, 대회 중 2등의 성적을 기록했다. 나는 저 중 1-1, 1-2, 1-3, 2-1, 4-1을 맡았다. 1-x 문제들은 매우 쉬운 문제들이었기 때문에 사실상 2-1 푼 게 유일한 기여라고 할 수 있겠다. 4-1도 원래 무조건 풀었어야 했을 문제인데, 못 푼 게 아쉽다. 나머지 문제들 중에서는 어려운 게 많았는데 팀원들이 대부분 너무 잘 풀어줘서 고마웠다. A. HicCup (0:13) $X$에 대한 이분 탐색을 한다. 간단한 스택 문제이다. 스택을 통해 현재 상태를 오토마타 느낌으로 저장한다. 현재 상태는 H, HC, HC!..
싱가포르 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$, ..
어제랑 비슷하게 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$꼴로..