• Solved / AC ratio: 0/0 (N/A)
• Fastest submission: No submission
• Writer: ainu7

때로는 쉽게 보이는 문제가 어렵기도 하고, 어려울 듯한 문제에 의외로 간단한 해법이 존재하기도 합니다.
일단 점화식으로 접근해봅시다. 상태 state(a, b, c)를 a개의 계단이 남아있고, 이번 세트에서 연경이가 b승 c패인 상태라고 정의합시다. 그러면 이 상태에서 연경이가 가위바위보를 이기면 state(a-1, b+1, c), 지면 state(a-1, b, c+1), 비기면 state(a-1, b, c)로 이행할 것입니다. 이 때 그 state로 이행하지 않고 세트를 리셋하면 state(a-1, 0, 0)으로 이행하게 될 것입니다. 가위바위보의 결과 한 세트가 끝나는 경우도 있으므로 좀 더 자세히 써보면...
state(a, b, c) -> 이겼다 -> b = n-1 인 경우에는 state(a-1, 0, 0) 으로 이행 (이긴 세트 수에 +1)
b < n-1 인 경우에는 state(a-1, b+1, c) 로 이행 또는 state(a-1, 0, 0)로 이행
졌다 -> c = n-1 인 경우에는 state(a-1, 0, 0) 으로 이행
c < n-1 인 경우에는 state(a-1, b, c+1) 로 이행 또는 state(a-1, 0, 0)으로 이행
비겼다 -> state(a-1, b, c) 으로 이행 또는 state(a-1, 0, 0)로 이행
이제 expected(a, b, c) 를 a개의 계단이 남아있고, 이번 세트에서 연경이가 b승 c패인 상태에서의 이제부터 얻을 수 있는 기대 승수 라고 합시다.
expected(a, b, c) -> 이겼다 -> b = n-1 인 경우에는 expected(a-1, 0, 0)+1
b < n-1 인 경우에는 max(expected(a-1, b+1, c), expected(a-1, 0, 0))
졌다 -> c = n-1 인 경우에는 expected(a-1, 0, 0)
c < n-1 인 경우에는 max(expected(a-1, b+1, c), expected(a-1, 0, 0))
비겼다 -> max(expected(a-1, b, c), expected(a-1, 0, 0))
기본적으로 expected(0, ...) = 0.0이니까 여기서부터 시작해서 점화식을 사용해 expected(1, ...), expected(2, ...), ... 를 차례대로 구해나가다 보면 언젠가는 문제에서 원하는 답인 expected(steps, 0, 0)을 구할 수 있을 것입니다.
이 방법으로 구현하면 다음과 같습니다.

#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
  int C;
  scanf("%d", &C);
  for (int i=0; i<C; i++) {
    int steps, n;
    scanf("%d %d", &steps, &n);
    double prev[10][10] = {0};
    double next[10][10] = {0};
    for (int j=1; j<=steps; j++) {
      for (int k=0; k<n; k++)
        for (int l=0; l<n; l++) {
          next[k][l] = max(prev[k][l], prev[0][0]);
          if (k==n-1) next[k][l] += 1 + prev[0][0]; else next[k][l] += max(prev[k+1][l], prev[0][0]);
          if (l==n-1) next[k][l] += prev[0][0]; else next[k][l] += max(prev[k][l+1], prev[0][0]);
          next[k][l] /= 3.0;
        }
      for (int k=0; k<n; k++)
        for (int l=0; l<n; l++)
          prev[k][l] = next[k][l];
    }
    printf("%lf\n", prev[0][0]);
  }
  return 0;
}

여기까지는 많은 참가팀들도 생각해봤을 방법인데... 여기에는 두 가지 문제가 있습니다.
(1) steps <= 100000000 이니 O(steps*n^2) 짜리 알고리즘은 TLE가 나겠죠.
(2) double을 1억번 더하면 precision error가 쌓여서 거대해질 수가 있습니다.
(2)번은 double 대신 long double을 사용하면 해결됩니다.
(1)번이 문제인데요.. 직관적으로 생각해보면 앞으로 남은 계단의 수가 많을 수록 한 계단의 가치는 일정해집니다. 이것은 n이 상대적으로 작기 때문인데요, 다시 말하면 계단 수가 적게 남은 경우에서의 기대값의 흔들림은 계단수가 많아질 수록 희미해지게 됩니다. a>40000일 때 expected(a, 0, 0) - expected(a-1, 0, 0) 을 expected(40000, 0, 0) - expected(39999, 0, 0) 이라고 가정하면, expected(steps, 0, 0) - expected(40000, 0, 0) = (steps-40000) * (expected(40000, 0, 0) - expected(39999, 0, 0)) 이 될 것입니다.
실제로 이렇게 해 보면, 상대오차가 1e-9보다 훨씬 작아지게 됩니다.
이렇게 구현한 코드는 다음과 같습니다.

#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
  int C;
  scanf("%d", &C);
  for (int i=0; i<C; i++) {
    int steps, n;
    scanf("%d %d", &steps, &n);
    long double prev[10][10] = {0};
    long double next[10][10] = {0};
    long double plus = 0.0;
    for (int j=1; j<=steps; j++) {
      for (int k=0; k<n; k++)
        for (int l=0; l<n; l++) {
          next[k][l] = max(prev[k][l], prev[0][0]);
          if (k==n-1) next[k][l] += 1 + prev[0][0]; else next[k][l] += max(prev[k+1][l], prev[0][0]);
          if (l==n-1) next[k][l] += prev[0][0]; else next[k][l] += max(prev[k][l+1], prev[0][0]);
          next[k][l] /= 3.0;
        }
      if (j==40000) plus = (steps-40000) * (next[0][0]-prev[0][0]);
      for (int k=0; k<n; k++)
        for (int l=0; l<n; l++)
          prev[k][l] = next[k][l];
      if (j==40000) break;
    }
    double res = prev[0][0] + plus;
    printf("%.16lf\n", res);
  }
  return 0;
}