PS Training 1

problem-solving

안녕하세요, 저번 달에 이어 다시 Problem Solving을 주제로 글을 쓰게 되었습니다. 최근에는 이렇다 할 연습을 따로 하지 않았는데, 한국인 problem setter가 준비한 코드포스 라운드도 있었고, SCPC 등을 이유로 조금씩 테크닉을 연습한 문제 등이 있어 모아 쓰게 되었습니다. 지난번엔 코드포스의 div1C 수준 정도의 문제를 다루었지만, 이번에는 div1B~div1C 수준의 문항에 대해 다룰 예정입니다. 각 문제의 디스크립션, 풀이, 그리고 풀어볼 수 있는 링크를 정리합니다.

White Lines

Codeforces Round #578 (Div.2)의 D번 문제입니다.

https://codeforces.com/contest/1200/problem/D

한국의 PS 유저인 jwvg0425님과 djm03178님이 준비해 주신 라운드였습니다.

문제의 내용은 아래와 같습니다.

$N * N$ 격자 그리드가 있습니다. 그리드의 각 칸은 검은 색이거나 흰 색으로 미리 칠해져 있습니다. 여기서, “White Line”이라는 것을 정의합니다. White Line이란, 어떤 행 또는 열이 모두 하얀색 칸으로만 이루어진 것을 의미합니다. 이제 $K * K$ 사이즈의 지우개를 딱 한 번 그리드 내에 사용하여, $K * K$ 크기의 부분 그리드를 모두 하얀색으로 바꿀 수 있습니다. 지우개를 최적으로 사용했을 때, 가능한 White Line의 최대 개수를 구해 주세요.

제한은 $1 <= K <= N <= 2000$ 이며, 그리드의 각 칸은 검은 색은 B, 흰 색은 W로 입력됩니다.

풀이

만약 $N$이 충분히 작았다면, 모든 위치에 지우개를 실제로 적용해 보고, White Line의 개수를 세는 방법으로 쉽게 풀 수 있는 구현 문제가 됩니다. 하지만 $N$이 크기 때문에, 더 효율적인 방법을 찾아야 합니다.

우선, White Line을 관리하는 것은 쉽지 않아 보이므로, 좀 더 쉽게 White Line의 “개수”를 관리할 수 있는 형태로 설계해 봅시다. 어떤 행 하나가 White Line이 되기 위해서는, 다음의 두 가지 조건 중 하나를 만족해야 합니다. 열에 대해서도 똑같이 생각할 수 있으므로, 행에 대해서만 정리합니다.

지우개를 사용하기 전에도 White Line이다. 즉, 하얀 칸으로만 이루어져 있다.
지우개가 사용되었을 때, 행에 존재하는 모든 검은 칸이 지우개 내에 포함되어야 한다.

1번 조건을 만족하는 행은, 입력을 받은 뒤 미리 세어 두면 됩니다. 지우개를 어디에 사용하든, 1번 조건에 의해 White Line이 된 행은 항상 White Line입니다.

이제 2번 조건에 대해 생각해보기 위해, 아래와 같은 행 하나를 생각해 봅시다.

$N$ = 7일 때, 2, 4, 5, 7번 칸이 검은 색인 어떤 행입니다. 위 행을 White Line으로 만들 수 있는 지우개의 영역은 아래처럼 표현됩니다.

각각 가능한 가장 왼쪽 위, 가장 오른쪽 위, 가장 왼쪽 아래, 가장 오른쪽 아래에 놓인 지우개의 모습입니다. 색을 달리 하여 표시하였으며, 경계가 잘 보이게 하기 위해 실제보다 2픽셀 정도 어긋나게 그려두었습니다.

위 네 영역의 합집합으로 표시되는 큰 직사각형 내에 지우개가 온전히 포함된다면, 항상 이 행을 White Line으로 만들 수 있습니다. 또한, 이러한 영역을 나타내기 위해서는, 가장 왼쪽의 검은 칸과 가장 오른쪽의 검은 칸만이 중요함을 직관적으로 알 수 있습니다.

이 때 주의해야 할 점은, 지우개의 한 변의 길이보다, 가장 왼쪽 검은 칸과 가장 오른쪽의 검은 칸 사이의 간격이 더 넓다면 지우개를 어떻게 배치해도 White Line을 만들 수 없다는 점입니다. 이렇지 않은 행들에 대해서만, 위와 같은 영역이 생길 것입니다.

