랜덤디펜스 4일차

https://master.d66dlzauezpcp.amplifyapp.com/pentagon03랜덤디펜스를 더 돌렸다. 요번에는 어려운 문제들이 대거 등장했다.  ---8160Trains플2PASSED,  UPSOLVED 거의 보자 말자 해싱 풀이가 나왔는데, 돌발적인 다른 이슈랑 Hasher struct를 어디서 가져와서 쓰려다가 말려서 실패했다. Rolling Hash를 구현했는데 WA를 받길래 포기하고 Dot Product를 쓴 koosaga님 구현을 가져왔다.RabinKarp(Polynomial Hash)는 이제 문자열을 Shift한다던지, reverse한다던지, 다항식 자체의 성질을 사용하는게 아니라단순히 Array를 저장하고 각 위치를 swap하는 정도의 단순한 연산만 있는 경우 Dot Pr..

2024.05.29

랜덤디펜스 1~3일차

https://master.d66dlzauezpcp.amplifyapp.com/pentagon031~3일차 푼 문제 정리를 해볼까 한다. 티어는 푼 시점 기준이다. 볼드체 해놓은 문제는 어려웠던거나 추하는것.1일차12581Your Rank is Pure (Small)골546분 대망의 첫 문제고 골드가 나와서 당황했다.dp로 잘 비빌 수 있을거 같지만 n이 작아서 비트마스크로 모든 가능한 경우를 다 해보는 쪽으로 방향을 선회했다.Off-by-One error의 심각성을 확연히 알 수 있었던 문제.구현하면서도 계속 헷갈려서 46분을 허비했다. 비트마스크만 나오면 요상한? 최적화를 해서 등수를 높이려는 욕심이 있는데 여기서 이걸 확실히 느꼈다. --- 23884알고리즘 수업 - 선택 정렬 4골414분 다음 문..

2024.05.27

USACO US Open 2009 Gold 3 - Tower of Hay

USACO US Open 2009 Gold 3 - Tower of HayBOJ 6116 케이크1st StepFirst, we can consider a greedy approach.By the following perspective: "lower the last floor, better it is"So we greedily choose the lowest last floor possible. (e.g. the last floor consists of only one bale)ex) 9 1 2 4 7 => 9 / 1 2 4 / 7 However we can find out this is wrong.Consider "3 3 1 2".choosing only '2' at the last eventually m..

2024.02.23

백준 17399 트리의 외심 - 정당성 증명

https://acmicpc.net/problem/17399트리 위 노드 a,b,c의 외심을 찾는 문제.외심은 정의는 다음과 같다.1. 동일성 -> dist(a,b) = dist(b,c) = dist(c,a) 2. 최소성 a와 b의 가장 가까운 중점을 M이라 해보자. M에서 a와 b쪽이 아닌 다른 방향 (부모 혹은 자식)으로 간 것들도 모두 a와 b의 중점이 될 것이다. 거리를 d라 하자. dist(M,c) = d라면 정답은 그대로 M이된다. (다른 방향으로 옮기면 d가 증가한다.) dist(M,c) != d라면 M을 적당히 옮겨서 c와의 거리를 맞춰야 한다. 적당히 옮겨서 외심 M이 존재한다고 가정하자. 놀랍게도 이때의 M은 (a와 c의 중점) 혹은 (b와 c의 중점) 중 하나다. 만약 M이 (a,b)..

2024.02.11

[BOJ 17371] 이사 | 증명

BOJ 17317 이사의 증명 문제: 점 $P_1$, $P_2$, ... $P_N$이 주어질 때 $f(X)$를 점 $X$에 대해 $P_i$중 가장 먼 점과 가장 가까운 점의 거리의 합으로 정의하자. $min(f(X))$를 구하시오. Claim) $min(f(P_i)) = min(f(X))$ = $X$를 $P_i$ 중 하나로 정해도 그 최솟값은 전체 최솟값과 같다. Proof) $f(P_{opt}) = min(f(P_i))$ $f(X_{opt}) = min(f(X))$ $X_{opt}$에 대해 가장 가까운 점 $P_i$와 가장 먼 점 $P_j$. 삼각부등식에 의해 $\overline{X_{opt} P_i} + \overline{X_{opt} P_j} \geq \overline{P_i P_j}$ 증명은 $X..

