본문 바로가기

전체 글

 (147)
Educational Codeforces Round 139 Dashboard - Educational Codeforces Round 139 (Rated for Div. 2) - Codeforces codeforces.com A - Extremely Round 전처리 00:02 AC B - Notepad# 길이가 2이며 서로 겹치지 않는 동일한 substring이 존재하는지 확인하면 된다. 00:07 AC C - Hamiltonian Wall 첫 번째 열에서 3방향으로 그리디하게 탐색하여 모든 셀을 방문할 수 있는지 확인하면 된다. 00:19 WA 방문 순서가 중요한데 위 또는 아래로 이동이 불가능할 경우에만 오른쪽으로 이동해야 한다. 00:25 AC D - Lucky Chains d = y - x라고 정의하자. gcd(x + k, y + k) = gcd(x + ..
Codeforces Round #837 Dashboard - Codeforces Round #837 (Div. 2) - Codeforces codeforces.com A - Hossam and Combinatorics ans = minv == maxv ? N * (N - 1) : (2 * cnt(minv) * cnt(maxv)); 00:04 AC B - Hossam and Friends 문제 이해를 잘못하였다. 00:08 WA 다음과 같은 배열 A를 정의한 후 two pointer로 관리하면 된다. A[i] = max(i번 사람이 모르는 사람의 번호) multiset으로 풀이할 수도 있다. 00:16 AC C - Hossam and Trainees 소인수분해 00:22 AC E - Hossam and a Letter 누적 합 + two poi..
C++ iterator 사용 시 주의 사항 다음은 대회 중에 제출한 소스의 일부이다. if (it-- != t2c.begin()) { // do something } 여기서 t2c는 std::map 타입이고 it는 std::map::iterator 타입이다. 위의 조건문에서는 undefined behavior가 발생한다. 지금까지는 iterator가 invalidated 상태가 되어도 dereference만 하지 않으면 문제가 없다고 생각하였다. 대회 종료 후 코드 테스트 중 원인을 알 수 없는 segmentation fault가 발생하였다. 도저히 원인을 찾을 수 없어 gdb로 디버깅을 하다가 놀라운 사실을 발견하였다. 일부 컨테이너에서는 iterator의 증감 연산 시 iterator가 invalidated 상태가 되면 segmentation..
겨울 숲의 초대 겨울 숲의 초대 www.acmicpc.net A - 눈 치우기 시뮬레이션 00:03 AC 시뮬레이션 없이 수학적으로 답을 구할 수 있다. 답은 max(maxv, (sum + 1) / 2)이 된다. C - 별꽃의 세레나데 (Easy) 조금 어이 없게 풀었다. 그냥 아무 식이나 때려 맞춰보다가 예제가 나오길래 제출하였다. 00:06 AC 기댓값은 확률의 역수라는 사실을 알고 있다면 쉽게 공식을 구할 수 있다. B - 은나무 특수한 모양의 트리에서 lca의 깊이를 구하는 문제이다. 파란색 노드의 전체 개수는 (K + 1)^H - 1개이다. 이보다 A 또는 B가 크다면 답은 -1이 된다. A와 B가 동일하다면 답은 0이 된다. 이외의 경우 lca는 항상 흰색 노드이다. O(N) lca 알고리즘처럼 노드의 깊이를..
BOJ 26248번 - 겨울 숲의 수호자 26248번: 겨울 숲의 수호자 첫 번째 테스트 케이스의 경우, 첫 번째 야수를 $0$초부터 $1$번 공격하고 두 번째 야수를 $1$초부터 $10$번 공격하고 첫 번째 야수를 $11$초부터 $9$번 공격하면 된다. 두 번째 테스트 케이스의 경우, www.acmicpc.net 서론 기반이 되는 논문은 링크에서 찾아볼 수 있다. 논문의 pseudocode를 그대로 구현하면 WA를 받는다. 약간의 수정이 필요한데 이를 위해서는 논문의 내용을 어느 정도는 이해하고 있어야 한다. 수정된 pseudocode를 공개하면 난이도가 대폭 낮아지기에 몇 가지 팁만 언급하고자 한다. 참고로 나도 논문의 모든 내용을 완벽하게 이해한 것은 아니라서 잘못된 부분이 존재할 수 있다. assert 도배하기 코드의 온갖 부분에 ass..
ACM-ICPC World Finals 2015 H - Qanat Qanat – Kattis, Kattis A qanat is an irrigation system widely used to deliver water in hot, arid climates. The technology was originally developed by Persians over 2000 years ago. In Morocco, qanats are known as khettara and are still used today in the southern part of the count open.kattis.com 너무 어려워서 solved.ac 티어를 보니 다이아였다. 무자비한 구현을 요구하는 Window Manager도 World Finals 2015 문제이다. ICPC 대회 시간이 5시간인..
Waterloo Programming Contest 2009-10-03 C - Cantor Cantor – Kattis, Kattis Hide Cantor Georg Cantor (public domain) The ternary expansion of a number is that number written in base $3$. A number can have more than one ternary expansion. A ternary expansion is indicated with a subscript $3$. For example, $1 = 1_{3} = 0.222\ldots _ open.kattis.com 0 이상 1 이하의 실수가 주어질 때 해당 수가 cantor set에 속하는지 판단하는 문제이다. 이때 입력은 소수점 아래 6자리까지 주어진다. 우선 0과 1을 제외한 모든 입력에 ..
제9회 한양대학교 프로그래밍 경시대회 (HCPC) Open Contest - Advanced Division 제 9회 한양대학교 프로그래밍 경시대회 (HCPC) Open Contest - Advanced Division www.acmicpc.net B - 배수관 미스터리 Union-Find + offline query 00:08 AC C - 나락도 락이다 dp 00:20 AC F - 출제비 재분배 단순 구현 00:23 AC G - 트리와 수열 트리 dp로 각 간선이 사용되는 횟수를 기록한 후 정렬하면 된다. 00:34 WA 정렬 과정에서 실수가 있었다. 00:47 AC J - 선물의 재분배 + 연산만 사용하여 풀이할 수 있다. B 값이 가장 큰 부원에게 선물을 몰아준 후 적절히 재분배하면 된다. 01:19 AC 남은 문제는 5개였고 문제별 감상평은 다음과 같았다. A - 어려워 보인다. 푼 사람이 별로 없다. ..

티스토리툴바