위 그림에서 볼 수 있듯이, 지우개가 놓일 수 있는 영역은 어떤 연속한 사각형 모양으로 표시됩니다. 좀 더 관리를 쉽게 하기 위해, 지우개의 “왼쪽 위 꼭지점”이 놓일 수 있는 영역만 생각해 봅시다.

지우개의 왼쪽 위 꼭지점이 위의 투명한 파란색 직사각형 영역 내에 존재한다면, 위 행은 White Line이 됩니다. 만약 지우개의 왼쪽 위 꼭지점이 위의 영역을 벗어난다면, 위 행은 White Line이 아니게 됩니다.

즉, 2번 조건을 만족하기 위해서는, 지우개를 놓는 위치, 더 자세히는 지우개의 왼쪽 위 꼭지점이 어떤 특정 직사각형 영역 내부에 있으면 됩니다.

모든 행과 열에 대해, 이미 White Line인 것의 개수를 따로 세어 두고, 아닌 경우엔 위와 같은 영역을 모두 얻어 두게 되면, 결론적으로 아래와 같은 문제로 변환할 수 있습니다.

그리드 내에 직사각형이 여러 개 있을 때, 하나의 점을 골라 최대한 많은 직사각형 내에 포함되게 하자.

이 문제는 어디서 많이 본 듯한 문제입니다. 이 문제를 가장 우아하게 해결하는 방법이라 생각되는 것이 있습니다. 사실 이 문제에 대한 풀이를 작성하는 이유도 아래의 방법을 소개하기 위해서입니다.

우리에게 어떤 자료구조가 있다고 생각합시다. 이 자료구조는 그리드를 관리하며, 다음과 같은 질의를 매우 빠르게 처리할 수 있습니다.

어떤 직사각형 영역 내부에 존재하는 모든 칸에 대해 +1을 적용한다

만약 이런 자료구조가 존재한다면, 먼저 설명한 문제를 그대로 풀 수 있습니다. 주어진 모든 직사각형을 질의를 이용해 업데이트한 뒤, 그리드 전체에 대해 최댓값 탐색을 한 번 하면 답을 얻을 수 있기 때문입니다. 그리고 놀랍게도, $O(1)$에 직사각형 영역 업데이트가 가능한 테크닉이 존재하며, 업데이트가 끝난 이후에는 그리드를 한 번 전체 탐색하며 최댓값을 찾기만 하면 됩니다.

우선, 우리가 다룰 그리드가 1행 $N$열 형태라고 생각해 봅시다. 즉, 질의는 그냥 구간 내에 +1 업데이트를 진행하는 연산이 되는 것입니다. 이는 세그먼트 트리 등의 유명한 자료구조로도 해결할 수 있지만, 업데이트만 필요하다면 다음과 같은 형태로도 간단하게 가능합니다.

먼저, 길이 $N$의 배열 A를 준비합니다. 배열의 모든 칸은 초기에 0으로 차 있습니다. 이제 구간 [L,R]에 +1을 적용하는 업데이트가 필요하다면, 그냥 A[L]에 +1을, A[R+1]에 -1을 더해 버립니다. 이러한 작업을 주어지는 모든 질의에 대해 마친 뒤, 배열을 누적합 배열로 바꿔 버립니다. 이렇게 하면, 실제로 구간에 대한 업데이트를 모두 적용한 것과 완전히 똑같은 상태가 됩니다. 그림으로 설명하면 아래처럼 됩니다.

먼저, 0으로 초기화된 배열을 준비합니다. 만약 여기에서, 구간 [2,5]에 +1을 업데이트하고 싶다면, A[2]에는 +1, A[5+1]에는 -1을 더합니다. 배열은 아래와 같이 변합니다.

만약 이 상태에서, 구간 [3,5]에도 +1을 업데이트하고 싶다면, A[3]에 +1, A[5+1]에 -1을 더해 줍니다.

그리고 마지막으로, 구간 [1,2]에 +1을 업데이트하고 싶다면, A[1]에 +1, A[2+1]에 -1을 더해 줍니다.

모든 업데이트가 끝났다면, 배열을 누적합 배열로 바꿔 줍니다. 다시 말해, A[i] += A[i-1] 을 i=1부터 N까지 순차적으로 모든 i에 대해 적용해 줍니다.

