본문 바로가기

알고리즘/코드포스44

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.
codeforces #580 div2 D - Shortest Cycle (무방향그래프 사이클, 비둘기집) https://codeforces.com/contest/1206/problem/D undirected graph이고, 최대 1e5개의 정점에 대해 만들어지는 사이클 크기의 최소값을 구하는 문제이다. 오픈카톡에 따르면 무방향그래프에서 사이클을 모두 구하는 것에 대한 알고리즘은 매우 어렵다. ( 불가능하지 않냐고 물어보는 사람도 있었다. ) 하지만 지금 문제에선 사이클 크기의 최소값을 구하는 것이므로 알고리즘을 짤 수 있다. 1) 사이클 크기의 최소값 구하기 서로 연결돼 있는 i,j에 대해, 그 간선을 끊었을 때 i~j의 경로 길이 + 1(자기자신)이 사이클 크기이다. 이를 모든 간선에 대해 적용하며 mn값을 갱신해 나가면 된다. 즉, adj[i][j]=adj[j][i]=0 -> mn = min( dist[.. 2019. 11. 13.
codeforces #580 div2 C - Almost Eqaul (발상) https://codeforces.com/contest/1206/problem/C 1 ~ 2*n 까지의 숫자를 나열하는데 연속된 n개의 부분합이 모두 같도록 나열하는 문제다. n==3) x y z x+1 y-1 z+1 n==5) x y z w d x+1 y-1 z+1 w-1 d+1 ... 위와 같은 패턴이면 된다. 위 패턴만 만족시키면 문제 조건을 만족하게 된다. 나는 추가로 구간의 합이 모두 같음도 생각해야 되는 줄 알아서 삽질을 좀 했다. #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; if (n % 2) { cout 2019. 11. 13.
Educational round #75 D - Salary Changing ( 이분탐색 ) https://codeforces.com/contest/1251/problem/D 보자마자 이분탐색이나 dp겠구나 싶어서 이분탐색으로 접근했다. 하지만 시간이 부족해서 10분정도 오버해서 풀었다. 설명) 사람의 수 n과 가지고 있는 돈 s가 주어지고 n명의 사람에 대해 받을 수 있는 돈의 범위 [l,r]이 주어진다. 이 때 사람들에게 나누어주는 돈의 중간값의 최대를 구하는 문제이다. l을 기준으로 사람들을 오름차순 정렬한다면 l, l, .... l, m, max(m,l), max(m, l) ... max(m,l) 인 경우가 최적이다. m값을 기준으로 오른쪽에 위치할 수 있는 사람은 r의 값이 m이상이어야 한다. 중간값 우측의 사람 수가 n/2미만이라면 그 값을 중간값으로 사용할 수 없다. 이 부분이 생각.. 2019. 11. 9.

티스토리툴바