오랜만에 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..
어떤 고수 분의 정올 필기 점수가 꽤 낮다는 정보를 보았다. 기존의 KOI 1차 풀이를 적는 블로거들이나 한컴 설명회에서 공통적으로 얘기하던 것은, 실기 문제를 돌리는 것이 곧 필기 대비이고 필기 점수는 상의 색깔 정도를 좌우할 뿐이라는 것이였다. 그런데 이번 필기를 보고 생각이 바뀌었다. 정올러들은 기본적으로 틀리면 다시 제출하고, 여러 테스트를 거칠 기회를 가진 채로 연습한다. 그래서 실수 한 번에 나락을 가는 수학 문제들에 취약할 것이라고 생각한다. 결론적으로, 필기에도 시간 투자를 꾸준히 해야 한다는 것이 내 생각이다. 조합, 대수 파트 공부를 다시 해야겠다.
글을 쓰는 시점은 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을 억까 당한..
냐 공통 부분 수열 확장 문제 링크 서브태스크 구성도 좋고, 재미있게 풀었다. 풀이 및 코드 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$번의 ..