초기 배열에 대해, 각각 적용되었던 질의인 [2,5], [3,5], [1,2]를 직접 적용한 것과 완전히 동일한 결과임을 볼 수 있습니다.

이것이 가능한 이유는, 누적합이 계산되는 과정을 생각해보면 간단합니다. A[L]에 적용된 +1은 누적합에서는 A[L], A[L+1], … , A[N]에 모두 적용되며, A[R+1]에 적용된 -1은 누적합에서는 A[R+1], A[R+2], … , A[N]에 모두 적용되기 때문에, 결과적으로는 A[L], A[L+1], … , A[R]에만 +1을 적용하는 것과 동일해지기 때문입니다.

이것을 2차원으로 확장하는 것 또한 매우 간단합니다. (R1,C1)을 왼쪽 위 꼭지점으로, (R2,C2)를 오른쪽 아래 꼭지점으로 하는 직사각형 영역에 대한 업데이트가 필요하다면, 칸 (R1,C1)에 +1, (R1,C2+1)에 -1, (R2+1,C1)에 -1, (R2+1,C2+1)에 +1을 업데이트하면 됩니다. 어떤 칸에 대한 업데이트는, 누적합에서는 해당 칸을 왼쪽 위 꼭지점으로 하고, 아래와 오른쪽으로 무한히 확장한 영역에 대한 업데이트가 됨을 생각해 보면 자명합니다. 그림으로는 아래처럼 표현됩니다.

(R1,C1), (R1,C2+1), (R2+1,C1), (R2+1,C2+1)에 대한 순차적인 업데이트 과정에서, 누적합에서 +1이 적용되는 부분은 파란색으로, -1이 적용되는 부분은 빨간색으로, +1과 -1의 업데이트 횟수가 동일하여 결론적으로 0이 적용되는 부분은 보라색으로 그린 그림입니다. 특정 직사각형 영역에 모두 +1을 업데이트하는 작업을, 4회의 operation으로 $O(1)$에 할 수 있음을 볼 수 있습니다.

이제 원래 문제로 돌아가서, 먼저 항상 White Line인 것의 개수를 세고, 그렇지 않은 행이나 열에 대해서는 위처럼 해당 행이나 열을 White Line으로 만들 수 있는 지우개의 왼쪽 위 꼭지점의 위치를 직사각형으로 표현하여, 가장 많이 누적된 위치에 지우개를 놓으면 됩니다. 시간복잡도는 총 $O(N^2)$이 됩니다.

소스 코드

대회 중에 제출하여 정답을 받았던 코드 전문은 아래와 같습니다. 앞서 설명한 풀이를 그대로 사용한 코드입니다.

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
char b[2020][2020];
int n, k, p[2020][2020];
 
int main() {
	scanf("%d %d",&n,&k);
	int add=0;
	for(int i=1;i<=n;i++)
		scanf("%s",&b[i][1]);
	for(int i=1;i<=n;i++) {
		int l=-1, r=-1;
		for(int j=1;j<=n;j++) {
			if(b[i][j]=='B') {
				if(l<0) l=j;
				r=j;
			}
		}
		if(l<0) add++;
		else {
			if(r-l+1<=k) {
				int r1=max(1,i-k+1), r2=i;
				int c1=max(1,r-k+1), c2=l;
				p[r1][c1]++;
				p[r1][c2+1]--;
				p[r2+1][c1]--;
				p[r2+1][c2+1]++;
			}
		}
	}
	for(int j=1;j<=n;j++) {
		int l=-1, r=-1;
		for(int i=1;i<=n;i++) {
			if(b[i][j]=='B') {
				if(l<0) l=i;
				r=i;
			}
		}
		if(l<0) add++;
		else {
			if(r-l+1<=k) {
				int r1=max(1,r-k+1), r2=l;
				int c1=max(1,j-k+1), c2=j;
				p[r1][c1]++;
				p[r1][c2+1]--;
				p[r2+1][c1]--;
				p[r2+1][c2+1]++;
			}
		}
	}
	int mx=0;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			p[i][j]+=p[i-1][j]+p[i][j-1]-p[i-1][j-1];
			if(p[i][j]>mx) mx=p[i][j];
		}
	}
	printf("%d\n",mx+add);
	return 0;
}

