본문 바로가기

코드포스19

codeforces #603 div2 D - Secrete Passwords ( 이분매칭, disjoint set ) http://codeforces.com/contest/1263/problem/D editorial은 biparite graph 어쩌고로 풀던데, 나는 유파로 풀었다. 문자열이 최대 2e5개 들어온다. . i번째 문자열과 j번째 문자열이 단 한 개라도 같은 알파벳을 사용했다면 두 문자열은 equivalent다 . k번째와 i번째 문자열이 equivalent하고 k번째와 j번째 문자열이 equivalent하다면 i번째와 j번째는 equivalent다. 위 상황에서 컴포넌트의 수를 구하는 문제이다. 간선만 잘 깔아주면 된다. 하지만 n이 커서 단순히 모든 요소를 비교하는 식으로 간선을 이을 수 없다. bool s[MAX][26] = { 0 }; string 형으로 문자열을 입력받은 후, 위에 저장해 뒀다. (.. 2019. 12. 2.
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.

티스토리툴바