codeforces #604 div2 D - Beatiful Sequence (수학,발상)
http://codeforces.com/contest/1265/problem/D - 댓글풀이 0,1,2,3이 각각 a,b,c,d번 나오는 숫자의 배열 a 를 만드는데 다음 조건을 만족해야 한다. 문제의 조건을 만족하기 위해선, 어떤 연속한 수도 같은 parity를 가질 수 없다. 따라서, 1. 배열의 크기가 홀수인 경우엔 cnt(even)와 cnt(odd)가 1 차이가 나야 한다. cnt(even)이 더 큰 경우 0과 2를 배열a의 홀수번 idx에 순서대로 배치하고, 1과 3을 배열 a의 짝수 idx에 순서대로 배치하면 된다. cnt(odd)가 더 큰 경우는 그 반대로 하면 된다. 2. 배열의 크기가 짝수일 경우엔 cnt(even)=cnt(odd) 1번처럼 하면 된다. 무엇을 먼저 배치할진 자유 그리고 ..
2019. 12. 7.
codeforces #578 div2 D - White Lines ( 배열구간 연산 )
https://codeforces.com/contest/1200/problem/D W,B 둘중 하나로만 이루어진 n*n배열이 주어졌을 때, 단 한번 k*k크기의 구간을 W로 바꿀 수 있다면 W로 빙고가 이루어지는 경우의 최대값을 반환하는 문제이다. row따로 column따로 생각할 건데, row만 차례로 볼 때, i번째 row에서 B가 나타난다면 첫번째 위치를 L, 마지막 위치를 R이라고 하자. 이때, R-L+1 (i,j)를 기준으로 k*k 구간을 W로 바꿀때 추가되는 빙고의 수라고 할 것이다. 일단은 row와 column 따로따로 '[r1,c1] ~ (r2+1,c2+1)에 속하는 ac[i][j]의 값을 1 증가하라' 는 의미로 다음과 같이 전처리 한다. ac[r2 + 1][c2 + 1]++; //[0,..
2019. 11. 15.
