코딩
-
CodeTON Round 1 (Div. 1 + Div. 2)코딩 2022. 3. 26. 17:45
이번에 CodeTON Round 1에서 5솔, 308등으로 레드퍼포를 띄웠습니다. 처음에는 A와 C에서 1번씩 틀려서 망했다고 생각했지만, D와 E에서 생각보다 빠르게 답을 찾아서 운 좋게 잘 볼 수 있었던 것 같습니다. 아무래도 Div.1+Div.2다 보니 퍼포가 높게 찍히기도 했네요. 아래는 풀이입니다. A. Good Pairs 일반성을 잃지 않고 $a_i\leq a_j$라 하면, 수식을 분석했을 때 $a_i\leq a_k \leq a_j$가 수식이 성립할 필요충분조건임을 쉽게 알 수 있습니다. 따라서 배열 중 최댓값과 최솟값의 인덱스를 고르면 됩니다. 더보기 (정렬해도 되는 문젠데 이렇게 풀어서 시간도 뺏기고 한 번 틀렸습니다.) #include using namespace std; typedef ..
-
백준 16238: 독수리코딩 2022. 3. 9. 14:17
https://www.acmicpc.net/problem/16238 16238번: 독수리 첫째 날 1번 칸의 왼쪽에서 날기 시작해 2번 칸의 양을 먹는다. 독수리가 먹은 양의 수는 10마리이다. 2번 칸에 있는 양을 먹었기 때문에, 1번, 2번 칸의 양의 수는 0이 된다. 첫째 날의 밤에 양의 수 www.acmicpc.net 풀이 물론 문제 조건에서는 왼쪽 또는 오른쪽에서 날기 시작할 수 있다고 했지만, 사실 관찰을 해보면 왼쪽에서만 날기 시작해도 정답에 영향을 주지 않습니다. 즉, 정해가 왼쪽과 오른쪽에서 날기 시작하는 것이 섞여있는 것이라면 그 위치들을 오름차순 정렬하여 순서대로 먹는 것도 같은 결과를 보여줍니다. 증명은 쉬우므로 생략하겠습니다. 위의 관찰을 하면 쉽게 dp로 풀 수 있습니다(기여창을..
-
백준 20106: Cave코딩 2022. 2. 23. 20:40
https://www.acmicpc.net/problem/20106 20106번: Cave While lost on the long walk from the college to the UQ Centre, you have stumbled across the entrance to a secret cave system running deep under the university. The entrance is blocked by a security system consisting of N consecutive doors, each door behind www.acmicpc.net 번역본은 https://oj.uz/problem/view/IOI13_cave를 참고하시면 됩니다. 풀이 시행이 최대 70,000번이며..
-
백준 20085: Detecting Molecules코딩 2022. 2. 22. 23:37
https://www.acmicpc.net/problem/20085 20085번: Detecting Molecules C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang) www.acmicpc.net 혹시라도 번역이 귀찮고 궁금하다면 https://oj.uz/problem/view/IOI16_molecules을 보는 것도 좋습니다. 풀이 굉장히 많은 생각을 하다 보면, 재미있는 관찰이 가능해집니다. "문제의 조건을 만족하는 해가 존재한다는 것과 정렬된 배열 w에서 연속된 값들의 합 중 문제 조건을 만족하는 값이 있다는 것은 동치이다." 문제의 처음이자 끝인 관찰이고, 저로서는 생각해내는 것이 어려웠습니다. 위의 명제를 증명해보겠습니다. 더보기..
-
백준 21761: 초직사각형코딩 2022. 1. 28. 14:58
https://www.acmicpc.net/problem/21761 21761번: 초직사각형 1차원 공간에서의 선분, 2차원 공간에서의 직사각형, 3차원 공간에서의 직육면체를 생각해 보자. 선분의 크기는 변수 $A$로, 직사각형의 크기는 두 개의 변수 $A$와 $B$로, 직육면체의 크기는 세 개 www.acmicpc.net 풀이 적당히 눈에 보이는 그리디로 풀어주면 맞습니다. $ABCD$의 값을 최대로 변화시켜주는 카드를 계속 찾아주면 됩니다. 이 방법으로 최적해를 찾을 수 있다는 것을 증명해보겠습니다. 더보기 처음에 값이 $A,\ B,\ C,\ D$라고 하겠습니다. 첫 시행에서 초직사각형의 부피를 가장 많이 증가시켜주는 카드를 일반성을 잃지 않고 $A$를 $N$만큼 증가시켜주는 카드(이제부터 $X$라고..
-
백준 1115: 순열코딩 2022. 1. 13. 14:32
https://www.acmicpc.net/problem/1115 1115번: 순열 0부터 N-1까지 모든 정수를 한 번씩 포함하고 있는 순열 A[0], A[1], ..., A[N-1]이 있다. 순열 A를 이용해서 A와 길이가 같은 자식 배열 B을 아래와 같은 방법으로 구할 수 있다. B[0] = 0 B[i] = A[B[i-1]] (1 ≤ www.acmicpc.net 풀이 순열 $A$를 $i \ \rightarrow \ A[i]$인 유향그래프처럼 생각해 봅시다. $A$에 $0\sim N-1$의 수가 모두 하나씩 들어가 있으므로 모든 노드들은 indegree와 outdegree가 각각 1이 됩니다. 따라서 이 그래프는 사이클로만 이루어지게 됩니다(증명은 귀류법으로 쉽게 할 수 있으므로 생략합니다). 이 사..
-
백준 12987: Matrix Again코딩 2021. 12. 9. 21:47
https://www.acmicpc.net/problem/12987 12987번: Matrix Again 첫 번째 줄에 N, K, M (1 ≤ N ≤ 50, 1 ≤ K ≤ 109, 1 ≤ M ≤ 104) 이 공백을 구분으로 주어집니다. 다음 N개의 줄에 걸쳐 행렬 A가 주어집니다. (-104 ≤ Aij ≤ 104, 1 ≤ i, j ≤ N) www.acmicpc.net 풀이 분할 정복을 이용하여 쉽게 풀 수 있습니다. $S_T=A+A^2+\dots+A^T$라고 하고, $S_T$를 빠르게 구해 봅시다. $S_{T/2}=A+A^2+\dots+A^{T/2}$이기 때문에, $T$가 짝수일 땐 $S_T=S_{T/2}+A^{T/2}\times S_{T/2}$로 $S_T$를 구할 수 있고, $T$가 홀수일 땐 $S_T..
-
Codeforces Round #752 (Div. 2)코딩 2021. 11. 1. 18:33
이번에 CR#752에서 314등으로 퍼플퍼포가 되었고, +110이 되어 코드포스 블루에 드디어 도달했습니다. 아무래도 운이 많이 따른 라운드인 것 같습니다. D는 그냥 수학문제였고, C는 나이브로 풀었지만 시스텟에서 다행히도 TLE가 나지 않았습니다(아니면 TLE날 데이터가 원초 없었을 지도 모르겠네요). 이대로 끝내기는 뭐하니까 이미 에디토리얼은 나왔지만 그냥 풀이를 쓰겠습니다. A. Era $a[i]-i$의 max를 찾으면 끝나는 문제입니다. 더보기 #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while(T--) { int n, a[101], m=0; cin >> ..