algospot.com :: 과거 게시판: [editorial] Editorial

[editorial] Editorial - F. The Game of Death

[문제 해설]
외친 숫자 X가 최대 100만이기 때문에 모든 확률을 따라가보면서 하면 시간 내에 나오지 않습니다.
이런 문제는 행렬을 이용해서 풀이할 수 있는데, 행렬 A를 다음과 같이 정의합니다.
A[i, j] = i가 j를 가리키고 있을 확률
맨 처음은 항상 나부터 시작하기 때문에 X번째에 어떤 사람이 걸릴 확률은 A^X * (1 0 0 0 ... ) 을 계산하면 되는데 이를 다시 정리하면
A^X[0, j] = X번째에 j가 걸릴 확률이 됩니다.
여기에서 A^X 를 빠르게 구하기 위해서는 B에 A^1을 저장한 후에 B를 계속 제곱하면서 곱해나가면 O(lg X)번의 계산으로 A^X를 계산할 수 있습니다. 예를 들어서 A^13 = A^8 * A^4 * A^1 = B^8 * B^4 * B^1 이 됩니다.
아래 소스코드는 Matrix Multiplication을 O(N^3)으로 계산한 코드입니다.
[spoiler="소스코드 보기"]

#include <cstdio>
#include <algorithm>
using namespace std;
struct Matrix
{
        double table[200][200];
        void multi(Matrix& rhs, int n)
        {
                double temp[200][200];
                for (int i = 0; i < n; ++i)
                        for (int j = 0; j < n; ++j)
                        {
                                temp[i][j] = 0.0;
                                for (int k = 0; k < n; ++k)
                                        temp[i][j] += table[i][k] * rhs.table[k][j];
                        }
                for (int i = 0; i < n; ++i)
                        for (int j = 0; j < n; ++j)
                                table[i][j] = temp[i][j];
        }
};
Matrix a, b;
int T, n, m, x, t;
int main()
{
        scanf("%d", &T);
        while (T--)
        {
                scanf("%d%d%d%d", &n, &x, &m, &t);
                fill(a.table[0], a.table[n], 0.0);
                fill(b.table[0], b.table[n], 0.0);
                for (int i = 0; i < n; ++i)
                {
                        int x;
                        scanf("%d", &x);
                        --x;
                        if (i == 0)
                                a.table[i][x] = b.table[i][x] = 1.0;
                        else
                        {
                                double p = (1.0) / (t * 2.0 + 1.0);
                                for (int j = -t; j <= t; ++j)
                                {
                                        int y = x + j;
                                        if (y < 0) y += n;
                                        else if (y >= n) y -= n;
                                        a.table[i][y] = b.table[i][y] = p;
                                }
                        }
                }
                for (int sq = 2; sq <= x; sq *= 2)
                {
                        b.multi(b, n);
                        if (x & sq)
                                a.multi(b, n);
                }
                for (int i = 0; i < m; ++i)
                {
                        int x;
                        scanf("%d", &x);
                        if (i) printf(" ");
                        printf("%.5lf", a.table[0][x - 1] + 1e-9);
                }
                printf("\n");
        }
}

[/spoiler]

[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

16년 전

7개의 댓글이 있습니다.

Taeyoon_Lee

이렇게 짜면 TLE던데요..?

16년 전 link
Toivoa

모의고사때에는 Matrix Multiplication을 O(N^3)으로 계산하는 것까지 허용했다고 들었습니다. Matrix Mutliplcation을 더 빠르게 하기 위해서는 Strassen이나 Coppersmith-Winograd 알고리즘을 사용하면 됩니다.
LIBe set에서는 vc9++로 보내면 ac 나옵니다. -_-;

16년 전 link
Taeyoon_Lee

제가 분명히 O(N^3 * logX) 의 시간복잡도로 풀었는데 TLE가 나서 뭔가 다른 좋은 방법이 있는 줄 알았어요.. OTL

16년 전 link
Toivoa

더 좋은 방법은 JM님이 써주실겁니다.

16년 전 link
JongMan

저희가 미리미리 저지 솔루션을 돌려보고 한 게 아니라서, TLE 관련 판정이 좀 일관성이 없었을 수도 있습니다.죄송해요 굽신굽신 (....)

16년 전 link
dgsquare

문제에 대해 정확한 이해가 안되서 질문드립니다.
솔루션의 결과치가 해석이 잘 안되서요.
문제의 입력을 조금 줄여서,
10 2 10 1
2 3 4 5 6 7 8 9 10 1
1 2 3 4 5 6 7 8 9 10
이런식의 입력을 넣어 보았습니다. (숫자는 2를 불렀다고 하고, 오차범위는 1로 줄였습니다.) 그럼 솔루션의 결과가
0.00000 0.11111 0.22222 0.33333 0.22222 0.11111 0.00000 0.00000 0.00000 0.00000
이렇게 나오는데요.
첫번째 차례에서 재욱이 2번을 선택했으므로 (재욱은 정확히 선택하므로)
0.00000 1.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
가 되는 것은 알겠습니다. 그런데 두번째에서 2번 사람이 3번을 선택했으므로, 균등확률로 분배되게 되면,
0.00000 0.33333 0.33333 0.33333 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000
이런 결과가 나와야 하는것 아닌가요?
제가 문제를 잘못이해한것 같은데 어떻게 솔루션의 결과가 나오는지 알려주시면 고맙겠습니다 (꾸벅 _-_ )

16년 전 link

Toivoa

에디토리얼로 올린 소스코드가 잘못된 것입니다. 모의고사때 썼던 데이터가 허술했나보네요.
참고로 에디토리얼 코드는 대회 후에 독립적으로 작성된 코드이며, 확률을 계산하는 부분을 아래와 같이 고치면 됩니다.

                for (int i = 0; i < n; ++i)
                {
                        int x;
                        scanf("%d", &x);
                        --x;
                        a.table[i][i] = 1.0;
                        if (i == 0)
                                b.table[i][x] = 1.0;
                        else
                        {
                                double p = (1.0) / (t * 2.0 + 1.0);
                                for (int j = -t; j <= t; ++j)
                                {
                                        int y = x + j;
                                        if (y < 0) y += n;
                                        else if (y >= n) y -= n;
                                        b.table[i][y] = p;
                                }
                        }
                }
                for (int sq = 1; sq <= x; sq *= 2)
                {
                        if (x & sq)
                                a.multi(b, n);
                        b.multi(b, n);
                }

15년 전 link

정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

[editorial] Editorial - F. The Game of Death

7개의 댓글이 있습니다.