非不偏版エンドニム

輪講メモ。

[参考元]

組合せゲーム理論入門 ?勝利の方程式?

非不偏版エンドニムはエンドニムの変形。

エンドニムとは、一列に並ぶ箱の山が与えられて、対局者はどちらか一方の端にある箱の山から好きな数だけ箱を取り除くことができる。
端にある箱の山が取り除かれたら、その隣にある山から箱を取り除くことができる。
最後の箱を取り除いた対局者の勝ち。

非不偏版エンドニムは、上のエンドニムに、左は左端の山から箱を取り除く、右は右端の箱の山から箱を取り除くという条件を付したもの。
左、右は対局者の取りうる選択肢が異なるので、対局者を区別するために呼ぶ。

入力形式

複数のデータセットの並びが入力として与える。
入力の終わりはゼロひとつの行で示される。
各データセットは以下の通り。

１行目 箱の山の個数 n (整数)
２行目 左端から１番目の山の箱の個数　左端から２番目の山の箱の個数　・・・　左端からn番目の山の箱の個数

出力形式

入力データセットごとに与えられた初期局面の帰結類。

帰結類とは次の４つの状態
・L 左必勝
・R 右必勝
・N 先手必勝
・P 後手必勝

#include <iostream>
#include <climits>

using namespace std;

const int MX_SIZE = 1000;
int inp[MX_SIZE];
int memo_l[MX_SIZE][MX_SIZE], memo_r[MX_SIZE][MX_SIZE];
int n;

int right_aw(int l, int r);
int left_wb(int l, int r);
void init();

void init()
{
    for (int i = 0; i < n; i++) 
        cin >> inp[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            memo_l[i][j] = memo_r[i][j] = INT_MAX;
}


int right_aw(int l, int r)
{
    if (memo_r[l][r] != INT_MAX)
        return memo_r[l][r];

    int ret;
    if (r - l == 0) 
            ret = inp[r];
    else {
        if (inp[l] <= left_wb(l + 1, r))
            ret = 0;
        else {
            ret = right_aw(l + 1, r) - left_wb(l + 1, r) + inp[l];
        
            if (ret < 0)
                ret = 0;
        }
    }
    
    return memo_r[l][r] = ret;
}


int left_wb(int l, int r)
{
    if (memo_l[l][r] != INT_MAX)
        return memo_l[l][r];

    int ret;
    if (r - l == 0) 
        ret = inp[r];
    else {
        if (inp[r] <= right_aw(l, r - 1))
            ret = 0;
        else {
            ret = left_wb(l, r - 1) - right_aw(l, r - 1) + inp[r];

            if (ret < 0)
                ret = 0;
        }
    }

    return memo_l[l][r] = ret;
}


int main()
{
    while (cin >> n, n) {
        int lw, rw;

        init();

        if (n <= 3) {
            rw = right_aw(0, n - 1);
            lw = left_wb(0, n - 1);
        }
        else {
            rw = right_aw(1, n - 2);
            lw = left_wb(1, n - 2);
        }

        if (inp[0] <= lw && inp[n - 1] <= rw)
            cout << "N: 先手必勝" << endl;
        else if (inp[0] > lw && inp[n - 1] > rw)
            cout << "P: 後手必勝" << endl;
        else if (inp[0] > lw && inp[n - 1] <= rw)
            cout << "L: 左必勝" << endl;
        else if (inp[0] <= lw && inp[n - 1] > rw)
            cout << "R: 右必勝" << endl;
        else
            cout << "分からない" << endl;
    }

    return 0;
}