문제 링크 질문은 언제나 환영입니다. 풀이 더보기 딱히 발상이 어려운 문제라고 보기는 힘들다. 특별한 알고리즘이 있는 문제도 아니다. 그냥 열심히 풀면 풀리는 문제다. 중요한 관찰은 하나뿐이다. 동적계획법처럼 귀납적으로 무-팰린드롬을 확장시키려는 시도를 해야 한다. 이 때, 확장하는 경계로부터 2칸 정도만 고려해도 충분하다. 왜냐하면 길이가 4 이상인 팰린드롬은 이미 길이가 2 이상인 팰린드롬을 포함하고 있기 때문이다. 예를 들어, $2$와 무-팰린드롬인지 알고 있는 $432$를 이어 붙이는 상황에서는 $2432$를 확인할 필요가 없는 것이다. 왜냐하면 $43$이 애초에 팰린드롬이 아니기 때문이다. 따라서 $24$와 $243$을 확인하는 것으로 충분하다. 이 관찰을 통해서 풀이를 이끌어 낼 수 있다. 무..

오랜만에 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..

프로베니우스의 동전 문제는, $a$원의 동전과 $b$원의 동전만으로 만들 수 없는 금액의 최댓값을 구하는 문제입니다. (이때, $a$, $b$는 자연수입니다.) 공식만 알고 있었는데, 정확한 적용 범위가 헷갈려서 아예 증명을 해봅니다. 잘못된 부분이 있다면 알려주세요 :) 표기 $\mathbb N_0:=\ $음이 아닌 정수 집합 $\mathbb N_+:=\ $양의 정수 집합 $\text{Theorem. }$ 서로소인 두 정수 $a,b\in \mathbb N_+$에 대해 $an+bm(n, m\in \mathbb N_0)$로 표현할 수 없는 최대의 정수는 $ab-a-b$이다. 보조정리 1과 보조정리 2가 참임을 보이면 theorem도 참이다. 보조정리 1. $an+bm=ab-a-b$인 $(n,m)$은 존재하..

구체수학과 koosaga님 블로그를 참고했습니다. 수학적 귀납법 정수 $n$에 관한 어떤 명제가 모든 $n\ge n_0$에 대해 참임을 증명하는 일반적인 방법이다. 이는 2가지 단계로 나뉜다. 기초(basis) 단계: $n_0$에 대한 증명 귀납(induction) 단계: $n_0,\cdots, n-1$에 대해 증명되었다는 가정 하에 $n>n_0$에 대해 증명 하노이탑 세 개의 탑에서 하노이탑 규칙에 따라 옮기는 최소 이동 횟수를 구하면 된다. 우선, 정의를 잘 하는 것이 중요하다. 책의 필자는 명명정복이라고 한다. $T_n:=$ 규칙 하에 다른 한 기둥으로 옮기는데 필요한 최소 이동 횟수 1번 기둥에서 2번 기둥으로 위쪽 $n-1$개의 원판을 옮기고, $n$번째 원판을 3번 기둥으로 옮긴 후 2번 기둥..

구체수학 일부 합을 공략할 때 유용한 일반 전략들. 일부는 점화식으로 일반항 구하는 데에도 사용 가능. 답을 추측하고 귀납법으로 증명한다 비약이 크기 때문에(우선 공식을 추측해야 하니까) 필자는 다른 안정적인 방식으로 닫힌 형식을 구하자고 이런 방법들을 소개한다. 합을 어지럽힌다 점화식으로 일반항을 구할 때 원래 "꼬리 자르기"라고 부르던 방식을, 책에서는 "섭동법"이라는 멋진 이름으로 소개한다. 등비수열의 합을 구할 떄 쓰는 방식이기도 한데, 등차수열의 합을 구할때는 잘 안 먹힌다. 그런데, 그림 가운데의 관찰을 바탕으로 한 차원 높게 잡고 구하면 구할 수 있다. 레퍼토리를 구축한다 $\square_n=\square_{n-1}+n^2;\; \square_0=0.$ $R_n=R_{n-1}+\beta+\g..