Educational Codeforces Round 137

A. PassWord

code

문제 설명

0부터 9까지의 숫자 중복 허용하여 4개를 사용해 만들 수 있는 비밀번호의 수를 출력해야 한다.

이때, 비밀번호는 서로 다른 숫자를 2개씩 포함해야 하고, 사용하지 않아야 하는 숫자들도 주어진다.

알고리즘

총 10,000가지의 조합을 하나씩 검사해보며 문제의 조건을 만족하는 지 확인해보면 된다.

B. Permutation Value

code

문제 설명

길이가 \(n\)인 순열 \(a\)에 대하여 이 순열의 값을 연속된 부분 배열이 순열인 부분 배열의 개수로 정의된다.

순열의 값이 최소가 되도록 하는 순열을 출력해야 한다.

알고리즘

먼저 순열의 값은 최소 2라는 것을 쉽게 발견할 수 있다. [1]과 \(a\), 이렇게 2개의 부분 배열이 순열인 경우가 2가지 존재한다. 따라서 순열의 값이 2가 되도록 순열을 만들어주면 된다. 단순하게 맨 앞 원소를 1로, 맨 뒤 원소를 2로 두면 나머지 원소를 아무곳이나 두어도 순열의 값이 2가 된다.

C. Save the Magazines

code

문제 설명

상자가 일렬로 총 \(n\)개가 있고 각 상자에는 잡지가 \(a_i\)개 들어있다. 이 중 몇 개의 상자는 뚜껑이 덮여있다. 만약 \(i\)번 상자의 뚜껑이 처음부터 덮여있었다면, 이 뚜껑을 \(i-1\)번 상자로 옮길 수 있다. 이후 비가 올 때, 뚜껑이 덮여져있는 상자에 있는 잡지는 멀쩡하고 나머지 잡지는 비에 젖게 된다.

뚜껑을 적절히 옮겨서 젖지 않게 보존할 수 있는 잡지의 최대 개수를 구해야 한다.

알고리즘

이 문제는 dp로 풀 수 있다. 단순하게 \(dp[n][i]\)를 \(n\)번째 상자까지 뚜껑을 옮길 지 말 지 결정하였고, \(n\)번째 상자에 있는 뚜껑을 사용하여 \(n\)번째 상자를 덮었는 지 여부가 \(i=0\text{ or }1\)일때, 보존할 수 있는 잡지의 최대 개수로 정의하자.

먼저 \(i\)번째 상자에 뚜껑이 없는 경우에는 단순히 \(dp[n][0] = \max(dp[n-1][0], dp[n-1][1])\), \(dp[n][1] = 0\)가 된다.

하지만 뚜껑이 있는 경우에는 아래와 같이 dp값을 갱신해줘야 한다.

\(dp[n][0]=\max(dp[n-1][0] + a[n], dp[n-1][1])\)

\(dp[n][1]=\max(dp[n-1][0], dp[n-1][1])+a[n]\)

위의 식은 뚜껑을 \(n-1\)번 상자로 옮기는 경우이고, 아래의 식은 뚜껑을 옮기지 않는 경우이다. dp table을 채워 이 문제의 답인 \(max(dp[n][0], dp[n][1])\)를 출력하면 된다.

D. Problem with Random Tests

code

문제 설명

길이 \(n\)이 최대 1,000,000인 2진수가 주어진다. 맨 앞자리가 0일 수 있음에 유의해야 한다.

이 2진수의 두 연속 부분 문자열을 구하고, 두 2진수를 or하여 값을 얻을 때, 가능한 값의 최댓값을 출력해야 한다.

이때, 테스트 케이스는 랜덤, 즉 각 자리에 1이 등장할 확률이 독립적이고 모두 0.5이다.

알고리즘

일단 or하여 값을 얻을 때 모든 경우를 고려하지 않아도 되고, 두 2진수 중 하나는 주어진 2진수를 그대로 사용하고, 다른 2진수는 왼쪽으로 \(k\)만큼 shift 연산을 하여 or하는 경우만 고려해도 된다. 하지만 이렇게 경우를 줄이더라도 결국 가장 큰 2진수를 구하려면 \(n^2\)번의 연산을 진행해야 한다.