Branch Assignment

2016년 ICPC World Finals의 B번으로 출제된 문제입니다. 세트 전체 문제 중, 6번째로 많이 풀린 문제였습니다.

풀어볼 수 있는 곳의 링크를 첨부합니다.

https://www.acmicpc.net/problem/12766

문제의 내용은 아래와 같습니다.

$N$개의 교차로와 $M$개의 단방향 가중치 있는 도로로 이루어진 도시가 있습니다. 이 중 1, 2, … , $B$번 도시는 지사(Branch)이며, $B+1$번 도시는 본부입니다. 우리는 프로젝트의 효율성을 위해, $B$개의 지사들을 $S$개의 비어있지 않은 그룹으로 나누려 합니다. 각 나뉜 그룹 내에서는 모든 서로 다른 두 지사가 직접 통신할 수 있어야 하며, 어떤 두 지사 $U$, $V$의 통신 과정은 아래처럼 진행됩니다.

지사 $U$가 본부로 메시지를 송신합니다.
본부에서 지사 $V$로 메시지를 송신합니다.

어떤 메시지가 송신되는 비용은, 해당 메시지가 따라간 도로들의 가중치의 합이 됩니다.

이제 지사들을 $S$개의 그룹으로 잘 나누어, 송신 비용의 합을 최소화 해 주세요.

제한은 $2 <= N <= 5000$, $1 <= M <= 50000$, $1 <= S <= B < N$이며, 모든 교차로에서 다른 모든 교차로로 가는 경로가 항상 존재함이 보장됩니다.

풀이

두 개의 문제를 합쳐 놓은 문제입니다. 각 문제를 따로따로 분리해 내는 것이 먼저입니다.

우선, 어떤 두 지사가 서로 통신하려면, 항상 본부를 거쳐야만 한다는 점에 주목해 봅시다. 만약 어떤 그룹의 크기가 $K$라면, 그룹 내에 속한 모든 지사들은 다른 $K-1$개의 지사들과 통신해야 합니다. 이 때, 이것은 각 지사가 본부로 $K-1$개의 메시지를 송신하고, 본부로부터 $K-1$개의 메시지를 받는 것으로 나누어 생각할 수 있습니다. 즉, $d_1[u]$를 본부에서 지사 $u$로 오는 최단 경로로, $d_2[u]$를 지사 $u$에서 본부로 가는 최단 경로로 생각하면, $d_1[u] + d_2[u]$ 가 그룹 내의 모든 지사에 대해 $K-1$번 더해지는 것이 해당 그룹 내의 총 송신 비용이 됩니다. 각 지사가 어떤 그룹에 속하든 $d_1[u] + d_2[u]$의 값은 변하지 않으므로, 우선 $d_1$과 $d_2$를 다 구해둔 뒤, $c[u] = d_1[u] + d_2[u]$로 정의된 배열 $c$를 만들 수 있다면, 그래프 구조를 버리고 다음 문제로 진행할 수 있습니다.

이를 위해, 본부에서 다른 모든 지사로 가는 최단 경로와, 각 지사에서 본부로 가는 최단 경로를 모두 구해 둡니다. 모든 간선을 입력된 방향대로 사용하면 $d_1$을 얻을 수 있고, 모든 간선의 방향을 뒤집어 사용하면 $d_2$를 얻을 수 있습니다. 다익스트라 알고리즘을 이용하면 $O(MlogN)$ 정도의 시간에 $d_1 + d_2$를 모두 계산할 수 있습니다. 이제부터 이렇게 계산한 $d_1 + d_2$를 앞서 말했듯이 $c$라고 따로 정의하겠습니다.

이 작업이 모두 완료되었다면, 문제는 아래와 같이 변합니다.

$N$개의 정수들이 있을 때, 원소들을 $S$개의 비어있지 않은 집합으로 잘 나누어, 각 그룹에 대해 (그룹 크기 - 1) * (그룹 내 정수들의 합)의 총합을 최소화 하세요.

이렇게 변형한 문제에서 관찰할 수 있는 중요한 포인트가 있습니다. 만약 각 그룹의 크기가 이미 정해져 있다면, 최적해는 어떻게 될까요?

