Codeforces Round #789 (Div. 1)

A. Tokitsukaze and Strange Inequality

code

1) 문제 해설

길이가 \(n \leq 5000\) 인 순열 \(p\)가 주어질 때

\( 1 \leq a < b < c < d \leq n, p_a < p_c,  \space p_b > p_d \)를 만족하는 \( (a, b, c, d) \) 쌍의 개수를 구하는 문제이다.

2) 알고리즘

\(cnt[i][j] \)를 \( p_1\)부터 \(p_i\)까지의 수 중, \(j \) 이하인 수의 개수라고 정의하자.

\( cmt\)를 전처리해 놓으면 특정 구간 \( [a, b]\)에서 \( k\) 이하인 수의 개수를 \( O(1) \) 안에 구할 수 있다.

\(b, c\)를 고정해두고 생각해보자. 그렇다면 위 조건을 만족하는 \(a \)의 개수는 \([1, b) \) 범위에서 \( p_c \) 이하인 수의 개수이고, 위 조건을 만족하는 \(d \)의 개수는 \( (c, n] \) 범위에서 \( p_b \) 이하인 수의 개수이다.

따라서 모든 \(b, c\)에 대해 위 조건을 만족하는 \( (a, b, c, d) \)의 개수를 구할 수 있으므로,

\( cnt \) 배열 전처리에 \( O(n^2) \), 모든 \(b, c\)에 대해 경우의 수를 계산하는 데 \( O(n^2) \) 안에 계산할 수 있다.

B. Tokitsukaze and Meeting

code

1) 문제 해설

\( n \times m\)의 방이 있다. 이 방에 0 또는 1이라는 번호를 가진 사람 \(n \times m \) 명이 순서대로 들어온다.

들어오는 사람은 \(1, 1\) 방으로 들어오고 원래 있던 사람은 오른쪽 방으로 밀려난다.

만약 맨 오른쪽 방에 있는 사람이 밀려나면 아랫 줄의 맨 왼쪽 방으로 들어간다.

이때, 각 행이나 열에 \( 1\) 인 사람이 하나라도 있으면 그 행이나 열을 좋은 행 또는 좋은 열이라고 한다.

모든 \( i \)에 대해, \(n \times m \) 명 중, \( i \) 명이 들어왔을 때, 좋은 행과 좋은 열의 개수를 구해야 한다.

 

2) 알고리즘

좋은 행을 구하는 알고리즘과 좋은 열을 구하는 알고리즘을 따로 분리해서 생각하자.

편의상 \( (n, m) \)개의 방 중 \( (a, b) \) 번 방을 \( i = a * m + b \) 번 방이라 하자.

 

좋은 열의 개수를 먼저 구해보자.

여기서는 사람 \(k\)명이 있을 때 사람 한 명이 \( 1\) 번 방으로 들어가면 \( k\) 명을 오른쪽으로 이동시킨다.

하지만, \( 1\)번 방이 아니라 \(k+1\) 번 방으로 들어간다고 해도 열의 관점에서 보면 차이가 없다.

따라서 단순히 \( col[i] \) 배열을 만들어 \(i\) 번 열에 사람이 있는지 여부를 저장하고,

사람을 추가할 때마다 \( col \) 배열을 갱신해 좋은 열의 개수를 구할 수 있다.

 

이제 좋은 행의 개수를 구해보자.

먼저 \(cnt[i]\)를 \( i-m+1\) 번째 사람부터 \(i\) 번째 사람 중 번호가 1인 사람이 있는지 여부를 저장하자.

예를 들어 방이 \( 3\times 3\) 크기이고, 사람의 번호가 \(100001000\)이라면 \(cnt\)는 \( 111001110 \)가 된다.

이 \(cnt\) 배열을 구해두면, 좋은 행의 개수를 구할 수 있다.

\( i\)명이 들어왔을 때 좋은 행의 개수는 \(cnt [i] + cnt [i - m] + cnt [i-2m] + \cdots \)가 된다.

따라서 이 식을 이용하면 사람을 추가할 때마다 \(cnt\) 배열을 이용하여 좋은 행의 개수를 구할 수 있다.

 

좋은 행과 좋은 열의 개수를 각각 구해준 뒤, 둘을 더하여 출력하면 된다.

C. Tokitsukaze and Two Colorful Tapes

code

1) 문제 해설

길이가 \( n \)인 두 순열 \(ca, cb\)가 주어진다.

이제 두 순열 \( a, b\)를 구성해야 한다.

