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; } } }