당연히 큰 그룹부터 차례대로 작은 수를 넣는 것입니다. 그룹 내 정수들은 그룹 크기에 비례하는 만큼 더해지기 때문에, 큰 그룹에 작은 수를, 작은 그룹에 큰 수를 넣으면 최적해가 됩니다. 따라서, 최적해 중 적어도 하나는 “정수들을 정렬했을 때, 연속한 원소들을 묶은 형태”가 됩니다.

이제 배열 $c$에 속한 정수들을 정렬해 둡시다. 그러면 문제는 다시 한번 아래처럼 변하게 됩니다.

$N$개의 정수들이 있을 때, 원소들을 $S$개의 파티션으로 분할하여, 각 파티션에 대해 (파티션의 크기 - 1) * (파티션 내 정수들의 합)의 총합을 최소화 하세요.

$N$이 충분히 작았다면, $O(N^3)$의 자명한 다이나믹 프로그래밍 솔루션이 존재하는 유명한 문제가 됩니다. 하지만, $N$이 최대 5000이기 때문에, 좀 더 빠른 방법이 필요합니다.

우선, $O(N^3)$의 다이나믹 프로그래밍 점화식을 살펴봅시다.

for(int i=1;i<=s;i++) {
    for(int j=1;j<=n;j++) {
        for(int k=1;k<j;k++) {
            d[i][j] = min(d[i][j], d[i-1][k] + (j-k+1)*sum(d[k..j]))
        }
    }
}

마지막 그룹이 될 구간을 결정하는 방식의 단순한 풀이입니다.

그러나 이 점화식은, 조건을 충분히 모두 활용하고 있지 않습니다. 연속한 원소를 묶는 이유가 무엇이었나요? 그룹의 크기가 정해졌을 때, 크기가 큰 그룹에 작은 원소를 순서대로 모아 넣는 최적해가 존재하기 때문입니다. 즉, i번째 그룹은 i-1, i-2, … , 1번째 그룹보다 크기가 작거나 같아야만 합니다. 다시 말해, i번째 그룹의 크기는 $floor(N/i)$를 넘을 수 없습니다. 만약 이 크기를 넘는다면, 1, 2, …, i-1번째 그룹의 크기도 최소한 i번째 그룹만큼 커야 하고, 이 경우 i번째 그룹까지의 크기만 모두 더해도 $N$이 넘어버리기 때문입니다.

따라서, 위 점화식을 아래처럼 변경해도 됩니다.

for(int i=1;i<=s;i++) {
    for(int j=1;j<=n;j++) {
        for(int k=max(1,j-n/i);k<j;k++) {
            d[i][j] = min(d[i][j], d[i-1][k] + (j-k+1)*sum(d[k..j]))
        }
    }
}

바뀐 부분은 세 번째 포문의 초기값 뿐입니다.

하지만 놀랍게도, 여기까지만 왔다면, $O(N^2logN)$의 풀이가 완성됩니다!

그 이유는, $N/1 + N/2 + … + N/N$이 약 $NlogN$에 근접하기 때문입니다. 증명은, 각 항을 $(N/1) + (N/2 + N/2) + (N/4 + N/4 + N/4 + N/4) + … $ 와 같이, 더 큰 값으로 교체하였을 때에도 그 계산 결과가 NlogN임을 보이면 쉽게 할 수 있습니다. 위처럼 코드를 작성하면 AC를 받을 수 있습니다. 단순한 관찰이 연쇄적으로 이루어져, 결론적으로 시간 복잡도를 줄이는 형태의 풀이입니다.

추가적으로, 이 문제에는 하나의 별해가 더 존재합니다. divide & conqure optimization이라 불리는 dp 최적화 테크닉이 그것입니다. 이 테크닉은 이 문제와 같은 형태의 점화식에서, 코스트(위 문제에서는 (그룹 사이즈 - 1) * (그룹 내 정수들의 합))가 특정 조건을 만족하면 사용할 수 있는 최적화 방법입니다. 이 방법을 사용할 경우, 그룹 크기를 강제하는 관찰을 하지 않더라도 문제를 해결할 수 있습니다. 지식이 많은 도움을 주는 좋은 예시가 됩니다.

소스 코드

첫 풀이는 관찰 위주이며, 코드가 간결하기 때문에, 별해인 divide & conqure optimization을 적용하여 정답을 소스 코드를 대신 소개합니다. 다익스트라 전처리 부분까지 포함되어 있습니다.

