裏紙

ほぼ競プロ、たまに日記

CF 676 E - The Last Fight Between Human and AI

問題

Problem - E - Codeforces

問題概要

多項式 P(x) = a_n x^n + a_{n-1} x^{n-1} + ... + a_1 x +a_0が与えられる.初期状態ではこの多項式の係数a_i (0 \le i \le n)は全て未定になっている.

人間とAIがゲームをする.まずはじめに,ある整数kが与えられる.そして,AIが先手となりゲーム開始となる.ターンごとに,そのターンが回ってきたプレイヤーはまだ係数の決定していない係数の1つa_jを選択し,その係数の値を決定する(整数でも,実数でも良い).

これを繰り返していき,多項式P(x)が完成する.そして,その多項式P(x)Q(x) = x-kで割り切れる時には人間の勝ちであり,そうでないときはAIの勝ちである.

ゲームの途中経過の状態が与えられるので,ここから人間が適切に行動を選択することで確実に勝てるかを判定せよ.

  • 1 \le n \le 100000
  • -10000 \le k \le 10000
  •  a_i(0 \le i \le n)?なら未定,そうでなければ既に整数で決まっている(-10000 \le a_i \le 10000)

イデア

まず,既に決定されている係数の個数で次に行動するのが人間かAIかはわかる(奇数個なら人間,偶数個ならAI).

その上でk=0か否かで場合分けをして考えてみる.

(1)k=0のとき

この時は,つまりQ(x)=xで割り切れるかを聞いている.その可否は係数 a_0 (定数項)のみに依存するのが分かる.よって,既にa_0が決定されており,その値が0なら勝ち・違うなら負け,まだa_0が決定していないときは次に行動する方の勝ちになる.

(2)k \neq 0のとき

係数全体の状態がどうなっているかを考える.まず,既に係数が既に確定しているとき,P(x)Q(x)=x-kで割り切れるかどうか知りたいときはP(k)=0となるかを調べれば良い.

そうでないときには,最後に係数選択を行える方が勝てる.未定の係数が1つになった状態を考えてみる.その次数をiとする(a_i x^ia_iだけが未定という状態を考える).C_1 \displaystyle \sum_{j=0, j \neq i}^{n} a_j k^jとし,C_2 = k^i (\neq 0)とする.このようにしたときに,a_ia_i * C_2 = -C_1を満たすように選ぶことによって,必ずP(x)Q(x)で割り切れるように導く事ができるので,最後の係数を人間が選べる(多項式の次数が奇数)なら人間の勝ち,そうでなければ負ける.

最後に,P(k)=0の判定部分について言及しておく.基本的な多項式の計算方法についてはホーナー法のようにやっていく.問題はP(k)が非常に大きな値になりうるので,いつもただただ計算し続けるだけではオーバーフローが発生してしまう.これをある基準で打ち切ることにする.その打ち切り基準についてだが,最後にi=0になった状態を考えると,係数の大きさ的にこの時点で変数nowの絶対値が10^4以下でなければnow*k+a[0]は0になり得ない(なぜなら -10000 \le a_0 \le 10000だから).では,その手前のi=1の状態を考えてみると,係数a_1に関してもさっきと同じように制約があるので差分を考えるとこの時点でnowの絶対値は2*10^4以下になっていなければいけないということになる.これを同じようにたどっていき,多項式の次数n10^5以下なので,nowの絶対値はいかなる時も10^5 * 10^4以下になっていなければならないということになる.よってその値を超えてしまった時点で打ち切って構わない.

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const long UND = 123456;

inline ll ab(ll x)
{
    return (x>0?x:-x);
}

int main()
{
    int n,k;
    cin >>n >>k;

    //未定係数の数
    int ct=0;
    vector<long> a(n+1);
    rep(i,n+1)
    {
        string s;
        cin >>s;

        if(s=="?")
        {
            a[i]=UND;
            ++ct;
        }
        else a[i]=stol(s.c_str());
    }

    bool valid=true;
    //人間のターンか
    bool man=((n+1-ct)%2==1);

    if(k==0)
    {
        if(a[0]==UND) valid=man;
        else
        {
            if(a[0]==0) valid=true;
            else valid=false;
        }
    }
    else
    {
        //未定係数が無い時
        if(ct==0)
        {
            ll now=a[n];
            for(int i=n-1; i>=0; --i)
            {
                if(ab(now)>1000000000LL) break;
                now=now*k+a[i];
            }

            if(now==0) valid=true;
            else valid=false;
        }
        else valid=(n%2==1);
    }

    string ans="No";
    if(valid) ans="Yes";
    cout << ans << endl;

    return 0;
}