AOJ 2512 Ononokomachi's Edit War

解法

適当に置換 or 削除でminimax法だと明らかに間に合わないので,すこし考える必要がある.
冷静に考えると,N が偶数のときは2ターン,N が奇数のときは1ターンやるのと変わらないことが分かる.
大まかには以下のように考えた.

  • 任意に削除,挿入が可能なので,直前の手番をキャンセルさせることが可能
  • minimax法の要領で,先手は遷移先でもっとも良いものを選ぼうとする
  • 最終的に有利な手が選ばれるのだから,後手としてはキャンセルするほうがよい
  • つまり結局,お互いに最後だけを考えればよい(もちろん最後の手がキャンセルでもよい)

高々 N = 2 と言っているのと同じなので,挿入,削除に関して全通り試しても十分間に合う.
毎回の操作で式として成り立っている必要が有ることに注意.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
constexpr int INF = 1e9;
 
int expr(string const& s, int& p);
int Or(string const& s, int& p);
int Xor(string const& s, int& p);
int And(string const& s, int& p);
int Plus(string const& s, int& p);
int term(string const& s, int& p);
int factor(string const& s, int& p);
int number(string const& s, int& p);
 
int expr(string const& s, int& p) {
    return Or(s, p);
}
 
int Or(string const& s, int& p) {
    int res = Xor(s, p);
    while(p < s.size() && s[p] == '|') {
        res |= Xor(s, ++p);
    }
    return res;
}
 
int Xor(string const& s, int& p) {
    int res = And(s, p);
    while(p < s.size() && s[p] == '^') {
        res ^= And(s, ++p);
    }
    return res;
}
 
int And(string const& s, int& p) {
    int res = Plus(s, p);
    while(p < s.size() && s[p] == '&') {
        res &= Plus(s, ++p);
    }
    return res;
}
 
int Plus(string const& s, int& p) {
    int res = term(s, p);
    while(p < s.size() && (s[p] == '+' || s[p] == '-')) {
        char op = s[p++];
        if(op == '+') {
            res += term(s, p);
        } else {
            res -= term(s, p);
        }
    }
    return res;
}
 
int term(string const& s, int& p) {
    int res = factor(s, p);
    while(p < s.size() && s[p] == '*') {
        res *= factor(s, ++p);
    }
    return res;
}
 
int factor(string const& s, int& p) {
    if(isdigit(s[p])) {
        if(s[p] == '0') {
            throw runtime_error("");
        }
        return number(s, p);
    }
    if(s[p] == '(') {
        int res = expr(s, ++p);
        ++p;
        return res;
    }
    throw runtime_error("");
}
 
int number(string const& s, int& p) {
    int res = 0;
    while(p < s.size() && isdigit(s[p])) {
        res *= 10;
        res += s[p++] - '0';
    }
    return res;
}
 
 
string pattern = "0123456789*+-&^|";
 
int parse(string const& s) {
    try {
        int p = 0;
        int t = expr(s, p);
        if(p != s.size()) {
            return INF;
        }
        return t;
    } catch(...) {
        return INF;
    }
}
 
int solve(string s, int cnt, int turn) {
    if(cnt == 0) {
        return parse(s);
    }
    int res = (turn == 0 ? -INF : INF);
    // erase
    for(int i=0; i<s.size(); ++i) {
        string t = s;
        t.erase(t.begin()+i);
        if(t.size() == 0 || INF == parse(t)) {
            continue;
        }
        int tmp = solve(t, cnt-1, turn^1);
        if(tmp == INF) {
            continue;
        }
        if(turn == 0) {
            res = max(res, tmp);
        } else {
            res = min(res, tmp);
        }
    }
 
    // insert
    for(int i=0; i<pattern.size(); ++i) {
        for(int j=0; j<=s.size(); ++j) {
            string t = s;
            t.insert(t.begin()+j, pattern[i]);
            if(INF == parse(t)) {
                continue;
            }
            int tmp = solve(t, cnt-1, turn^1);
            if(tmp == INF) {
                continue;
            }
            if(turn == 0) {
                res = max(res, tmp);
            } else {
                res = min(res, tmp);
            }
        }
         
    }
    return res;
}
 
 
int main() {
    int n;
    string s;
    while(cin >> n >> s, n) {
        if(n & 1) {
            cout << solve(s, 1, 0) << endl;
        } else {
            cout << solve(s, 2, 0) << endl;
        }
    }
}