전체 글
-
Codeforces Round 817 (Div. 4)코드포스 2023. 11. 13. 15:42
Dashboard - Codeforces Round 817 (Div. 4) - Codeforces codeforces.com G 홀수번째 index의 원소들을 모두 xor한 값을 a, 짝수번째 index의 원소들을 모두 xor한 값을 b라고 하자. (모든 원소를 xor한 결과가 0) iff (a=b). 따라서 모든 원소를 xor한 결과가 0이 되게 답이 되는 배열 A를 구성하자. case1 index of array A 1 2 ... N-2 N-1 N val 0 1 ... N-3 MSB^acc MSB MSB = (1
-
Codeforces Round 827 (Div. 4)코드포스 2023. 11. 13. 14:15
Dashboard - Codeforces Round 827 (Div. 4) - Codeforces codeforces.com E 배열 a의 누적합 배열 b, prefix max array c를 생각하자 bi = a1 + a2 + ... + ai ci = max(a1, a2, ... , ai) 다리길이가 ci 이상이라면 적어도 높이 bi만큼은 올라 갈 수 있다. 하지만 다리 길이가 ci 미만이면 높이 bi만큼 올라가지 못한다. 따라서 다리길이가 k이면 올라갈 수 있는 최대 높이를 구하려면 k이하인 cj 중 가장 오른쪽에 있는 cj의 index인 j를 찾으면 된다. 답은 bj F 문자열 s와 t를 각각 재배열하여 s < t 를 만족하도록 할 수 있는지를 묻고 있다. 그리디하게 s는 오름차순으로, t는 내림차..
-
Codeforces Round 849 (Div. 4)코드포스 2023. 11. 11. 12:37
Dashboard - Codeforces Round 849 (Div. 4) - Codeforces codeforces.com D 배열 a[0...N-1] 을 왼쪽과 오른쪽 두 개의 subsequence로 나누었을 때, 나눌 수 있는 모든 경우에 대해, 왼쪽/오른쪽 subsequence에 포함된 알파벳의 개수를 세는 방법은 다음과 같다. 배열 a[0...N-1]에 포함된 알파벳의 개수를 모두 센다. -> 오른쪽 subsequence에 포함된 알파벳. 이제 왼쪽 subsequence의 영역을 하나씩 넓혀간다. E 편의상 0을 positive integer, -0을 negative integer 이라고 하자. 그러면, 모든 정수(0, -0 포함) negative 이거나 positive 이다. 이때 임의의 두 ..
-
Codeforces Round 835 (Div. 4)코드포스 2023. 11. 11. 12:27
Dashboard - Codeforces Round 835 (Div. 4) - Codeforces codeforces.com D 함수값이 일정한 부분은 valley 판정에 중요한 부분이 아니다. 중요한 건 양 끝 점이 다음 조건을 만족하는지 여부이다. 따라서 배열 a를 입력받을 때 함수값의 변화가 있는 부분만 받아서 문제를 해결하면 편하다. E 경우의 수를 다루는 문제는 답이 (중간 과정이 모두 int라도) long long일 수 있다. G a에서 출발하여 인접한 노드로 움직일 때 각 노드에서의 x의 값은 유일하게 결정된다(∵ xor의 항등원이 0). 따라서 각 노드에서의 x 값은 a와 그 노드의 단순 경로의 weight 들로 계산할 수 있다. 먼저 a에서 b로 teleport를 사용하지 않고 이동하는 ..
-
dfs를 이용한 완탐시, 방문 해제 모두 하고 return true실수모음 2023. 10. 24. 18:05
9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net 틀린 코드(42번째 줄에서 바로 return true 하면 안됨) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 7..