#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
#include <functional>
#include <utility>
#include <algorithm>

using namespace std;

typedef long long lli;
typedef pair<int,int> ip;

class e {
public:
	int v, w;
	e(int v, int w)
	:v(v),w(w)
	{}
};

vector<e> con[5001], rcon[5001];
int dd[5001], c[5001];
int n, b, s, m;

void dij(int s, bool inv) {
	memset(dd,-1,sizeof(dd));
	dd[s]=0;
	priority_queue<ip,vector<ip>,greater<ip> > q;
	q.push(ip(0,s));
	while(!q.empty()) {
		ip t=q.top();
		q.pop();
		int dis=t.first, u=t.second;
		if(dd[u]!=dis) continue;
		vector<e>& to=(!inv?con[u]:rcon[u]);
		for(int i=0;i<to.size();i++) {
			int v=to[i].v, w=to[i].w;
			if(dd[v]<0 || dd[v]>dis+w) {
				dd[v]=dis+w;
				q.push(ip(dd[v],v));
			}
		}
	}
}

lli d[5001][5001], p[5001];

void f(int L, int R, int l, int r, int k) {
	if(L>R || l>r) return;
	int mid=(l+r)/2, pv=-1;
	for(int i=L;i<=min(R,mid-1);i++) {
		lli w=d[k-1][i]+(mid-i-1)*(p[mid]-p[i]);
		if(w<d[k][mid]) {
			d[k][mid]=w;
			pv=i;
		}
	}
	f(L,pv,l,mid-1,k);
	f(pv,R,mid+1,r,k);
}

int main() {
	scanf("%d %d %d %d",&n,&b,&s,&m);
	for(int i=0;i<=n;i++) {
		for(int j=0;j<=b;j++)
			d[i][j]=(1LL<<61);
	}
	d[0][0]=0;
	while(m--) {
		int u, v, w;
		scanf("%d %d %d",&u,&v,&w);
		con[u].push_back(e(v,w));
		rcon[v].push_back(e(u,w));
	}
	dij(b+1,false);
	for(int i=1;i<=n;i++) c[i]=dd[i];
	dij(b+1,true);
	for(int i=1;i<=n;i++) c[i]+=dd[i];
	sort(c+1,c+b+1);
	for(int i=1;i<=b;i++)
		p[i]=p[i-1]+c[i];
	for(int i=1;i<=s;i++) f(i-1,b,i,b,i);
	printf("%lld\n",d[s][b]);
	return 0;
}

Filp and Shift

마지막으로는, 간결한 관찰과 매우 짧은 코드로 완성되는 재미있는 문제에 대한 소개로 마치겠습니다. 이 문제는 2001년도 ICPC 대전 리저널의 E번으로 출제된 문제입니다. 풀어볼 수 있는 링크를 첨부합니다.

https://www.acmicpc.net/problem/7347

문제의 내용은 아래와 같습니다.

위 그림처럼, 원형으로 검은 구슬과 흰 구슬이 $N$개 놓여 있습니다. 이 중 어떤 연속한 3개의 구슬을 골라, 그 순서를 뒤집어줄 수 있을 때, 검은 구슬은 검은 구슬끼리, 흰 구슬은 흰 구슬끼리 모여있게 만들 수 있다면 YES, 아니라면 NO를 출력하세요.

즉, 최종 결과는 아래와 같은 상태가 되어야 합니다.

제한은 $10 <= N <= 30$입니다.

풀이

먼저, 이 문제는 관찰이 완료된다면 매우 짧은 코드로 풀이가 완성됩니다. 따라서, 아직 문제를 풀어 보지 않았다면, 풀이를 보기 전 한 번쯤 생각을 해본 뒤 풀이를 보는 것을 권장합니다.

우선, 연속한 세 구슬의 순서를 뒤집는다는 것은 곧 i번째 구슬과 i+2번째 구슬의 순서를 바꾸는 것을 의미합니다. 가운데 구슬은 연산 이후에도 아무런 위치 변화가 없기 때문입니다. 즉, 홀수 번째 구슬끼리, 짝수 번째 구슬끼리만 따로 생각해 보면, 각 그룹(홀수 번째/짝수 번째) 내에서는 항상 원하는 형태를 만들어버릴 수 있습니다.

