[Codeforces Round 943 (Div. 3)] Permutation Game

문제

https://codeforces.com/contest/1968/problem/D

난이도

백준기준 G5~G3쯤 될 것 같다.

알고리즘 분류

DFS, 게임이론, 수학

풀이

코포 치면서 이 문제 되게 좋았던 것 같다. 이름에서부터 게임이 들어가있듯이 게임이론에 대한 최소한의 이해를 하고 있으면 조금 도움이 된다. 일단 알고 들어가야 하는 것은 양쪽 플레이어는 항상 최선을 다해서, 최대의 점수를 얻기 위해 노력을 하고 이 문제에서 양쪽 플레이어는 서로에게 영향을 주지는 못한다. 따라서 각각 얻을 수 있는 최대 점수를 구해주면 된다.

점수는 1초 마다 현재 플레이어의 idx에 해당하는 score의 점수를 얻는다. 그리고 플레이어는 idx와 순열에 따라 이동을 하거나 하지 않을 수 있다. 

문제에서 플레이어의 맨 처음 위치가 주어진다. 그리고 그 위치는 순열에서 이동에 사용할 수 있다. 순열이 [3,0,1,2] 인 경우 플레이어의 idx가 0인 경우 idx 3으로 이동할 수 있고 0->3->2->1->0... 이런 식으로 이동하고 그 idx에 해당하는 score을 얻을 수 있다. 이 때 DFS를 이용하여 이동을 표현해줄 수 있다.

k가 1억까지 갈 수 있지만 n은 2만 정도이기 때문에 실제로는 k가 20000이 넘어가는 순간부터 방문했던 장소를 다시 반복해서 돌게 된다. 하지만 그럴 필요가 없다. 그 이유에 대해 생각해보자. 만약 x1->x2->x1이 이득인 경우가 존재한다면 방문했던 장소를 다시 가는 것이 이득일 것이다. 만약 x1>x2인 경우 x2로 이동하지 않고 가만히 있는 것이 이득이다. x1<x2인 경우 x1->x2 이동 한 후 x1로 이동하는 것 보다 가만히 있는 것이 이득이다.

자 이제 그럼 최대 점수를 어떻게 구할 수 있을 지 좀 더 생각을 해보자. 각 자리에서 얻을 수 있는 값은 다음과 같다. 남은 시간 동안 현재 idx에서 얻을 수 있는 스코어 + 현재 점수이다. 현재 점수가 뭐냐면 각 자리에서 취할 수 있는 행동은 2가지가 있다. 가만히 있거나 옆으로 옮겨가거나, 옆으로 계속 옮겨가면서 점수를 더해주었을 때 갖는 점수이다. 플레이어의 맨 처음 idx가 0이고, 순열이 [3,0,1,2] 인 경우 idx1에서 얻을 수 있는 점수는 현재 점수(지나온 곳) score[0]+score[3]+score[2]
+ 남은 시간 (k-지나온 곳의 개수) * 현재 idx의 스코어일 것이다.

그렇게 각 자리에서 얻을 수 있는 점수의 최댓값중 가장 큰 값이 큰 플레이어가 승리하게 될 것이다.

from sys import stdin
input=stdin.readline

for _ in range(int(input())):
    n,k,pb,ps=map(int,input().split())
    perm=list(map(int,input().split()))
    arr=list(map(int,input().split()))
    pb-=1
    ps-=1
    mxb=0
    t=0
    now=0
    vib=[0]*n
    vis=[0]*n
    while vib[pb]==0 and t<k:
        mxb=max(mxb,now+arr[pb]*(k-t))
        now+=arr[pb]
        vib[pb]=1
        pb=perm[pb]-1
        t+=1
    mxs=0
    t=0
    now=0
    while vis[ps]==0 and t<k:
        mxs=max(mxs,now+arr[ps]*(k-t))
        now+=arr[ps]
        vis[ps]=1
        ps=perm[ps]-1
        t+=1
    if mxb>mxs:
        print("Bodya")
    elif mxb<mxs:
        print("Sasha")
    else:
        print("Draw")