2023.01.07

Full Diamond

상위 100개 문제를 다이아 이상의 문제로 채웠다! 공부하고 연습한 기록이 이만큼 쌓여서 뿌듯하다. 이제는 사고력을 키워보자. 스스로 사고해서 문제를 풀어내는 것이 재밌어지는 그날까지 연습!

2021.06.11

5월 25일 #금광, 전개도

보호되어 있는 글입니다.

2021.05.25

5월 22일 #JOI 깃발

보호되어 있는 글입니다.

2021.05.22

Codeforces Round #704 Div.2

이정도로 망친건 꽤나 오랜만이다.애드혹, Case-Work 연습이 부족함을 절실히 느낀 라운드A 잔실수와 C 뇌절이 결정적인 악재로 작용했다.D,E를 봤을 때는 이미 시간이 30분밖에 안 남은 시점이었다.C에서 D,E로 빨리 넘어가면 라운드를 살릴 가능성이 더 높아졌을 거라 판단된다.A. x in {a,b,c}에 대해 min( (t+x-1)/x*x )를 구하여 출력하면 된다. 함수를 만들었는데 함수 인자를 int로 하는 실수를 저질렀다. 교훈: 간단한 함수는 lambda + auto 타입 인자를 사용하자. define도 좋은듯B. 쉬운 constructive.  뒤에서부터 큰 수 기준으로 배열을 자르면 된다.C. 파라메트릭, dp 뇌절로 쉬운 애드혹을 1시간 20분 가량 붙들었다. 펑파라메트릭이 성립할 ..

2021.02.23

Codeforces Round #703 Div.2

codeforces.com/contest/1486 총평: 전체적으로 문제 셋이 재밌었고 선방했다. 정확히 1달만에 즉흥적으로 친 코포라 걱정 반 설렘 반이였는데 오히려 더 나은 결과를 얻었다 A -> B -> C1 -> C2 -> E 순으로 풀었다. A는 직관적으로 생각하면 쉬울 것을 너무 성급하게 찍어버렸다. i -> i+1 단방향만 가능하므로 i=0->n-1까지 따라가면서 가능한지 검사하는게 중요 포인트 B는 수학. 무난히 빨리 풀었다. C1, C2는 재미있는 인터랙티브 문제이니 꼭 풀어보는 것을 추천한다. 로그를 붙이는 다양한 알고리즘에 관하여 숙고한 경험이었다. C1 구현에 오래 걸리고, C2는 자칫 못 풀 뻔 했지만 관점을 완전히 바꾸니 시간 투자 후 해결할 수 있었다. E는 다익스트라 문제인데..

2021.02.19

Solved.ac 경험치 시스템 개편

최근 Solved.ac 티어 계산 시스템이 바뀌었다. 1번 항목과 2번 항목은 푼 문제를 어려운 순으로 정렬해 상위 100개 문제를 합산하는 것으로 수정되었다. 솔브드 Slack에서 얻은 정보들이다. 첨언 하자면 푼 문제 수에 따른 값은 최대 175이며, 거의 증가하지 않는다. 675문제 푼 내가 169점이고, 9000문제 가량 푸신 구사과님이 175점인 것을 보면 된다! 기여 수에 따른 값은 최대 25이고 135문제 기여 -> 25, 8문제 기여 -> 14인 것을 보면 티어와 거의 무관한 수치다. 티어와 가장 유관한 것은 푼 문제들 중 가장 어려운 것과 클래스가 되시겠다. 다이아, 루비를 많이 풀자 의도

2021.02.08

If you are a Newbie in Competitive Programming

