Array Game

문제

Problem - 1600E - Codeforces

배열이 주어지면 Alice와 Bob이 서로 한번씩 돌아가면서 배열의 양쪽 끝의 숫자를 뺄 수 있습니다.

두명이 뺀 숫자들은 항상 증가 수열을 이뤄야하며 자신의 차례에서 증가수열을 이룰 수 없을 때 그 사람은 

패배 입니다.

선공은 항상 Alice가 먼저이고 두 사람중 승리하는 사람을 출력하는 문제 입니다.

 

예를들어 배열에 3, 8, 10, 5, 7, 6 이 있다고 하면 Alice는 양쪽 끝인 3과 6을 선택할 수 있습니다.

만약 6을 선택하면 두사람은 항상 오른쪽의 수만 빼야 합니다. 3은 6보다 작으므로 증가수열을 이룰 수 없기 때문입니다

그럼 Bob이 7을 뽑으면 Alice는 더이상 뽑을 숫자가 없어지므로 패배하게 됩니다.

따라서 Alice는 미리 처음에 수를 뽑을 때 연속되는 위치에서 증가하는 수열이 짝수개인지 홀수개인지 파악해야 합니다

결국 Alice는 무조건 3을 뽑아야합니다.

3을 뽑으면 또 8, 10, 5, 7, 6 이 남기 때문에 여기서도 마찬가지로 양쪽끝의 증가수열의 길이가 홀수개인지 짝수개인지 파악하면서 진행하여야 합니다.

vector<ll>v(n), A(n), B(n);
for (int i = 0; i < n; i++)cin >> v[i];
A[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
	if (v[i] < v[i + 1])A[i] = A[i + 1] + 1;
	else A[i] = 1;
}
B[0] = 1;
for (int i = 1; i < n; i++) {
	if (v[i] < v[i - 1])B[i] = B[i - 1] + 1;
	else B[i] = 1;
}

벡터 v에다가 주어진 수열들을 모두 저장합니다.

A벡터 에는 수열의 오른쪽에서 왼쪽으로 진행되는 수열들의 증가수열의 길이를 체크할 것입니다. 

따라서 벡터 v를 거꾸로 돌아가면서 prefix sum형태로 진행하게 됩니다.

가장 왼쪽의 수열은 자기자신 밖에 없으므로 A[n-1]은 항상 1입니다.

반대로 B벡터 에는 수열의 왼쪽에서 오른쪽으로 진행되는 수열들의 증가수열의 길이를 체크할 것입니다.

가장 오른쪽의 수열은 자기자신 밖에 없으므로 B[n-1]은 항상 1입니다.

x = 0, a = 0, b = n - 1;
    ans = -1;
    while (1) {
        if (v[a] > v[b]) {
            if (A[a] & 1)break;
            else if (v[b] > ans) {
                ans = v[b];
                b--;
            }
            else {
                x++;
                break;
            }
        }
        else if (v[b] > v[a]) {
            if (B[b] & 1)break;
            else if (v[a] > ans) {
                ans = v[a];
                a++;
            }
            else {
                x++;
                break;
            }
        }
        else {
            if ((A[a] & 1) == 0 && (B[b] & 1) == 0)x++;
            break;
        }
        x++;
    }
    if (x & 1)cout << "Bob";
    else cout << "Alice";

1번째 줄에서 x는 턴의 갯수를 셀것입니다. Alice가 시작하는 턴은 0번째 턴으로 시작합니다. 따라서 턴이 홀수에서 끝나면 Bob이 이기고 짝수에서 끝나면 Alice가 이깁니다. 

a와 b는 양쪽끝의 포인터 역할을 합니다. ans는 가장 최근에 배열의 넣은 값을 기록하는 역할을 합니다.

4번째줄의 코드와 15번째 줄의 코드는 성격이 완전히 똑같고 서로 반대되는 상황이기 때문에 4번째 코드만 설명하겠습니다.

5번째 줄) 만약 주어진 배열에서 맨 왼쪽의 숫자가 크다면 먼저 왼쪽에서 오른쪽으로 진행하는 증가수열의 길이를 체크한 A벡터의 값이 홀수 이면 그대로 멈춥니다. 왜냐하면 반대쪽은 이미 왼쪽보다 작기 때문에 진행하는 방향은 항상 왼쪽이기 때문입니다.

6번째 줄) 그게 아니라면 맨 왼쪽의 숫자를 골랐을 때 자기 자신이 지게 되므로 무조건 오른쪽의 숫자를 골라야합니다.

따라서 ans를 자신이 선택한 수(맨 오른쪽의 수)로 갱신하고 맨 오른쪽 포인터인 b를 한칸 땡겨 옵니다.

10번째 줄) 오른쪽의 숫자를 뽑아야하는데 그 숫자가 가장 최근에 뽑은 숫자보다 작으면 뽑을 수 없는 상황이기 때문에

그냥 턴(x)만 늘려주고 while문을 빠져나오게 됩니다.

 

26번째 줄) 양쪽 끝의 배열의 수가 서로 같으면

27번째 줄) 양쪽 끝의 증가수열의 갯수를 체크합니다. 왼쪽과 오른쪽의 증가수열이 모두 짝수이면 턴을 늘립니다.

 

30번째 줄) 모든 코드에서 break이 없으면 항상 턴(x)를 늘려줍니다.

 

32번째 줄) 턴(x)가 홀수이면 Bob의 승리입니다. 그게 아니면 Alice의 승리입니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll n, x, a, b, ans;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    vector<ll>v(n), A(n), B(n);
    for (int i = 0; i < n; i++)cin >> v[i];
    A[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--) {
        if (v[i] < v[i + 1])A[i] = A[i + 1] + 1;
        else A[i] = 1;
    }
    B[0] = 1;
    for (int i = 1; i < n; i++) {
        if (v[i] < v[i - 1])B[i] = B[i - 1] + 1;
        else B[i] = 1;
    }
    x = 0, a = 0, b = n - 1;
    ans = -1;
    while (1) {
        if (v[a] > v[b]) {
            if (A[a] & 1)break;
            else if (v[b] > ans) {
                ans = v[b];
                b--;
            }
            else {
                x++;
                break;
            }
        }
        else if (v[b] > v[a]) {
            if (B[b] & 1)break;
            else if (v[a] > ans) {
                ans = v[a];
                a++;
            }
            else {
                x++;
                break;
            }
        }
        else {
            if ((A[a] & 1) == 0 && (B[b] & 1) == 0)x++;
            break;
        }
        x++;
    }
    if (x & 1)cout << "Bob";
    else cout << "Alice";
    return 0;
}