AC-JSC2019-C. Cell Inversion

작성일

문제: https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c

해설: https://img.atcoder.jp/jsc2019-qual/editorial.pdf

  • 간단한듯 보이는 문제이지만 너무 어려웠다. 이게 어떻게 C번인지 이해가 안감..
  • 그리고 이걸 푼 사람들도 새삼 대단해보인다.
  • 문제를 정리하면 다음과 같다.
    • B와 W로 구성 된 2N길이의 문자열이 있다.
    • N은 $10^5$으로 $O(N\log{N})$ 이하의 풀이가 필요하다.
    • 문자를 2개씩 총 N번 선택한다. 이때 각 문자는 1번만 사용할 수 있다. 즉 모든 문자가 딱 1번씩만 선택된다.
    • 선택한 문자 2개를 포함하여 그 사이에 있는 문자가 inversion된다. B는 W로, W는 B로 inversion 된다.
    • 최중 문자열을 모두 W로 만드는 선택의 경우의 수를 출력하라.

첫 번째 명제

일단 문제의 조건에 부합하는 선택을 하면서, 각 문자를 L과 R로 분류하자. L은 선택시 왼쪽에 있을 문자, R은 선택시 오른쪽에 있을 문자이다. 선택 이후 도출된 LLRR과 같은 문자열에서 L과 R을 어떤 순서로 짝짓든간에 무조건 결과가 같다.

문제를 푸는 동안 심지어 첫번째 명제 조차 눈치채지 못했다! 그리고 Editorial을 보면서도 이해하는데 한참이나 걸렸다. 무진장 자괴감이 온다. 여튼 증명은 다음과 같다.

  • 일단 예를들어 생각하자. BWWB가 입력으로 주어지면,
    • LLRR을 위의 선택의 예시로 생각해 볼 수 있다. 두가지 가능성을 생각해볼 수 있다.
      • 1,3과 2,4를 짝짓는 경우
      • 1,4와 2,3을 짝짓는 경우
    • 위의 두가지 가능성 모두 결과가 WWWW로 같다.
    • 왜나하면 선택에 포함되는 횟수가 항상 같기 때문이다.
      • 1은 선택에 1번 포함되고
      • 2는 선택에 2번 포함되고
      • 3은 선택에 2번 포함되고
      • 4는 선택에 1번 포함된다
  • 위의 예시를 근거로 생각해 볼때, 최종 결과는 선택에 포함되는 횟수가 결정한다.
  • 선택에 포함되는 횟수는, 아래와 같이 결정된다.
    • L인 문자: 왼쪽에 있는 L의 수를 $L_i$라 두고, R의 수를 $R_i$라 둘 때, $L_i - R_i + 1$이 선택에 포함되는 횟수이다.
    • R인 문자: 반대
  • 결국 LLRR과 같은 문자열이 도출되면, 어떤 순서로 짝을 짓든간에 각 문자가 선택에 포함되는 횟수는 동일하다.

두 번째 명제

첫 번째 명제에서 처럼 L과 R로 선택을 해서 도출되는 LLRR과 같은 결과물을 X라고 하자. 이 X는 반드시 하나만 존재한다.

사실 첫번째 명제를 생각하지 못하게 만드는 이유는, 두번째 명제가 없기 때문이다. X가 반드시 하나만 존재한다는 보장이 있으면, 1번을 더 생각해내기 쉬울 것이다. 여튼 여러개의 보조명제를 이용해서 증명해보자.

보조명제1: 왼쪽 끝은 반드시 B이고, L이어야 한다. W이라면 답은 0이다.

비교적 쉽게 증명할 수 있다.

  • 왼쪽 끝이면 반드시 L이 된다. R이 선택된다면 짝지을 L을 찾을 수 없기 때문이다.
  • 이제 첫 번째 명제에서 사용한 선택에 포함되는 횟수를 계산해 보면, 1이 나온다. 즉 B가 왼쪽 끝에 있어야 1번 inversion되어서 W가 된다.

보조명제2: 나머지 Cell에 대해서 아래가 성립한다.

문자열 홀수번째 짝수번째
B L R
W R L

증명은 아래와 같다.

  • 두번째 Cell을 생각해보자. 첫번째는 무조건 B/L이니 왼쪽으로 부터 1개의 선택이 강요된다.
    • 만약 두번째 Cell이 B라면 L이 되어선 안된다. 그럼 선택된 횟수가 2로 늘어나서 다시 B가 된다. 그러니 R이 되어야 한다.
    • 만약 두번째 Cell이 W라면 R이 되어선 안된다. 그럼 선택된 횟수가 1뿐이므로 B가 된다. 그러니 L이 되어야 한다.
  • 두 번째 Cell까지 선택된 결과는 아래와 같다.
    • BB -> LR
    • BW -> LL
  • 즉 세 번째 Cell에서는 선택된 횟수가 무조건 짝수번 누적된 채로 시작한다.
    • 그러므로 처음부터 시작하는거랑 유사해진다.
    • 그러나 W가 될 수도 있다. 이 경우를 생각해보면 BBW는 될 수 없다.
      • 논리상 LR뒤에서 짝수를 유지하려면 R이 붙어야 한다.
      • 그러나 LRR이 된다면 R과 짝지을 L의 수가 부족하다.
      • BWW는 LLR로 가능하다.
    • 결론적으로 세번째에서 B가 된 경우는 모두 L이고, W가 된 경우는 모두 R이다.
  • 이를 반복해 보면 홀/짝에서 위 표와 같은 규칙을 찾을 수 있다.

이제 보조명제2를 활용하면 X가 하나인 것이 도출된다. B와 W가 정해지면 L과 R은 한 가지 값으로 결정되기 때문이다.

마지막 계산

이제 계산하는 부분만 남았다. LLRLRR인 문자열을 생각해보자.

  • 가장 왼쪽에 있는 R부터 선택을 하면, 짝지을 수 있는 L의 수가 2개이다.
  • 그 다음 R은 짝지을 L의 수가 3개이지만, 앞선 R이 한개를 썼으므로 총 2개이다.
  • 마지막 R은 짝지을 L의 수가 3개이지만, 앞선 두개의 R이 이미 선택되었으므로, 가능한 경우의 수가 1가지 이다.

최종 결과는 $3\times2\times1 = 6$이다. 같은 방법으로 LLLRRLRR을 계산해보면 $3\times2\times2 = 12$ 가 나온다. 이를 구현하면 된다.