이 때, \(ca_i = cb_j\)라면, \(a_i = b_j \)를 만족해야 한다.

\( \sum_{i} |a_i - b_i| \)가 최대가 되도록 두 순열 \(a, b\)를 구성해야 한다.

2) 알고리즘

정점이 \( n\) 개인 그래프에서, 모든 \( i\)에 대해 방향이 없는 간선 \(ca_i, cb_i\)를 추가한다.

그렇다면 단순 사이클이 여러 개가 생성된다.

이제 우리는 각 정점에 서로 다른 숫자를 \(1\)부터 \(n\)까지 할당하여, 각 간선에 대해 간선에 연결된 두 정점의 차이가 최대가 되도록 해야 한다.

크기가 2인 사이클이 있다고 하자. 그렇다면 두 정점에 각각 \(1, n\)을 할당하면, \(2(n-1)\)만큼 차이의 합이 증가한다.

이 상태의 사이클에서 정점 하나를 추가해보자. 이때 추가한 정점에 어떠한 수를 할당해도 차이의 합은 변하지 않는다.

그러면 크기가 2인 사이클에서 두 정점을 추가해보자. 이때 추가한 정점에 \(a, b\)를 할당하면 차이의 합은 \(2|a-b| \)만큼 증가한다.

다시 말하면 크기가 짝수인 사이클은 크기가 2인 사이클 여러 개로 생각해도 차이의 합은 변하지 않는다.

따라서 홀수인 사이클은 정점 하나를 지워 짝수인 사이클처럼 취급하고, 각 짝수 사이클은 크기가 2인 사이클 여러 개로 취급할 수 있다.

즉 주어진 그래프를 크기가 2인 사이클 여러 개로 나누고, 각 사이클의 정점에 \((1, n), (2, n-1), (3, n-2) \cdots\)를 할당하면 차이의 합을 최대로 할 수 있다.

D. Tokitsukaze and Permutations

code

1) 문제 설명

처음에 길이 \(n\)인 순열 \(a\)가 주어진다.

\(1\) 부터 \(n\)까지의 \(i\)에 대해 \( a_i > a_{i+1} \) 이면 교환한다. 이 작업을 총 \( k\) 번 반복한다.

그 후 새로운 배열 \(v\)를 정의한다. \(v[i]\)는 자신 왼쪽에 있는 원소 중 자신보다 큰 원소의 개수이다.

\(k\)와 \(v\)가 주어질 때, 가능한 원래 배열 \(a\)의 개수를 구하는 문제이다.

이때, \(v\)의 일부 원소는 지워져있을 수 있다.

2) 알고리즘

먼저 관찰을 하다보면, \(a\)와 \(v\)는 1대 1 대응이 된다. 따라서 \(v\)의 개수를 구하는 문제로 치환해서 풀 수 있다.

기존 배열 \(a\)에서 교환할 때 \(v\)에서 어떤 일이 일어나는지 살펴보면,

\(v_i, v_{i+1}\)을 교환하면, \(v_{i+1}-1, v_i\) 가 된다.

이를 응용하면, 초기 배열 \(a\)를 치환한 배열 \(v\)의 조건을 몇 개 확인할 수 있다.

먼저 초기 배열의 \(v[1, k]\)는 어떤 수가 들어와도 상관이 없다. 어떤 수가 들어오더라도 \(k\) 번 연산을 진행하면 의미가 없어진다. 따라서 \(v [1, k]\)에 수를 배열하는 경우의 수는 \(k!\)이다.

\(k\) 보다 큰 \(i\)에 대해, 초기 배열의 \(v [i]\)는 배열의 \(v [i-k]\)에 의해 결정된다.

만약 \(v[i-k]\)가 0이 아니라면 초기 배열의 \(v [i]\)는 \(v [i-k]+k\)가 되어야만 한다. 경우의 수는 1가지이다.

만약 \(v[i-k]\)가 0이라면 초기 배열의 \(v [i]\)는 \(k\) 이하의 수이어야 한다. 경우의 수는 \(k+1\) 가지이다.

만약 \(v [i-k]\)가 -1, 즉 정해지지 않았다면, 초기 배열의 \(v [i]\)는 어떤 수가 와도 된다. 경우의 수는 \(i+1\) 가지이다.

따라서 모든 \(i\)에 대해서 가능한 \(v [i]\)의 경우의 수를 구할 수 있고, 이를 모두 곱하여 가능한 초기 배열 \(v\)의 개수를 구할 수 있다.