코드포스
-
Codeforces Round 871 (Div. 4)코드포스 2023. 11. 24. 01:15
Dashboard - Codeforces Round 871 (Div. 4) - Codeforces codeforces.com D 방법 1 - dp n을 쪼개서 m이 될 수 있음? i) n = m 이면 가능 ii) n != m 이면 3|n일 때 n/3 또는 2n/3로 m을 만들 수 있다면 가능 iii) 그 외에는 불가능 방법 2 - 관찰 F G 방법 1 - dp 위 캔의 모양을 아래와 같이 변형하자. 그리고 dp를 다음과 같이 정의한다. 1 2 3 4 5 6 7 8 9 10 dp[r][c] := i를 쳤을 때 넘어지는 점수의 합 dp[r][c] := i² + dp[r-1][c-1] + dp[r-1][c] - dp[r-2][c-1] ex) dp[9] = 9² + dp[5] + dp[6] - dp[3] 방법 ..
-
Codeforces Round 859 (Div. 4)코드포스 2023. 11. 23. 21:49
Dashboard - Codeforces Round 859 (Div. 4) - Codeforces codeforces.com C 010101010101로 치환되는지만 확인하면 된다. 즉, 1. 홀수번째 index가 모두 1로 치환될 수 있는지 2. 짝수번째 index가 모두 0로 치환될 수 있는지 3. 그러면서 치환 과정에 모순이 생기지 않는지 확인하면 된다. (101010 이 되는지 추가적인 확인은 불필요 !) F 많이 귀찮은 구현 문제. 유한번의 bounce 만으로 시행이 끝난다고 하자. 그러면 각 벽면 (r, c)에서 bounce는 많아야 2번이다. 그 부분은 cnt라는 map을 통해서 관리한다. 다음과 같은 알고리즘을 이용한다. 가. 현재 상태(cr, cc, dr, dc)에서 다음 벽을 튕기고 나..
-
Codeforces Round 784 (Div. 4)코드포스 2023. 11. 15. 09:40
https://codeforces.com/contest/1669 Dashboard - Codeforces Round 784 (Div. 4) - Codeforces codeforces.com D 스템프들은 'W'를 기준으로 독립적이다. 따라서 각각 스템프가 찍여있는 segment들이 유효한지 판단하면 된다. 한편, segment에서 하나의 색만 존재하지 않는 한 유효하다.(두 색이 모두 존재한다면, 그렇게 되게끔 스템프를 찍을 수 있다) RB RBB RBBB ... BR BRR BRRR ... 위 패턴은 모두 유효한 방법(물론 그 패턴의 반전 포함)이고 임의의 segment는 위 패턴의 결합을 이해할 수 있다. BBBBRRBBRBBRRRRBBB 를 예로 들어보자. BBBBRRBBRBBRRRRBBB BBBB..
-
Codeforces Round 799 (Div. 4)코드포스 2023. 11. 15. 09:15
Dashboard - Codeforces Round 799 (Div. 4) - Codeforces codeforces.com E 방법 1 - two pointer index 0 1 2 3 4 5 6 7 8 val 1 0 1 1 0 1 0 0 1 길이가 7인 1-based 배열이 주어졌다고 하자. 위 배열로부터 값이 1인 index를 저장하고 있는 배열을 구하자. [0, 2, 3, 4, 8] 이로부터 합이 2인 maximum segment를 구할 수 있다.(합이 4가 되는 segment에서 양 끝 index에서 1씩 줄이면 된다.) [0, 2, 3, 4, 8] → 구간 [0+1, 4-1] [0, 2, 3, 4, 8] → 구간 [2+1, 8-1] 방법 2 - prefix array + binary searc..
-
Codeforces Round 806 (Div. 4)코드포스 2023. 11. 14. 15:41
Dashboard - Codeforces Round 806 (Div. 4) - Codeforces codeforces.com F ai < i 를 만족하는 원소에 대하여, i < j && i < aj 인 (i, j)의 개수를 세자. 배열의 원소를 왼쪽에서 차례로 볼 때, 현재 보고 있는 원소의 index를 j라고 하자. 수식 i < j && i < aj 의 의미를 다시 해석해보면 다음과 같다. i := 이미 본 원소의 index j := 현재 보고 있는 원소의 index (i < aj 를 만족하는 i의 개수) := 지금까지 본 index 중 aj보다 작은 index G good key만을 사용하다가 bad key 만을 사용하는 것이 최적이다. 예를 들어 다음과 같이 key를 사용했다고 하자. index 1..
-
Codeforces Round 790 (Div. 4)코드포스 2023. 11. 14. 15:04
Dashboard - Codeforces Round 790 (Div. 4) - Codeforces codeforces.com H2 i = aj 인 순서쌍 (i, j)의 개수를 세면 됨 방법 1 - BIT(fenwick tree) 배열의 왼쪽부터 오른쪽으로 차례로 보자. 지금까지 본 원소(왼쪽에 있는 원소)들 중 본인보다 작거나 같은 수의 개수를 세면 된다. 이를 위해 누적합의 다음 성질을 이용한다. 편의상 index 0은 생각하지 않기로 한다. 0으로 초기화된 배열 A에 대해, B를 배열 A의 누적합이라고 하자. i.e. B[i] = A[1] + A[2] + ... + A[i] A[1] 에 1을 더하면 B의 모든 원소는 1 증가한다. 한편 A[n] 에 1을 빼면 B[n]을 포함하여 B..
-
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는 내림차..