본문 바로가기

일기

간단한 nypc 후기 대기시간에 plum님 곡 틀어줘서 좋았다.간식이 맛있다.실수오차 싫다. 끝 더보기
그냥 오렌지 보내줘 에듀코포만 안쳤어도.. 20240823 추가)치터 잡혀서 2098이 됐다... 더 짜증남 더보기
문제를 별해로 푸는 능력 가만보면 P2 이상 되는 문제를 풀었을 때 정해랑 일치한 경우가 거의 없는 것 같다. 당연한 것 같기도 하고..https://www.acmicpc.net/problem/16901https://www.acmicpc.net/problem/31232https://www.acmicpc.net/problem/28220https://www.acmicpc.net/problem/32007https://www.acmicpc.net/problem/18798지금 바로 생각나는 것만 적어봐도 이정도다. 딱히 별 의미는 없고 신기해서 글을 써봤다. 더보기
루비를 풀었다 첫 루비는 꼭 자력솔을 하고 싶어서 하루종일(정확히는 이틀) 잡았다.6모 직전에 이게 맞는 선택인지는 모르겠다..총 126번 제출했는데 대부분 별 의미 없는 제출이고 버킷 사이즈 잡았던 게 대부분이다.Traveling Saga Problem보다 더한 시간 억까를 당해서 fastio랑 비재귀 레이지를 복붙해왔는데 그래서 사실 진짜 자력솔이라 할 수 있는지는 모르겠지만 아무튼 맞았다. 풀이를 간단하게만 적자면, 쿼리를 버킷으로 쪼개서, 그 버킷 전체를 포함하는 갱신 쿼리와 포함하지 않는 갱신 쿼리를 나누고 포함하는 경우는 일단 세그로 갱신한 다음 또 홀짝성으로 xor할지 말지를 결정하고, 포함하지 않는 경우는 레이지로 하나하나 업데이트해주면 된다.위 풀이를 미친듯이 최적화하면 풀린다. 이제 시험공부랑 cp나.. 더보기
2월 PS (3) 이번 주는 글을 미리미리 안써놔서 몰아쓰는 관계로 내용이 부실할 수 있다. 또한 날짜별 분류가 큰 의미가 없는 것 같아 앞으로는 구분하지 않겠다. POI'12/13 레이저 solved.ac 티어 더보기 20240212 기준 : Platinum I (μ = P1 - 0.16, σ = 0.38) 알고리즘 분류 더보기 solved.ac : dp, coordinate_compression, prefix_sum, sweeping, geometry 작성자 풀이 : dp, coordinate_compression, prefix_sum, sweeping, geometry, segtree(lazyprop) 풀이 더보기 원점에서 쏘는 직선의 기울기를 0에서 쭉 증가시킨다고 해보자. 그러면 직선이 레이저에 맞는 기울기가 구.. 더보기
2월 PS (2) 티스토리에 서식이 있는 걸 발견했다. 개꿀 2/5 이 글에 있는 문제 위주로 풀었다. BOJ 22306 트리의 색깔과 쿼리 2 트리의 색깔과 쿼리를 온라인으로 처리하는 문제이다. solved.ac 티어 더보기 20240205 기준 : Diamond IV (μ = D4 - 0.23, σ = 0.44) 알고리즘 분류 더보기 solved.ac : smaller_to_larger, hash_set, tree_set, graph_traversal 작성자 풀이 : smaller_to_larger, tree_set, graph_traversal 풀이 더보기 말 그대로 간선을 직접 끊을 것이다. 이를 위해 인접 리스트는 std::set으로 관리한다. 간선을 끊으면 2개의 컴포넌트로 나뉘어질 것인데, 이 중 크기가 더 .. 더보기
2월 PS (1) 매주 일요일마다 푼 문제를 정리하려고 한다. 언제까지 갈 진 모르겠다. 2/1 : KOI 문제 하나가 끌려서 잡아서 풀었고, 계절학교 문제 출처 찾아다니다가 P2 1개, D3 1개를 날먹했다. KOI'23 블록 쌓기 solved.ac 티어 더보기 20240201 기준 : Platinum II (μ = P2 - 0.24, σ = 0.45) 알고리즘 분류 더보기 solved.ac : dp, prefix_sum 작성자 풀이 : dp, prefix_sum (dp최적화용) 풀이 더보기 제한을 보니 DP인데 DP 식을 세우기에 꽤 까다로워 보인다. 뭐든 간에 관찰을 해서 단순화시켜야 할 것 같다. 먼저 구간(L~R)에 대한 dp식을 세울 지 1~i에 대한 dp식을 세울 지 생각해 봤다. 현재 보고 있는 칸에 쌓을 .. 더보기
overflow https://www.acmicpc.net/problem/31286 31286번: 철도 2 $N = 6$, $U = [0, 1, 2, 3, 4]$, $V = [1, 2, 3, 4, 5]$, $W = [3, 1, 4, 1, 5]$인 경우를 생각해 보자. 그레이더는 다음 함수를 호출한다. travel([0, 1, 2, 3, 4], [1, 2, 3, 4, 5], [3, 1, 4, 1, 5]) 모든 가능한 $(x, y)$ 순서쌍에 대 www.acmicpc.net 이번 선발고사 4번 문제이다. O(N^2logN^2)까지 짜서 당시 37점을 먹었는데 그 코드에서 꽤 직관적인 관찰 하나로 필요한 mst 간선만 남기면 바로 100점이 나오는 문제였다. 풀이를 듣자마자 이걸 왜 못맞췄지 소리가 절로 나왔다. 그리고 그.. 더보기

티스토리툴바