Computer Science/Problem Solving (12) 썸네일형 리스트형 JOISC 2021/2022 Day 1. Jail 트리 형태의 감옥이 주어진다. 이후 M개의 죄수의 초기 위치인 a_i와, 목표 위치인 b_i가 주어진다. 죄수를 인접한 위치로 옮길 수 있다. 다음 두 조건을 만족하면서 M개의 죄수를 목표 위치로 옮길 수 있는지 판별하면 된다. 1. 도중에 한 방에 여러 명의 죄수가 존재해선 안 된다. 2. 한 죄수는 무조건 최단경로로만 이동해야 한다. (트리이므로 최단경로가 유일하다.) 다음과 같은 관찰이 가능하다. Claim) 만약 가능하다면, Exist i, a_i -> b_i 사이 아무것도 없고, b_i는 어떠한 a_j -> b_j 사이에도 존재하지 않음(즉 그냥 i를 먼저 밀어버리고 생각 가능) 이 강력한 Claim을 바탕으로 문제를 그냥 풀어버릴 수 있다. 죄수들을 정점으로 하는 그래프를.. 1221 Problem Solving CERC 2021 F Letters : 그냥 구현하면 된다. Petro Camp Summer 2016 Day 6 D Championships : 먼저 차수가 d 미만인 점을 제외하고, 이를 바탕으로 위상정렬하듯이 큐로 불가능한 후보들을 제거해준 후 가장 큰 연결성분을 찾으면 된다. Petro Camp Summer 2016 Day 5 I Vier : a+b = c+d = K일 때 K를 고정시키면 N개 후보군에 대해 성립하는지 판별은 O(N)에 가능. 임의의 순열은 모든 K에 대해 성립하거나, 아주 적은 개수의 K개에 대해서 성립하지 않을 것으로 추측 가능하다. 이를 바탕으로 K를 무작위로 1000번정도 정해주면 된다. CERC 2021 K Single-track railway : 세그먼트 트리에서 이분탐색.. 1114 Problem Solving IOI 2005 Practice 1 : Divisor game p가 소수라고 생각해보면, n = p인지 확인하기 위해선 p 이하의 모든 소수들에 대해 질문을 해 보아야 한다. 이러한 결과를 바탕으로 생각해보면, 그냥 체를 이용해 n 이하의 모든 소수를 구하고 그 소수들에 대해 지수를 구한다고 생각하면 풀 수 있다. (최소 증명은 자명하므로 생략함) 시간복잡도는 O(NlogN)이다. Google Code Jam 2014 Round 2 C : Don't Break The Nile Small : 그래프를 탐색한다고 생각하자. 단순 플로우 알고리즘을 돌릴 경우 TLE가 날 것이다. 다음과 같은 그리디한 전략으로 격자 그래프에서 dfs를 하자 : 왼손 법칙을 하면서 미로를 건너듯이, 왼손이 벽에 붙어있도록 방향을.. 0916 Problem Solving urd05의 추천으로 4문제 셋을 돌았습니다. 점수는 50/100/85/0입니다. JOISC 2016/2017 Day 1 : Sparklers 50점 (서브테스크 1, 2) : 기본적으로 파라메트릭 서치를 박고 시작하는건 굉장히 자명해 보인다. 자명한 관찰을 하나 할 수 있다. 현재 l~r까지를 소비했을 때, 다음 소비하는 것은 l-1 혹은 r+1이 될 것이다. 이를 바탕으로 DP를 정의하자. L[s][e], R[s][e]를 정의하자. 이는 s~e 구간의 모든 것을 소비했을 때 가능한 최소 위치, 최대 위치이다. DP 전이는 굉장히 간단하다. L[0][N-1], R[0][N-1]이 존재한다면 가능, 아니면 불가능이다. 시간복잡도는 O(N^2log(1e9/T))이다. 100점 : L번째 사람부터 R번째 사.. 0911 Problem Solving 보호되어 있는 글입니다. 0909 Problem Solving 보호되어 있는 글입니다. 0903 Problem Solving 4문제로 이루어진 셋을 돌았습니다. 결과는 100 / 42 / 0 / 100입니다. 1. JOI2020 Capital City(수도) 30점 (서브테스크 3) : 직관적인 DnC가 보인다. 현재 구간을 [s, e)라고 할 때, mid를 포함하는 답을 생각해보면 순회를 통해 O(N) 혹은 O(NlogN)에 mid를 포함하는 모든 답을 구할 수 있음을 알 수 있다. 또한 어떤 도시가 mid를 사이에 둔다면, 이 도시가 수도로써 동작하기 위해선 mid를 반드시 거쳐야 하므로 mid를 포함하는 답에 포함되게 된다. 따라서 mid가 사이에 없는 도시들로 분리할 수 있고, 이를 통해 DnC가 가능하다. 100점 : 위 방법을 트리에서 정확히 똑같이 하면 된다. 센트로이드 분할을 이용하자. (이 경우엔 한번에 여러 .. 0827 Problem Solving 4문제로 구성된 셋을 돌았습니다. JOI 17 : Long Mansion 먼저, 각 i에 대해 최종 도달 가능 범위를 L[i] ~ R[i]라 하자. 이러한 L[i], R[i]를 모두 구할 수 있다면, 쿼리를 O(1)에 처리 가능하다. 이제 이러한 L[i], R[i]를 구해보자. 10점 (서브테스크 1) : 최대한 왼쪽으로 갔다가 최대한 오른쪽으로 갔다가 ... 구간이 일정해질 때까지(더 이동이 불가능해질 때까지) 반복한다. 가지고 있는 Key의 정보는 std::set으로 관리한다. 시간복잡도는 O(N^2logN + Q)이다. 25점 (서브테스크 2) : Key의 종류가 최대 20개이다. 따라서 이를 비트마스킹하고 bitwise or SegTree를 짜고, 최대한 왼쪽으로 가는 것과 최대한 오른쪽으로 가는.. 이전 1 2 다음
