2022.08.04 PS 일지
2022. 8. 4. 23:59
PS 기록들
내일 국민대 알고리즘 대회라서 장장 두 달만에 키보드를 잡아보았다. 사실 그 사이에 쇼미더코드 치느라 딱 하루 한 적이 있긴 하다. 문제집 문제 링크 위상정렬 + 순서 관계 없는 것들끼리는 번호순으로. 예전에 풀어봤던 문제라 거의 5분 컷 한 것 같다. 풀이 더보기 칸 알고리즘으로 구현해야 한다. 코사라주 알고리즘(역간선 활용)으로는 아마 방법이 없을 것이다. 기존의 칸 알고리즘의 큐 부분을 우선순위 큐로 바꾸어 풀어주면 된다. #include #define rep(i,a,b) for (auto i = (a); i sync_with_stdio(0); cin >> n >> m; rep(i,1,m) { int a, b; cin >> a >> b; adj[a].push_back(b); ind[b]++; } r..
프로베니우스의 동전 문제
2022. 6. 13. 21:43
조합론 공부
무지성으로 공식만 알아서 막 때려넣다가 자꾸 실수해서 이참에 제대로 알아보자! 느낌으로 증명을 적으려 한다. $\text{Theorem. }a,b\in \mathbb N, \; \gcd(a,b)=1$일 때 $an+bm(n, m\in \mathbb N_0)$로 표현할 수 없는 최대의 정수는 $ab-a-b$이다. $\text{Claim. lemma 1}$과 $\text{lemma 2}$가 참임을 보이면 정리도 참이다. $\text{Lemma 1. }an+bm=ab-a-b$인 $(n,m)$은 존재하지 않는다. $\text{proof:}$ 더보기 표현이 가능하다고 가정하자. $ab-a-b=a(b-1)+b(-1).$ $a(b-1-k)+b(-1+\frac {ak}b)(1\le k\le b-1)$꼴로 표현 될 것이다..
공부 2
2022. 6. 6. 20:32
조합론 공부
수학적 귀납법 - 구체수학 구체수학 하노이탑 세 개의 탑에서 하노이탑 규칙에 따라 옮기는 최소 이동 횟수를 구하면 된다. 우선, 정의를 잘 하는 것이 중요하다. 필자는 명명정복이라고 한다. $T_n:=$ 규칙 하에 다른 한 기둥으로 옮기는데 필요한 최소 이동 횟수 1번 기둥에서 2번 기둥으로 위쪽 $n-1$개의 원판을 옮기고, $n$번째 원판을 3번 기둥으로 옮긴 후 2번 기둥에 있던 $n-1$개의 원판을 3번 기둥에 올린다. 그러면 총 이동 횟수 $T_n$은 $T_n\le T_{n-1}+1+T_{n-1}=2T_{n-1}+1$가 된다. 이 때, $n$번 원판을 움직이기 위해서 $n-1$개를 들어내는 작업과 $n$번 원판을 놓은 뒤 그 위에 $n-1$개를 쌓는 작업은 필수적으로 동반되므로 $T_n\ge 2..
공부 1
2022. 6. 6. 18:09
조합론 공부
구체수학 일부 합을 공략할 때 유용한 일반 전략들. 일부는 점화식으로 일반항 구하는 데에도 사용 가능. 답을 추측하고 귀납법으로 증명한다 비약이 크기 때문에(우선 공식을 추측해야 하니까) 필자는 다른 안정적인 방식으로 닫힌 형식을 구하자고 이런 방법들을 소개한다. 합을 어지럽힌다 점화식으로 일반항을 구할 때 원래 "꼬리 자르기"라고 부르던 방식을, 책에서는 "섭동법"이라는 멋진 이름으로 소개한다. 등비수열의 합을 구할 떄 쓰는 방식이기도 한데, 등차수열의 합을 구할때는 잘 안 먹힌다. 그런데, 그림 가운데의 관찰을 바탕으로 한 차원 높게 잡고 구하면 구할 수 있다. 레퍼토리를 구축한다 $\square_n=\square_{n-1}+n^2;\; \square_0=0.$ $R_n=R_{n-1}+\beta+\g..
[번역] 5910. Mountain Climbing
2022. 6. 6. 15:58
PS 문제들
백준 5910번 출처: USACO January 2012 Silver 3번 Farmer John은 그의 소가 고강도 운동을 할 때 더 높은 품질의 우유를 생산한다는 것을 발견했습니다. 따라서 그는 $N(1\le N\le 25\, 000)$마리의 소에게 산행을 시키기로 결정했습니다! 소 $i$는 산을 오르는 데 $U_i$ 시간이 걸리고 산을 오르는데 $D_i$ 시간이 걸립니다. 각 소는 이동마다 사람의 도움이 필요하지만 돈이 없어서 사용할 수 있는 인력은 FJ와 그의 사촌 Farmer Don뿐입니다. FJ는 등산을 안내할 계획이고, FD는 하산을 안내할 것입니다. 최대 한 마리의 소가 어느 시점에서든 FJ의 도움으로 등산할 수 있고, 최대 한 마리의 젖소가 어느 시점에서든 FD의 도움으로 하산할 수 있습니..
2022.06.05 PS 일지
2022. 6. 6. 06:00
PS 기록들
어떤 고수 분의 정올 필기 점수가 꽤 낮다는 정보를 보았다. 기존의 KOI 1차 풀이를 적는 블로거들이나 한컴 설명회에서 공통적으로 얘기하던 것은, 실기 문제를 돌리는 것이 곧 필기 대비이고 필기 점수는 상의 색깔 정도를 좌우할 뿐이라는 것이였다. 그런데 이번 필기를 보고 생각이 바뀌었다. 정올러들은 기본적으로 틀리면 다시 제출하고, 여러 테스트를 거칠 기회를 가진 채로 연습한다. 그래서 실수 한 번에 나락을 가는 수학 문제들에 취약할 것이라고 생각한다. 결론적으로, 필기에도 시간 투자를 꾸준히 해야 한다는 것이 내 생각이다. 조합, 대수 파트 공부를 다시 해야겠다.
2022.06.04 PS 일지
2022. 6. 5. 01:16
PS 기록들
글을 쓰는 시점은 6월 5일 오전 1시이다. solved.ac 시즌 2가 곧 오전 6시에 시작한다. 첫 시즌 공지 때에는 목표를 2주 정도 동안 Diamond 3로 잡았다. 그런데, 정올을 망친 뒤 슬럼프를 잠깐 가지고 해서 좀 더뎌졌다. 그래서 Diamond 4로 목표를 낮췄는데, 더 우선순위인 일이 생겨 티어를 높이는 것을 중단하였다. 그래서 아쉽게 5시간 남긴 상황에서 D4 - 32로, D4 달성은 무리라 판단하고 이만 자려고 한다. 한 2주 정도 더 레이팅 올리기에 여념을 쏟지 못할 것 같다. 아무튼 시즌 2 기대된다. +) PS 일지도 한동안 OI 문제 풀이에 쏟느라 안 하고 있었는데, 이제는 좀 적을지도? +) 저번에 Bitaro's Party에 알 수 없는 이유로 cin/cout을 억까 당한..
[IZho 2012 Day 2] Monkey and Apple-trees(원숭이와 사과 나무)
2022. 6. 4. 01:20
PS 문제들
지문 링크 / 문제 링크 더보기 이거 풀면서 lazy propagation를 짜는 방식도 바꿨다. 속도가 2배가량 향상되고, 훨씬 직관적으로 변했다. 풀이 더보기 dynamic segment tree + lazy propagation. #include using namespace std; using ii = pair; using ll = long long; #define rep(i,a,b) for (auto i = (a); i v = m-s+1; r->v = e-m; l->z = r->z = 1; z = 0; } } void update(int a, int b) { if (a update(a,b); v = (l?l->v:0) + (r?r->v:0); } int query(int a, int b) { if..
[번역] 24618. Robot Instructions
2022. 6. 1. 20:44
PS 문제들
백준 24618번 출처: USACO February Silver 2번 문제 Bessie는 선물로 받은 로봇의 작동법을 배우다 로봇을 $(0,0)$에서 $(x_g,y_g)$로 이동시키 고 싶어졌다. Bessie는 '$i$번째 로봇을 $(x_i,y_i)$만큼 이동' 형식으로 구성된 명령 목록을 가 지고 있다. Bessie를 도와 $K=1\cdots N$에 대해, $K$개의 명령을 선택해 $(x_g,y_g)$로 이동시키는 방법 의 수를 구하라. 조건 $1 ≤ N ≤ 40$
[번역] 21617. Redistributing Gifts
2022. 6. 1. 20:38
PS 문제들
백준 24617번 출처: USACO February Silver 1번 문제 Farmer John은 $N$마리의 소들에게 각각 선물을 했다. 각 소는 $N$개의 선물에 대해 선호 도로 순위를 매긴 목록이 있다. 하지만 귀찮은 FJ는 그냥 각 소 $i$에게 선물 $i$를 주었다. 소들은 선물을 재분배하려 한다. 단, FJ가 준 선물보다 선호하지 않는 선물을 배정하는 일은 없게 분배하려 한다. 각 소가 받을 가능성이 있는 선물 중 가장 선호하는 선물을 구하라. 조건 $1 ≤ N ≤ 500$
[COCI 12/13 #1] SNAGA(숫자의 힘)
2022. 6. 1. 00:17
PS 문제들
문제 링크 플4치고 쉬운? 문제 풀이 더보기 2 3→2 4→3→2 5→2 6→4→3→2 7→2 8→3→2 9→2 10→3→2 주어진 수를 나누지 않는 최솟값 → 어떤 수보다 미만의 모든 수가 주어진 수를 나누게 하는 최솟값 따라서 $$|\{k|(2\nmid k)\}|\times (strength(2)+1)\\+\\ |\{k|(2\mid k)\wedge(3\nmid k)\}|\times (strength(3)+1)\\+\\ |\{k|(2\mid k)\wedge (3\mid k)\wedge (4\nmid k)\}|\times (strength(4)+1)\\+\\ \vdots$$ 를 구해주면 된다. $\mathrm{lcm}$ 단위로 커지기 때문에, 전처리할 $strength(k)$의 종류가 그리 많지 않다는 ..
코드 최적화
2022. 5. 26. 19:14
기타
알고리즘 트레이닝 초록책 2판을 오늘 받아보았다. 새롭게 추가된 내용이 곳곳에 있을 것이기 때문에 앞에서부터 살펴보았다. 역시나 따로 언급되지 않은 '3.3 코드 최적화'라는 목차가 생겼다. 코드 최적화는 고인물들이 아니더라도 통용되고 잘 알려진 기법이다. 하지만, 그 최적화를 깊이있게 이해하는 사람은 드물고, 그냥 입에서 입으로 전해지는 정도인 것 같다. 따라서 최적화의 중요한 부분들을 보충해주는 것이 마음에 들었다. 덕분에 갖고 있던 의문점들도 많이 해결되었다. 컴파일러 출력 컴파일러 최적화 /2, %2 등을 비트연산으로 대체하는 코드들을 보면서 안 예쁘다고 느껴왔었다. 그래서 세그트리 기본문제에다가 비트 연산을 사용한 경우와 그렇지 않은 경우를 비교해 본 바 있다. 하지만 유의미한 속도 차이가 없어..
[KOI 2010 본선] 체인점
2022. 5. 25. 20:13
PS 문제들
문제 링크 이 문제를 풀기 전에 BOI의 굉장한 학생을 먼저 풀어보시는 것을 추천드립니다. 풀이 더보기 다익스트라로 $A$로부터의 거리, $B$로부터의 거리, $C$로부터의 거리를 구한 뒤, $A$로부터의 거리의 오름차순으로 $B$로부터의 거리를 좌표압축한 인덱스에 $C$로부터의 거리를 업데이트해주면 된다. #include using namespace std; using ii = pair; using ll = long long; void o_o(){ cerr c >> m; rep(i,1,m) { int x, y, z; cin >> x >> y >> z; adj[x].emplace_back(y,z); adj[y].emplace_back(x,z); } vector v(n); vector bs; ll da[N..
[JOISC 2018 Day 3] Bitaro's Party
2022. 5. 25. 18:13
PS 문제들
문제 링크 usaco.guide에서 sqrt decomposition 예제로 제일 쉬운거로 추천되어 있었는데, 그걸 왜 곧이곧대로 믿었을까요... 풀 때 사진 참고하세요. 문제 번역 \(1\)부터 \(N\)까지 높이에 대한 내림차순으로 번호가 매겨진 \(N\)개의 마을들이 있습니다.(같은 높이의 마을은 없습니다.) \(M\)개의 운하는 서로 다른 마을을 단방향으로 연결합니다. \(i\)번째 운하(\(1\le i\le M\))은 높은 \(S_i\)에서 낮은 \(E_i\)로 흐릅니다. 운하는 거꾸로 거슬러 올라갈 수 없습니다. 비버 Bitaro의 \(N\)명의 친구들은 \(N\)개의 마을에 살고 있습니다. Bitaro는 \(Q\)번의 파티를 열며, 친구들을 초대할 것입니다. \(j\)번째 파티에는 \(Y_j..
[Balkan OI 2011 Day 2] trapezoid(사다리꼴)
2022. 5. 23. 21:38
PS 문제들
문제 링크 꾸준히 다이아를 풀고 있어서 기쁘다. Subtask: $N≤5\,000$ (40점) 더보기 단순히 $O(n^2)$ LIS를 돌리면 된다. #include using namespace std; using ii = pair; using ll = long long; void o_o(){ cerr > t[i].se.se; } sort(t+1,t+n+1); rep(i,1,n) { lis[i] = 1, cnt[i] = 1; rep(j,1,n-1) { if (t[j].se.fi < t[i].fi.fi and t[j].se.se < t[i].fi.se) { if (lis[i] < lis[j]+1) { lis[i] = lis[j]+1; cnt[i] = cnt[j]; } else if (lis[i] == lis..
[IOI 2005 Day 1] Garden(정원)
2022. 5. 22. 18:44
PS 문제들
문제 링크 예전 IOI라서 서브태스크가 없다. 플1... 까지는 아닌 것 같다. 풀이 더보기 겹치지 않는 두 직사각형을 선택한다는 조건을 잘 고민해보면, 수직선 하나를 두고 양쪽에서 선택한다는 의미가 된다. 그래서 아래의 색칠된 직사각형이 좌상단 영역에서 둘레가 최소가 되는 조건 만족 직사각형이라면, 저기 여러가지 나머지 직사각형들 중 최소가 되는 것과 함께 고려해주면 된다는 것을 알 수 있다. 따라서, $a(i,j):=(i,j)$를 우하단 점으로 하는 직사각형들 중 최소, $b(i,j)=i\le i',\, j\le j'$일 때, $(i',j')$을 좌상단 점으로 하는 직사각형들 중 최소로 잡고 $\min$ 2D 누적합을 진행해주면 된다. #include using namespace std; using ..
[KOI 2018 본선] 조화로운 행렬
2022. 5. 21. 22:59
PS 문제들
문제 링크 Subtask: $M = 2, 3 ≤ N ≤ 10\,000$ (14점) 더보기 어차피 부분행렬 속 각 열 속의 등수가 전부 같은 것이 조건이므로, 행렬의 각 열의 순서는 바뀌어도 상관이 없다. 따라서 각 열을 첫번째 행의 크기 순서대로 정렬하는 것이 가능한데, 이러면 LIS 문제로 환원되어 쉽게 풀 수 있다. $O(n^2)$으로도 가능한데, $O(n\log n)$으로 풀어 Subtask #3와 함께 긁었다. Subtask: $M = 3, 3 ≤ N ≤ 10\,000$ (9점) 더보기 $O(n\log n)$의 LIS는 적용할 수 없다. 따라서 $O(n^2)$ LIS를 사용하여 풀 수 있다. 코드 Subtask: $M = 2, 3 ≤ N ≤ 2\cdot 10^5$ (15점) 더보기 세그트리를 이용..
[JOISC 2019 Day 1] Examination(시험)
2022. 5. 17. 20:15
PS 문제들
문제 링크 BBST를 사용하는 개날먹 JOISC 문제 다음으로 푼 두 번째 JOISC 문제다. 문제에 풀 때 사용할 수 있는 자료구조 테크닉(문제 특성에 비해 약간 오버킬)을 배울 수 있어 좋았다. 또한, 풀이만 6개를 확인했는데... 진짜 이런 고난이도에 조건이 적은 문제는 여러 방법으로 접근할 수 있구나... 싶었다. Subtask: $N ≤ 3\ 000, Q ≤ 3\ 000$ (2점) 더보기 Naive하게 짜면 된다. 2점이라 짜다고 생각했는데 풀고 나니 걸맞는 점수다 ㅋㅋ 코드 Subtask: 점수 $ ≤ 10^5, Z_j =0$ (20점) 더보기 난이도가 확 뛴다. 우선, 각 점수 쌍들을 좌표로서 해석하면 시각화가 되므로 풀이에 접근하기 좋다. 시각화 이후에 간단한 관찰들을 바탕으로 떠오르는 자..
[KOI 2021 1차 중등부] 두 개의 팀
2022. 5. 16. 02:25
PS 문제들
문제 링크 재밌는 트리 DP 문제였다. 편의상 각 사원 $i$의 실력을 $V_i$, 부모를 $P_i$라고 하자. Subtask: $V_i > 0$ (17점) 더보기 그냥 최대한 많이 포함하면 이득이다. 그런데, 한 팀의 팀장을 전체 트리의 루트로 잡아버리면 다른 팀이 만들어질 수 없다. 또한, 루트의 $k$대 독자 후손 노드도 잡아버리면 다른 팀이 만들어질 수 없다. 따라서 1번 노드에서부터 DFS를 돌리다가 처음으로 자식 노드가 2개 이상이 된다면 가장 큰 2개만 골라주면 된다. 필자의 코드이다. Subtask: $N\le 5\ 000,\ P_i=i-1$ (12점) 더보기 직선형 그래프에서 문제를 풀면 된다. Kadane 알고리즘과 꽤 비슷하다. 각 노드 $i$마다 $\sum_{i\le k\le j}V..
KOI 고등부 Checklist
2022. 5. 16. 01:23
기타
PS 관련 이모저모 및 상반기 목표
2022. 5. 15. 23:59
기타
5월 중순인데 이제..? 너무 벌레다. 일단, 올해 달성한 것은 USACO Gold, Codeforces Expert이고, 올해 놓친 것은 Google Code Jam 2R 진출, KOI 2차 진출이다. Google Code Jam이야 얼마든 있는 기회인거고... KOI를 2년째 예선 무상으로 지내는 것이 문제다. KOI 예선 무상은 정말 쓰라리고, 생각할수록 침울하다. 당연히 올해는 통과라고 자신했는데, 자신이 무상할 정도로 미친듯이 말아먹었다. 작년에 친 KOI 1차보다 더 조졌다. 하지만, 내가 이걸 계기로 개빡쳐서 PS를 놓을 수 있을까? 답은 '아니오'다. 어차피 재밌어서 하는건데 빡종한다고 다시 안 켤 리가 없다는 것이다. 그런 만큼, KOI 1차에서 내가 저지른 실수들, 잘못된 전략들, 새로..
2022.05.13 PS 일지
2022. 5. 14. 06:00
PS 기록들
냐 공통 부분 수열 확장 문제 링크 서브태스크 구성도 좋고, 재미있게 풀었다. 풀이 및 코드 Subtask #1: $|W|=1$(14점) 더보기 자명하다. 왼쪽 확장 경우, 오른쪽 확장 경우로 나눠서 각각 쌍이 존재하는지 확인하면 된다. 하지만 Subtask #2도 충분히 쉬우므로 한번에 긁었다. Subtask #2: $\sum |X|, \sum |Y| \le 300$(17점) 더보기 $W$의 모든 위치에 대해서 문자 $c$를 끼워 넣은 경우에도 여전히 $|X|$와 $|Y|$의 부분 수열이 되는가를 판단하면 된다. 그러면 $\mathcal O(|W|\times |C|\times (|X|+|Y|+|W|))$의 시간이 걸린다. 따라서 대충 $26\times 300^2\approx 2\cdot 10^6$번의 ..
2022.05.12 PS 일지
2022. 5. 13. 06:00
PS 기록들
냐 K번째 수 문제 링크 냐 풀이 더보기 사실 루트질 연습하려고 담아둔 문제인데, 그냥 세그트리로 풀었다. 이게 머지 소트 트리 맞나? 아무튼 각 노드가 구간을 커버하는 배열의 정렬된 상태를 담는데... 이렇게 하면 쿼리를 $\mathcal O(\log n)$개의 구간에 대해 각각 $\mathcal O(\log n)$의 이진 탐색을 진행하여서 총 $\mathcal O(\log^2 n)$에 응답할 수 있게 된다. ヘビの JOI 君 문제 링크 풀이 쓰기 좀 귀찮네... 생각을 풀어서 쓰려니 귀찮다. 참고로 이 문제 기여에 나는 #Case_work를 넣었다. 깔끔하게 분류 안 하면 자꾸 꼬이는 듯. 풀이 더보기 물론 다익스트라다. 뭐 다른게 나올 일도 없지 않은가... 그 상태에서 뭘 어떻게 해야되냐가 문제인..
2022.05.11 PS 일지
2022. 5. 12. 06:00
PS 기록들
오늘 티어 많이 올린듯 후후 JOI 국가의 행사 문제 링크 3가지 풀이가 존재한다고 한다. 참고 풀이 더보기 멀티소스 다익스트라로 전처리를 해준다. 각 노드 $v$에 대해 구한 최단거리를 $\text{value}[v]$라고 하자. 문제가 $\displaystyle \min _{\text{v}\in \text{경로}} \text{value}[v]$ 쿼리를 푸는 문제로 단순화된다. $\text{value}[v]$의 크기에 따른 크루스칼 변형을 떠올릴 수 있다. 그렇게 구성되는 스패닝 트리 위의 간선을 타는 경로가 최적이다. 따라서 구성된 스패닝 트리로 sparse table을 구성한다. 쿼리를 sparse table로 처리한다. 코드 더보기 구현이 워낙 길어져서, 모듈화시켜서 풀었다. 덕분에 디버깅 없이 1..