BOJ 26973 - Circular Barn (P3)

계절학교 시즌이 되기도 했고 해서 적당히 실력에 맞는 USACO 문제들을 풀어보려 한다.

tag

solved.ac 태그 : ad_hoc, dp, game_theory, math, number_theory, primality_test, sieve

작성자 풀이 태그 : (동일)

 

풀이

일단 n = 1인 게임부터 생각해보자. 여기서 중요한 사실은 소수인것도 있지만 1, 2, 3만큼 소를 뺄 수 있다는 점이다. 먼저 소가 4마리일 때 Nhoj가 이기고(4는 소수가 아님), 소가 4의 배수에서 4의 배수가 아니게 되었을 때, 4k + a(0 < a < 4)로 표현되므로 a = 1, 2, 3중 하나이고 결국 다시 4의 배수로 만들 수 있다. 결론은 4의 배수이면 쭉 Nhoj가 이긴다는 소리이다. 역으로 처음에 4의 배수가 아니었다면 바로 4의 배수로 만든 다음 같은 작업을 반복할 수 있으므로 John이 이긴다.

 

하지만 이 문제에서는 이러한 게임을 2턴씩 n개를 순서대로 진행한다. 그럼 각 게임은 독립적이므로 내가 이기는 게임의 경우 최대한 빨리 끝내고, 지는 게임의 경우 최대한 게임을 길게 진행하는 사악한(?) 전략을 생각할 수 있다. 우리는 n = 1일 때를 해결하면서 게임의 필승 방법이 어떤 식으로 진행되는지 알게 되었다. 그렇다면 실제로 케이스를 나누면서 게임이 어떻게 진행되는지 생각해보자.

 

우리가 알고 있는 사실은 4의 배수일 때 Nhoj가 이기고, 이 때 Nhoj는 계속 John의 동작에 따라 4의 배수로 만들어주어야 한다. 이 때 John이 게임을 최대한 늘리기 위해서 취해야 하는 동작은 무엇인가? 답은 소 2마리만 계속 빼는 것이다. 이는 짝수인 소수가 2뿐이라는 것에서 착안한 것인데, 이 경우 Nhoj는 4의 배수로 만들어주어야 하기 때문에 Nhoj는 할 수 있는 동작이 2밖에 없다. 즉 8 -> 6 -> 4 -> 2 -> 0처럼 2씩 줄이는 것이 최선이다.

 

만약 John이 2가 아닌 다른 수만큼 뺀다면, Nhoj는 적당한 홀수인 소수를 골라 2만 썼을 때보다 더 빠르게 수를 줄일 수 있다. 따라서 소가 4k마리일 때는 2k턴만에 끝난다. 같은 이유로, 4k+2마리로 시작했다면 John도 똑같은 전략을 취할 수 밖에 없기에 2k+1턴만에 끝난다. 이렇게 4로 나눈 나머지가 짝수인 경우를 모두 해결했다.

 

그렇다면 4로 나눈 나머지가 홀수인 경우는 어떨까? 이는 사실 앞서 생각한 경우와 거의 동일하다. 일단 처음에 소가 k마리(k%4는 홀수)라 하자.

일단 John이 이기는데, John은 바로 4의 배수로 만들어야 하기 때문에 John이 고를 수 있는 소수 p(p=1 포함)는 p mod 4 = k mod 4를 만족해야 한다. 이 경우 k := k-p가 되어 k가 4의 배수가 되므로 앞에서 말한 전략과 동일하게 (k-p)/2턴만에 끝나게 된다. 결국 처음에 고르는 소수가 중요한데, 자명하게 최대한 큰 p를 골라줘야 한다. 이렇게 가장 큰 p를 골랐을 때 답은 1 + (k-p)/2가 된다. 이렇게 4로 나눈 나머지가 홀수인 경우를 해결할 수 있다.

 

이제 전체 문제를 해결하자. 이제 우리는 각 게임이 몇 턴만에 끝나는지 알고 있으므로, 순서대로 진행했을 때 가장 빨리 끝나는 게임에서 누가 이기는 지를 판별해주면 된다. 이 때 한 번에 2턴씩 진행한다는 것에 유의하여 계산하자.

 

코드

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef __int128_t lll;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
#define sz(x) (ll)x.size()
ll dp[5050505];
vector<ll> p[4];
bool sieve[5050505]={1,1};
int main(){
    fast;
    p[1].push_back(1);
    for(ll i = 2 ; i <= 5050500 ; i++){
        if(!sieve[i]){
            p[i%4].push_back(i);
            for(ll j = i*i ; j <= 5050500 ; j+=i)sieve[j] = 1;
        }
    }
    dp[0] = 0;
    for(int i = 1 ; i <= 5000000 ; i++){
        if(i%4 == 0 or i%4 == 2)dp[i] = i/2;
        else{
            auto it = --upper_bound(all(p[i%4]), i);
            dp[i] = 1 + (i - *it) / 2;
        }
    }
    ll t; cin>>t; while(t--){
        ll n; cin>>n;
        vector<ll> v(n);
        P john = {1e18, 0}, nhoj = {1e18, 0};
        for(int i = 0 ; i < n ; i++){
            ll a; cin>>a;
            if(a%4 == 0)nhoj = min(nhoj, P((dp[a]+2)/2, i));
            else john = min(john, P((dp[a]+1)/2, i));
        }
        cout<<(john < nhoj ? "Farmer John\n" : "Farmer Nhoj\n");
    }
}

 

여담)게임 이론들은 풀이를 쓰는 것이 쉽지 않다..