Fancy Fence라는 문제를 풀었다. 더보기 스택을 이용한다는 사실을 알고 있었다. 근데 생각보다 알고 있는데도 인덱스 확인하고 설계하는게 좀 까다로웠다. 컨디션이 안 좋아서 풀이는 작성 안 하고... 풀 때 끄적인 필기만 캡쳐해서 올리겠다. #include using namespace std; using ll = long long; #define rep(i,a,b) for (auto i = (a); i h[i]) sum = (sum-c[s.top()])%MOD, s.pop(); ans += (x[i-1]-(empty(s)?0:x[s.top()]))*C(h[i]+1)%MOD*w[i]%MOD; ans += sum*w[i]%MOD + C(w[i]+1)*C(h[i]+1)%MOD; ans %= MOD; c[..

대회 알림이 6개나 올라와 있길래 할 만한 게 뭐가 있을지 찾아보다가 SNUPC OC Div.2 작년 결과를 보니 대회 우승/준우승 컷이 꽤 낮아서 우승/준우승을 목표로 잡고 참가했다. 대회가 끝났는데 아직 프리즈 이후 상황이 안 나와서 2등 아니면 3등인데 높은 확률로 3등이다. 아쉬운 점은 대회에 늦게 들어온 것과 C 코드를 다 짜고 실수 몇 개 고치다가 노트북 배터리가 부족해서 카페에서 집까지 뛰어서 충전기를 가져오느라 제출이 늦어진 점이다. 또, E에서 해서는 안되는 실수를 했던 점이 아쉽다. 양방향이여서 SPFA가 아니라 dfs 한 번으로 체크하고서 다익스트라를 돌리면 되는 거였는데 착각하고 인터넷에 있는 SPFA 코드를 찾아다가 넣고서 두 번이나 틀렸다. 대회 링크 질문은 언제나 환영입니다. ..

어제 저녁에 고층 빌딩을 열어서 읽다가 잠들었다. 그래서 일어나자마자 풀고 풀이를 적었다. 글 [BOJ 1328] 고층 빌딩 요즘 학교 OJ에다가 USACO 문제들을 번역해서 하나 둘씩 올리고 있다. 어제는 해커컵 예선 A번 번역한 거에다가 TC를 추가하고 정답 코드를 재채점 돌렸다. 그런데 웬걸, 서버가 터졌다. 아침에 일어나니 다시 잘 돌아가고 있길래 재채점을 다시 돌렸다. 웬걸, 다시 터졌다. 호스팅 업체의 문제인지, OJ의 문제인지 뭔지 모르겠다. 고작 코드 2개 재채점 돌리는데 터지다니... 그래서 Mountain Climbing을 오늘 올리려고 했는데 아직도 못 올리고 있다. P2 짜리를 하나 풀었는데... 구현만 몇 시간 걸린 것 같다. 힘들다... 아무래도 깔끔하게 다시 풀어볼 필요가 있다..

오랜만에 ARC를 쳤는데, 개인 최고 퍼포먼스를 내서 기쁜 마음에 풀이를 작성한다. 유의: 궁금하신 점은 댓글로 남겨주세요! Max Mod Min 요약: multiset에서 최소원으로 최대원에 modular를 취해주는 과정을 반복한다. 만약 0이 되면 multiset에서 빠지면 된다. 이 때 연산의 횟수를 구하면 된다. 풀이: modular 취하고 나면 최대원의 값이 최소원보다도 작아지므로 새로운 최소원이 된다. 이는 덱을 이용하면 구현할 수 있다. 시간 복잡도는 modular을 취할 때 항상 크기가 절반 미만으로 감소한다는 사실을 고려하면 $O(N\log \max A)$가 된다는 것을 알 수 있다. 더보기 한국 참가자들 중에 가장 늦게 제출해서 망했다고 생각했다. 10분 정도 걸렸나? 항상 보면 나는 ..

Round 2-A는 빨리 탈주했다. 그래서 2-A는 당연히 가망이 없었다. 어제는 2-B를 봤다. 231점을 받았다. 이 점수로는 본선 진출이 불가능할 것으로 보이고, 결과를 받고 나면 낙담해서 후기와 반성을 집어치울 것 같으므로 미리 적어둔다. 역시나 이번 대회에서도 아쉬운 점은 많이 찾아볼 수 있지만, 평소보다는 그 정도가 적었다. 물론 적다고 해도 남들이 보기에는 꽤 오랜 삽질을 한 것처럼 보일 것이다. 비트문자열 두 번의 제출이 모두 0점으로 실패했다. 늦었지만 52분 32초 만에 100점. 정수 놀이 보자마자 BFS로 서브태스크를 긁어야겠다고 생각했다. BFS는 안정적으로 구현할 수 있어서 22분 31초 만에 제출해서 31점. 양방향 탐색으로 최적화를 하거나 DB를 만드려는 시도를 했지만 수포로..

멀티탭 스케줄링 문제 링크 그리디 연습 겸 풀어봤다. 풀이 더보기 전기용품을 사용하려 할 때 다음의 두 가지 선택이 있다: 이미 플러그가 꽂혀 있어서 그대로 사용한다 기존의 플러그 중 하나를 뽑고 새 플러그를 꽂아 사용한다. 2번에서 어떤 플러그를 뽑을지 선택하는 것이 관건이다. 나중에 제일 적게 등장할 플러그를 뽑을 것인가? 아니다. 가장 나중에 등장할 플러그를 뽑을 것인가? 맞는 것 같다. 이는 가장 나중에 등장하지 않는 플러그를 뽑았다고 가정했을 때, 이 보다 가장 나중에 등장하는 플러그를 뽑는 것이 항상 유리하거나 같다는 발상을 통해 확인할 수 있다. #include using namespace std; using ii = pair; using ll = long long; #define rep(i..

학교 선생님께서 전용 Online Judge를 만들어 주셨다. CSL Hust OJ 기반이다. 선생님께 부탁드려서 admin 권한을 받고 문제를 추가 중이다. 대회 기능도 테스트 해보았다. 이 OJ는 불행히도 서브태스크 문제를 못 만들고, 문제에 달린 게시판도 없다. 그러나 Special Judge는 지원한다. 결국 Codeforces 기능 정도를 지원한다고 보면 되겠다. 사실 서브태스크 문제를 만들 정도로 학생들의 수요가 높지 않아서 별 상관은 없다. 그래도 나중에 여건이 된다면 선생님께 여쭤서 사이트를 수정해 보는 것도 괜찮을 것 같다. 디자인도 좀 개선하고. 좋은 점은 CSL이 정보 교사 협회인가 뭔가여서 코드업 기초 문제들이 자동으로 수록되어 있다. 덕분에 학생들이 나름 참여하고 있다. 데이터를 ..

내일 국민대 알고리즘 대회라서 장장 두 달만에 키보드를 잡아보았다. 사실 그 사이에 쇼미더코드 치느라 딱 하루 한 적이 있긴 하다. 문제집 문제 링크 위상정렬 + 순서 관계 없는 것들끼리는 번호순으로. 예전에 풀어봤던 문제라 거의 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..