Educational Codeforces Round 70 (Rated for Div. 2) 후기

Educational Codeforces Round 70 (Rated for Div. 2)

Dashboard - Educational Codeforces Round 70 (Rated for Div. 2) - Codeforces

A. You Are Given Two Binary Strings...

$S_k$은 0과 1로 이루어진 문자열(2진수로 나타낸 수) $f(x)$를 $k$번만큼 밀어낸 2진수 문자열과 와 $f(y)$의 합이다. 여기서, $k$는 우리가 임의로 정할 수 있는 수이다. 문제에서 요구하는 것은 이 $S_k$를 뒤집은 문자열(앞으로 $revS_k$라고 하겠다)이 $k$에 따라 여러가지 생길 수 있는데 그 중에서 가장 사전 순으로 앞서는 문자열을 만들기 위한 $k$값을 구하라는 문제였다.

처음엔 문제를 보고 조금 당황했지만, 사전 순으로 가장 앞서는 문자열이 0이므로 문자열 맨 뒤에서 등장하는 0의 개수를 최대화하면 되는 문제이다. 그렇다면 $f(x)$의 가장 오른쪽에 등장하는 1을 없애주면 된다는 뜻이다.

 

따라서, $f(x)$의 오른쪽에서 가장 빨리 등장하는 1의 좌표를 $posX$라고 하고 $f(y)$의 오른쪽에서 가장 빨리 등장하는 1의 좌표를 $posY$라고 하자. 그렇다면 $revS_k$를 사전 순으로 가장 앞서게 할 수 있는 방법은 $posY$에 있는 1을 $posX$위치까지 밀어내어 더해버리면 된다는 것이다.

 

단, 예외가 있는데 $posX$는 반드시 $posY$보다 크거나 같은 곳에서 시작해야한다는 것이다. 왜냐하면 $k$는 0이상의 정수이므로 오른쪽으로 쉬프트 하는 것은 불가능하기 때문이다.  따라서 답은 적당한 예외처리를 한 $posX-posY$가 될 것이다. 빠르게 풀고 10분정도에 AC.

 

B. You Are Given a Decimal String...

$x-y$ 카운터가 있을 때, 처음에 카운터의 값이 0이고 각각 $x$ 또는 $y$를 더할 수 있다고 한다. 이때, $x$ 또는 $y$를 더한 이후 다음 차례에서 반드시 이 값을 출력해야한다고 한다.

 

하지만, 주어진 문자열은 데이터가 손실된 문자열이라고 한다. 손실된 문자열이 주어지고 원래의 문자열을 출력한다고 할 때, $x-y$ 카운터를 사용하면 몇 번만에 문자열을 전부 출력할 수 있는지 구하라는 문제이다. 단, $x$와 $y$는 $[0, 9]$의 자연수이다.

 

이 문제는 각 숫자 (0~9)에서 다른 숫자(0~9)로 가는 최소 비용을 구해야하는 문제이다. $N=10$이니 BFS를 통해 도달 가능성을 구한다음, Floyd알고리즘을 사용해 각 숫자에서 다른 숫자로 가는 최소 비용을 구해야한다.  물론 자기 자신에서 자기 자신으로 가는 비용도 구해야 한다. 그렇게 각 $x-y$ 카운터마다 비용 테이블을 생성한 다음, $2*10^6$길이의 문자열을 만들기 위해 각 $x-y$카운터마다 필요한 비용을 2차원 행렬로 구하라는 문제이다.

 

시간 복잡도가 굉장히 빡빡한 문제였는데 최소 비용을 구하는 과정만 해도 $O(10^3)$이 걸리고, 카운터는 100개이고, 문자열은 200만자리이고. 즉 $O(10^5 + 10^2 * |S|)$만큼의 시간복잡도가 걸리는 문제였다. 시간제한이 2초이고 최대 연산 횟수가 $2*10^8$이라 불안했지만 Editorial에는 c++을 사용하면 충분히 돌아간다라고만 써있더라. 차라리 20만자리였으면 걱정을 안했을 것 같은데.. 이건 문제 낸사람이 조금 잘못했다고 생각한다.

 

어쨌든 대회 중간에는 BFS, 플로이드를 구현하고 문자열에서 문자간 거리를 구하는 과정에서 디버깅을 하다 대회가 끝나버렸다.

대회 끝나자마자 다시 풀고 AC.

 

D. Print a 1337-string...

되게 재미있고 참신한 문제였다. 사실 B나 C정도가 적당하다고 생각한다. 이 문제는 사람들이 많이 풀고 있길래 보고있는 문제였는데, 처음에 보자마자 소인수분해가 떠올랐다. n이 주어지면 소인수 분해를 적당히 한 다음. 1과 3, 7의 개수를 적당히 분배해 String을 출력하면 되겠거니 했는데, 한 10억쯤 되면 소수가 들어오면 어떻게하지..? 라는 생각이 나더라.

 

1이나 7을 10억개 출력할 수는 없는 노릇이라 대회 중에는 D를 버리고 다시 B를 풀었다.

 

정해는 되게 신박했다! 곱으로 표현할 수 없다면 더하라는 건데,

어차피 1337을 만드는 방법은 1 1개, 3 2개, 7 2개를 만드는 것인데, $33...33$에서 2개를 취하는 것이므로 3의 개수는 $nC2$가 되는 것이다. 즉, 3의 개수를 $x$라고 하면 $x(x-1)/2 <= n$인 $x$를 찾아주면 된다는 것이다. 그럼 일단 $x(x-1)/2$개의 1337을 만들 수 있다. 그럼 나머지 $n-xC2$도 처리를 해줘야 한다. 1337을 정확히 몇 개 만드는건 간단하다. 바로 $1337....7$과 같이 숫자 하나만 주구장창 나열하면 되는 것이다. 업솔빙을 하는 도중에는 먼저 133..337을 출력하고 뒤에 1337...7을 따로 출력했지만, 이렇게 하면 경우의수가 더 늘어나버린다. Editorial에서는 맨 처음에 133을 출력하고 7을 $n-xC2$개만큼 출력한 다음, 3을 $x-2$개(앞에 2개를 이미 출력했으므로) 출력한 다음 7을 출력하면 된다고 한다. 감동했다.

 

즉, 만약 $n=100$이라면?

$1337777777773333333333337$

Editorial 보고 AC를 받았다.

 

 

 

총체적으로 구현이 까다로운 대회였는데, 풀이가 되게 간단하고 깔끔했다. 특히 D번이 맘에 들었던 문제였다.