ACM-ICPC 模擬国内予選 2013 E: 小野小町の編集合戦 [Licence: NYSL Version 0.9982]

Evaluator.java

public class Evaluator {
    private static final int RADIX = 10;
    private final Tokenizer tokenizer;

    public Evaluator(String s) {
        this.tokenizer = new Tokenizer(s);
    }

    public long evaluate() {
        try {
            final long ans = or();
            if(tokenizer.hasNext())
                return -Long.MAX_VALUE;
            return ans;
        } catch (ParsingException| TokenizingException e) {
            return -Long.MAX_VALUE;
        }
    }

    private long or() throws ParsingException, TokenizingException  {
        long ans = xor();
        while (tokenizer.hasNext() && tokenizer.nextType() == Tokenizer.TokenType.Operator
                && tokenizer.peek() == '|') {
            tokenizer.poll();
            ans |= xor();
        }
        return ans;
    }

    private long xor() throws ParsingException, TokenizingException  {
        long ans = and();
        while (tokenizer.hasNext() && tokenizer.nextType() == Tokenizer.TokenType.Operator
                && tokenizer.peek() == '^') {
            tokenizer.poll();
            ans ^= and();
        }
        return ans;
    }

    private long and() throws ParsingException, TokenizingException  {
        long ans = plusMinus();
        while (tokenizer.hasNext() && tokenizer.nextType() == Tokenizer.TokenType.Operator
                && tokenizer.peek() == '&') {
            tokenizer.poll();
            ans &= plusMinus();
        }
        return ans;
    }

    private long plusMinus() throws ParsingException, TokenizingException  {
        long ans = times();
        while (tokenizer.hasNext() && tokenizer.nextType() == Tokenizer.TokenType.Operator
                && (tokenizer.peek() == '+' || tokenizer.peek() == '-')) {
            if (tokenizer.poll() == '+')
                ans += times();
            else
                ans -= times();
        }
        return ans;
    }

    private long times() throws ParsingException, TokenizingException  {
        long ans = factor();
        while (tokenizer.hasNext() && tokenizer.nextType() == Tokenizer.TokenType.Operator
                && tokenizer.peek() == '*') {
            tokenizer.poll();
            ans *= factor();
        }
        return ans;
    }

    private long factor() throws ParsingException, TokenizingException {
        switch (tokenizer.nextType()) {
            case LeftParenthesis: {
                tokenizer.poll();
                final long ans = or();
                if (tokenizer.nextType() != Tokenizer.TokenType.RightParenthesis)
                    throw new ParsingException();
                tokenizer.poll();
                return ans;
            }
            case Number:
                return tokenizer.pollLong();
            default:
                throw new ParsingException();
        }
    }

    private static class ParsingException extends Exception {
        private ParsingException() {
        }

        private ParsingException(String message) {
            super(message);
        }

        private ParsingException(String message, Throwable cause) {
            super(message, cause);
        }

        private ParsingException(Throwable cause) {
            super(cause);
        }

        private ParsingException(String message, Throwable cause,
                                 boolean enableSuppression, boolean writableStackTrace) {
            super(message, cause, enableSuppression, writableStackTrace);
        }
    }

    private static class Tokenizer {
        private final char[] cs;
        private int cursor = 0;

        public Tokenizer(final String s) {
            cs = s.toCharArray();
        }

        public boolean hasNext() {
            return cursor < cs.length;
        }

        public TokenType nextType() throws TokenizingException {
            if(!hasNext())
                throw new TokenizingException();
            // except 0
            if ('0' < cs[cursor] && cs[cursor] <= '9')
                return TokenType.Number;
            switch (cs[cursor]) {
                case '+':
                case '-':
                case '*':
                case '&':
                case '^':
                case '|':
                    return TokenType.Operator;
                case '(':
                    return TokenType.LeftParenthesis;
                case ')':
                    return TokenType.RightParenthesis;
                default:
                    return TokenType.Invalid;
            }
        }

        public long pollLong()  throws TokenizingException {
            if(!hasNext())
                throw new TokenizingException();
            long ans = 0;
            while (cursor < cs.length && Character.isDigit(cs[cursor]))
                ans = ans * RADIX + cs[cursor++] - '0';
            return ans;
        }

        public char poll()  throws TokenizingException {
            if(!hasNext())
                throw new TokenizingException();
            return cs[cursor++];
        }

        public long peekLong()  throws TokenizingException {
            if(!hasNext())
                throw new TokenizingException();
            int tmp = cursor;
            long ans = 0;
            while (tmp < cs.length && Character.isDigit(cs[tmp]))
                ans = ans * RADIX + cs[tmp++] - '0';
            return ans;
        }

        public char peek()  throws TokenizingException {
            if(!hasNext())
                throw new TokenizingException();
            return cs[cursor];
        }

        public static enum TokenType {
            Number, Operator, LeftParenthesis, RightParenthesis, Invalid
        }
    }

    private static class TokenizingException extends Exception {
        private TokenizingException() {
        }

        private TokenizingException(String message) {
            super(message);
        }

        private TokenizingException(String message, Throwable cause) {
            super(message, cause);
        }

        private TokenizingException(Throwable cause) {
            super(cause);
        }

        private TokenizingException(String message, Throwable cause,
                                    boolean enableSuppression, boolean writableStackTrace) {
            super(message, cause, enableSuppression, writableStackTrace);
        }
    }
}

Main.java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    private static final char[] nums = "0123456789".toCharArray();
    private static final char[] opes = "+-*&^|".toCharArray();
    private static final Map<String, Long> cache = new HashMap<>();

    public static void main(String... args) {
        try (final Scanner sc = new Scanner(System.in)) {
            while (sc.hasNext()) {
                final int N = sc.nextInt();
                if (N == 0)
                    return;
                final String s = sc.next();
                final long ans = memoize(2 - (N & 1), s, 1);
                System.out.println(ans);
                cache.clear();
            }
        }
    }

    private static long memoize(final int N, final String s, final int sgn) {
        if (cache.containsKey(s))
            return cache.get(s);

        final long ret = solve(N, s, sgn);
        cache.put(s, ret);
        return ret;
    }

    private static long solve(final int N, final String s, final int sgn) {
        final String t = s.trim();
        final long v = evaluate(t);

        if (v == -Long.MAX_VALUE)
            return Long.MAX_VALUE;

        if (N == 0)
            return sgn * v;

        final int l = t.length();
        long max = -Long.MAX_VALUE;
        // insert
        for (int i = 0; i <= l; i++) {
            for (final char c : nums)
                max = Math.max(max, -memoize(N - 1, new StringBuilder(s).insert(i, c).toString(), -sgn));
            for (final char c : opes)
                max = Math.max(max, -memoize(N - 1, new StringBuilder(s).insert(i, c).toString(), -sgn));
        }
        // remove
        for (int i = 0; i < l; i++)
            if (s.charAt(i) != '(' && s.charAt(i) != ')')
                max = Math.max(max, -memoize(N - 1, s.substring(0, i) + s.substring(i + 1) + "  ", -sgn));

        return max;
    }

    private static long evaluate(final String s) {
        return new Evaluator(s).evaluate();
    }

    private static void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }
}