본문 바로가기

전체 글

간단한 nypc 후기 대기시간에 plum님 곡 틀어줘서 좋았다.간식이 맛있다.실수오차 싫다. 끝 더보기
BOJ 17187 - Necklace (P1), BOJ 22195 - Necklace 4 (D5) 둘은 메모리 제한만 다른 문제이다. 사용 알고리즘더보기kmp 풀이더보기두 문자열을 s, t라 하자. 뒤집는 경우는 s든 t든 하나만 뒤집고 똑같이 하면 되니 뒤집는 경우는 고려하지 않아도 된다.t = A+B로 쪼개고 r = B + '$' + s + '#' + A 꼴로 된 문자열을 생각해보자. 중간에 $와 #는 문자열을 구분짓기 위한 dummy이다.예를 들어, s = "yxbadctz", t = "dcbayxz"일 때 A = "dc", B = "bayxz"가 가능하다.r = "baxyz$yxbadctz#dc"가 된다. 이제 여기서 r의 fail function과 rev(r)의 fail function을 구한 다음 $와 # 사이에 있는 인덱스 i를 순회하면서 fail_r{i} + fail_rev(r){|r|.. 더보기
BOJ 18083 - Disposable Switches (D5) 지금까지 푼 CHT 문제들 중에 CHT를 가장 특이하게 쓰는 것 같다. 사용 알고리즘dp, Convex Hull Trick 풀이가장 먼저 관찰해야 하는 사실은 v가 영향을 줄 수 없다는 것이다. 왜냐하면 v>0이므로 처음부터 v가 나눠져 있었다고 생각하면 된다.결국 각 간선의 가중치는 l + c가 되고, 최단 경로의 간선 개수에 영향을 받음을 알 수 있다. 이제 다음과 같은 dp를 정의하자.dp[i][j] := 1번 정점에서 i번 정점까지 도달하는 데에 j개의 간선을 사용했을 때의 최단 경로이는 O(N(N+M))에 계산할 수 있다. (다익스트라를 이용한 O(N(N+M)logNM)은 TLE를 받는다.)이렇게 구한 dp[n][i](1 f_i(x) = i*x + dp[n][i]라는 직선을 생각해보자. 이 직.. 더보기
그냥 오렌지 보내줘 에듀코포만 안쳤어도.. 20240823 추가)치터 잡혀서 2098이 됐다... 더 짜증남 더보기
제2회 청소년 IT경시대회 고등부 (알고리즘 부문) 풀이 일단 대회 자체는 3월 중순인가? 그때 있었다. 근데 왜 지금 쓰냐면 업솔빙하기 귀찮아서 미루고 있다가 여름학교 때 갑자기 생각나서 다 풀었다. 일단 본 대회 때는 은상이었다. 3개 중에 1개 풀었는데 은상인것도 재밌지만 1번과 2,3번의 난이도 격차가 커서 그럴 만도 하다. 근데 솔직히 2번 안잡고 3번 쭉 잡았으면 2개는 풀었을듯난이도는 굳이 따지자면 개인적으로 KOI 고등부보다는 쉽다. 근데 애초에 문제 스타일이 좀 달라서 직접 비교하기는 좀 힘들다. 1번 - 즐거운 회의 (KITPA 2회 고등부 1번)문제 링크 티어더보기solved.ac Gold V (20240815 기준) 알고리즘 분류더보기solved.ac : prefix_sum작성자 풀이 : graph_theory 풀이더보기친한 관계를 그래프.. 더보기
BOJ 26973 - Circular Barn (P3) 계절학교 시즌이 되기도 했고 해서 적당히 실력에 맞는 USACO 문제들을 풀어보려 한다.tag더보기solved.ac 태그 : ad_hoc, dp, game_theory, math, number_theory, primality_test, sieve작성자 풀이 태그 : (동일) 풀이더보기일단 n = 1인 게임부터 생각해보자. 여기서 중요한 사실은 소수인것도 있지만 1, 2, 3만큼 소를 뺄 수 있다는 점이다. 먼저 소가 4마리일 때 Nhoj가 이기고(4는 소수가 아님), 소가 4의 배수에서 4의 배수가 아니게 되었을 때, 4k + a(0  하지만 이 문제에서는 이러한 게임을 2턴씩 n개를 순서대로 진행한다. 그럼 각 게임은 독립적이므로 내가 이기는 게임의 경우 최대한 빨리 끝내고, 지는 게임의 경우 최대한 .. 더보기
Educational Codeforces Round 168 (Rated for Div. 2) 억까가 연이어 일어나서 결국 레이팅은 떨어진다.일단 B 문제 조건이 나중에 계속 추가되었는데 틀린 3번 중에서 없던 조건 때문에 틀린 게 2번이다. 이걸로 추가로 10분 정도 날렸으니 엄청난 패널티를 먹었다.그다음에 C는 거의 4분만에 풀었고 D도 10분만에 풀었다. 그리고 E를 봤는데 뭔가 병렬이분탐색처럼 이분탐색을 한꺼번에 처리할 수 있는 느낌이 들어서 펜윅 + 오프라인 쿼리랑 섞어서 코드를 짰다. 그렇게 냈는데 12번이나 틀렸다.분명 틀릴 코드가 아니었는데 너무 억울해서 tc를 뜯어봤는데 무슨 4만번째 쿼리에서 뜬금없이 틀리길래 뭔가 알고리즘에 오류가 있나 해서 코드를 다시 봤더니 그제서야 실수가 보였다.결론만 말하자면if(l+1 >= r)continue;이 부분을if(l+1 >= r){ .. 더보기
Codeforces Round 961 (Div.2) (코포 복귀전) B에서 말려서 멸망!오랜만에 푸니까 코포 스타일 문제가 적응이 안되네요D도 50분 줬으면 풀었을 것 같은데 좀 아쉽지만아무튼 다시 열심히 해서 오렌지 ㄱㄱ 20240724 +)블루 복귀 :( A(0:00 ~ 0:04, 0WA)문제 요약 : n x n 판에 k개의 기물을 올릴 때 기물이 올라가있는 대각선의 개수는 최소 몇 개인가? ((i,j)는 i+j번 대각선 위에 있음)풀이기물이 많은 대각선부터 순서대로 나열하면 그 크기가 n, n-1, n-1, n-2, n-2 ... , 1, 1이므로 큰 곳부터 놔주면서 k를 언제 넘는지 보면 된다.구현하다가 좀 실수해서 2분 정도 낭비.더보기#include using namespace std;#pragma GCC optimize("O3")#pragma GCC opti.. 더보기

티스토리툴바