There was a question in Codeforces recently. Talking about "I'm such a Newbie in Codeforces.. What should I do?" This is a quite boring question since there are tons of same questions. So it got many downvotes, obviously. However, I wanted to reply him because I was once a Newbie too. My Reply If you are thinking Codeforces as a 'tutorial' site, you are in the wrong place. That's why you are get..

2021.01.21

KOI에 등장하는 DP 문제들 #2

2020.09.29 1. 부동산 투자 codeup.kr/problem.php?id=3724 정수 수열에서 연속된 1부분 또는 2부분을 골라 합을 최대화하는 문제. 수열 길이 N 0 : Left[N] = dt[N-1] else : Left[N] = N dtR[N] : N번째 수를 시작으로 하는 구간을 고를 때, 구간합의 최대 dt[N]과 똑같이 구한다. mdt[N]을 dt[1]~dt[N] 중 max로 정의하자. mdtR도 마찬가지. dt[N] 중 최대를 구한 후 모든 합최대구간 중 max( mdt[left[N]-1] , mdtR[N+1] , 0)을 구해 2번째 합최대 구간을 구한다. 구현! 놀랍게도 반례가 있었다. 합최대구간을 고르지 않는게 최대일 수도 있다. 위 증명에서 A1,A2중 적어도 하나는 X와 ..

2020.09.29

과반수 원소 알고리즘

Majority Element / Majority Vote Algorithm 주어진 리스트에서 과반수를 차지하는 원소의 존재성 판정과, 존재 시 과반수 원소를 구하는 알고리즘. A[] = { 1, 3, 1, 1, 2} 리스트 A에서 과반수 원소는 1이다. 정렬하면 슥삭 풀리는 문제이지만 O(N) 시간복잡도에 가능한 알고리즘이 존재한다. O(N) Solution 내가 소개할 것 : Pair 매칭 알고리즘. *기존 길이 $n$ 리스트 A로부터 길이 $[n/2]$ 리스트 B를 만든다. N이 짝수일 때 : 앞에서부터 차례대로 2개씩 묶는다. 각각의 pair (x,y)에 대해 x==y면 하나만 남기고, x!=y면 둘 다 제거한다. A[]={1,3,1,1,2,1} 을 예시로 들자면 (1,3) => (), (1,1)..

2020.08.20

첫 Codeforces

Codeforces Div.3에 처음으로 참여했다. https://codeforces.com/contest/1367 Dashboard - Codeforces Round #650 (Div. 3) - Codeforces codeforces.com A,B,C는 문제를 빠르게 읽는 것에 경각심을 느끼게 해주었다. D,E는 문자열 다루기에 익숙해지라는 것을 가르쳐주었다. F1,F2는, 내가 아이디어에 강하지만 애매한 구현을 더 연습해야 좋은 결과를 낼 수 있다는 조언을 주었다. 새벽에 재밌었다.

2020.06.17

강 건너기 문제

※이 글은 사람이 10명 이하일 때의 알고리즘입니다. Large 문제의 해법은 0000 원하는 상태 ==> 1111 이 된다. 탐색 알고리즘 n이 7 이하이기 때문에 사람들이 분포될 수 있는 경우의 수는 2^7 * 2(배의 위치) = 256 으로 매우 작다. 그렇기 때문에 브루트 포스 (DFS)로 충분히 해결될 수 있을 것이라 보았지만 웬걸, 83퍼에서 시간 초과가 걸리고 말았다. 다시 생각해보니 256개의 정점이 있는 것이더라.. 일반적인 DFS로 풀 경우 지수함수에 비례하는 시간이 걸리므로 시간 초과가 날 수 밖에 없다. 그럼 지금 구해야 하는 것은 가중치 그래프에서의 최단 거리이다. 그렇다면 역시 다익스트라 알고리즘을 사용하자. 아래 풀이를 이해하기 위해서는 다익스트라 알고리즘에 대한 기본적인 이해..

2020.02.02