하지만 테스트 케이스가 랜덤이라는 사실을 활용하면, shift를 많이 진행할 필요가 없다는 것을 알 수 있다. 만약 shift를 \(k\)번 한 것이 \(k-1\)번 이하로 한 것보다 더 좋으려면, 앞의 연속된 \(k-1\)개의 bit가 모두 1이어야 함을 알 수 있다. 따라서 약 100번 정도만 비교를 진행한다면 오답이 나올 확률이 \(\0.5^{100}) 정도로 매우 줄어들어 항상 정답을 얻을 수 있다.

c++의 bitset을 활용하면 보다 쉽게 구현할 수 있다.

F. Intersection and Union

code

문제 설명

총 \(n\)개의 구간 \([l_i, r_i]\)가 주어진다. \(S_i\)는 구간 \([l_i, r_i]\)에 있는 모든 자연수들의 set이다.

이제 1번째 set부터 \(n\)번쨰 set까지 순서대로 \(or, and, xor\)연산 중 하나를 진행한다. 따라서 총 \(3^{n-1}\)종류의 연산이 가능하다. 이렇게 얻은 \(3^{n-1}\)개의 set들의 크기의 합을 계산해야 한다.

알고리즘

먼저 가장 단순한 문제를 풀어보자. \(S_i\)는 0만 포함한 집합이거나 공집합 중 하나인 경우만 살펴보자. 그렇다면 계산 결과 또한 0만 포함한 집합이거나 공집합이 된다. 따라서 우리는 이중에서 0만 포함한 집합이 되도록 하는 연산이 몇 종류인지 알고 싶다.

따라서 dp를 사용하여 이를 계산하자. \(dp[n][i]\)를 \(n\)번째 set까지 연산을 진행하였을 때, set의 크기가 \(i\)인 경우의 수로 정의한다. 여기서는 \(i\)는 0 또는 1이 된다.

만약 \(S_i\)가 0이라면 점화식은 아래와 같이 구할 수 있고,

\(dp[i][0]=3dp[i -1][0]+dp[i-1][1]\)

\(dp[i][1]=2dp[i-1][1]\)

\(S_i\)가 1이라면 점화식은 아래와 같이 구할 수 있다.

\(dp[i][0] = dp[i-1][0]+1dp[i-1][1]\)

\(dp[i][1] = 2dp[i-1][0]+2dp[i-1][1]\)

위 두 개의 식은 단순하게 2 by 2 행렬로 표현할 수 있다.

 

이 문제에서는 set이 연속된 구간이다. 따라서 0부터 300,000의 모든 수에 대해 각 숫자가 set에 포함되는 지 여부에 따라 \(n-1\)개의 matrix를 곱해줘야 한다. 이를 단순하게 구현한다면 시간초과가 나게 된다.

여기서 구간이 연속으로 주어진다는 것을 이용하면 된다. \(l_i, r_i\)에 대해 \(l_i\)보다 작거나 \(r_i\)보다 큰 숫자들은 set에 포함되지 않은 경우의 행렬을 곱해주고, \(l_i\)이상 \(r_i\)이하인 경우에는 set에 포함된 경우의 행렬을 곱해주면 된다.

구간에 곱을 하는 연산은 lazy segment tree로 구현할 수 있으므로, lazy segment tree를 이용하여 \(O(nlogn)\)의 시간복잡도로 문제를 해결할 수 있다.

 

사실 lazy segment tree는 시간복잡도 앞 상수가 크고, 거기다가 트리 원소를 행렬로 했으며 최적화도 딱히 안하고 struct 써서 구현했으며 \(n\)범위도 커서 시간초과가 충분히 날 수 있는 코드였다. 하지만 문제의 시간이 널널했고, 운이 좋아서 시간제한이 5초인데, 실행시간 4.2초로 간신히 통과했다.