연산 횟수를 생각할 필요가 없으므로, 이제부터는 홀수 번째 구슬끼리/짝수 번째 구슬끼리에 대해서는 즉각적으로 원하는 형태로 변형할 수 있는 것으로 생각합니다.

만약 $N$이 홀수라면, $N$번째 구슬과 $N+2(= 2)$번째 구슬을 교환하는 작업에 대해 생각해볼 수 있습니다. $N$은 홀수이기 때문에, 서로 다른 두 그룹 간에 교류할 방법이 생긴 것입니다. 이 경우, 두 그룹이 따로 있지 않으며, 조작이 자유로운 하나의 그룹만 있는 상태가 되므로, 최종 상태는 아무 것이나 마음대로 만들 수 있습니다. 따라서, $N$이 홀수라면 답은 항상 YES입니다.

만약 $N$이 짝수라면, 홀수 번째 그룹과 짝수 번째 그룹은 교류할 방법이 없습니다. 따라서, 검은 구슬과 흰 구슬을 모으는 작업을 하기 위해 두 그룹이 서로 교류할 수는 없습니다.

구슬의 배열은 원형입니다. 따라서, 같은 색 구슬끼리 모았을 때, 어떤 그룹 하나는 $N$ -> $1$ 부분을 통과할 것이고, 다른 그룹 하나는 통과하지 않을 것입니다. 통과하지 않는 쪽에 주목해 봅시다. 통과하지 않는 쪽에 대해서만 생각할 것이므로, 선형으로 모두 모을 수 있는지만 생각하면 됩니다.

우선, 홀수 번째 그룹의 검은 구슬과 짝수 번째 검은 구슬의 개수를 세어 봅시다. 만약 1개가 넘게 차이난다면, 어떻게 배치하더라도 검은색 구슬끼리 모을 방법이 없습니다. 아래의 그림처럼 되는 것이 최선입니다.

홀수 번째 구슬은 위쪽에, 짝수 번째 구슬은 아래 쪽에 그렸습니다. 검은 구슬의 두 그룹이 붙어 있기 위해서는, 각 그룹 내의 검은 구슬의 수가 많아야 1 차이나야 합니다.

하얀 구슬에 대해서도 마찬가지입니다. 짝수 번째 그룹의 하얀 구슬의 개수와, 홀수 번째 그룹의 하얀 구슬의 개수가 1을 넘게 차이난다면 하얀 구슬끼리 모두 모을 방법이 없습니다.

검은 구슬과 하얀 구슬 중 한 쪽만 모두 모을 수 있다면, 다른 쪽은 반드시 모두 모이게 됩니다. 따라서, 답이 YES일 조건은 아래와 같이 정리됩니다.

$N$이 홀수
홀수 그룹과 짝수 그룹의 검은 구슬의 수가 1 이하 차이
홀수 그룹과 짝수 그룹의 흰 구슬의 수가 1 이하 차이

위 세 조건 중 하나 이상을 만족한다면 답은 YES이며, 그렇지 않을 경우 NO입니다. $N$이 매우 작음에도 불구하고, $O(N)$의 풀이가 존재하는 특이한 문제입니다.

소스 코드

구현은 매우 간단합니다. 위 조건을 그대로 코딩하면 됩니다. 정답을 받은 소스 코드를 첨부합니다.

#include <stdio.h>
#include <algorithm>

using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n, w, s1 = 0, s2 = 0, s3 = 0, s4 = 0;
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%d", &w);
			if (w) {
				if (i % 2 == 0) s1++;
				else s2++;
			}
			else {
				if (i % 2 == 0) s3++;
				else s4++;
			}
		}
		if (n % 2 || abs(s1 - s2) <= 1 || abs(s3 - s4) <= 1) puts("YES");
		else puts("NO");
	}
	return 0;
}

마무리

저번과 마찬가지로, 각 문제를 풀어볼 수 있는 링크를 따로 모아 보았습니다.

White Lines : https://codeforces.com/contest/1200/problem/D
Branch Assignment : https://www.acmicpc.net/problem/12766
Flip and Shift : https://www.acmicpc.net/problem/7347

감사합니다.

PS Training 1

White Lines

풀이

소스 코드

Branch Assignment

풀이

소스 코드

Filp and Shift

풀이

소스 코드

마무리

websocket, socket.io를 이용한 양방향 통신

2019 국제정보올림피아드(IOI) 문제 풀이