模擬国内予選 E.サイコロスタンプ

ACM-ICPCの模擬国内予選に参加しました。チーム(@haraduka_, @garasubo, @mayoko_)としてはA, B, Dの3問を解いてなるほど。といった感じでした。以前1年分やった感じでは4完はできると思っていたのでちょっと悲しいです。

しかも僕が担当して解かれた問題は一問もないという…　本番頑張ります…

一応Eを担当して解法はまとまっていたのでそれを紹介します。C, Dも自力で解けるようになりたいですね。Fからは自力で解けないのは仕方ないと思っています。

解法

以下のソースコードはAOJで出すとTLEしそうなことをお断りしておきます。

この問題はbitDPで解くことができます。状態としてはdp[state] := (1～nのうちstateで表される状態のサイコロだけ投げたとき最高で何点取ることができるか,およびその時のサイコロの目がどのように構成されるか)を考えます。

すると,ある状態sからさらに一つのサイコロiを投げた場合の状態nsは,「まず,サイコロiを投げてからdp[s]になるように状態sを構成するサイコロを投げる」と考えて更新することができます。

struct Point {
    int x;
    int y;
    Point() {}
    Point(int x, int y) : x(x), y(y) {}
    bool operator<(const Point& rhs) const {
        if (x != rhs.x) return x < rhs.x;
        else return y < rhs.y;
    }
    bool operator==(const Point& rhs) const {
        return x == rhs.x && y == rhs.y;
    }
};

struct Dice {
    int up, down, front, back, left, right;
    Point now;
    Dice() {}
    void move(char dir, map<Point, int>& S) {
        S[Point(now.x, now.y)] = down;
        int tup = up, tdown = down, tfront = front, tback = back, tleft = left, tright = right;
        if (dir == 'L') {
            up = tright;
            right = tdown;
            left = tup;
            down = tleft;
            now.x--;
        } else if (dir == 'B') {
            up = tfront;
            front = tdown;
            down = tback;
            back = tup;
            now.y++;
        } else if (dir == 'R') {
            up = tleft;
            right = tup;
            left = tdown;
            down = tright;
            now.x++;
        } else {
            up = tback;
            front = tup;
            back = tdown;
            down = tfront;
            now.y--;
        }
        S[Point(now.x, now.y)] = down;
    }
};

const int MAXN = 16;
int x[MAXN], y[MAXN];
map<Point, int> memo[MAXN];
map<Point, int> dp[1<<MAXN];
int dpmemo[1<<MAXN];

void solve(int n) {
    for (int i = 0; i < n; i++) {
        Dice dice;
        cin >> dice.now.x >> dice.now.y;
        cin >> dice.left >> dice.right >> dice.front >> dice.back >> dice.down >> dice.up;
        string s;
        cin >> s;
        map<Point, int> S;
        for (char c : s) {
            dice.move(c, S);
        }
        memo[i] = S;
        //for (auto el : S) {
        //    cout << el.first.x << "  " << el.first.y << "  " << el.second << endl;
        //}
    }
    for (int i = 0; i < (1<<n); i++) {
        dp[i].clear();
        dpmemo[i] = 0;
    }
    for (int s = 0; s < (1<<n)-1; s++) {
        for (int i = 0; i < n; i++) {
            if ((s>>i)&1) continue;
            int ns = (s | (1<<i));
            map<Point, int> S = memo[i];
            for (auto el : dp[s]) {
                S[el.first] = (el.second);
            }
            int tmp = 0;
            for (auto el : S) {
                tmp += el.second;
            }
            if (tmp > dpmemo[ns]) {
                dpmemo[ns] = tmp;
                dp[ns] = S;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < (1<<n); i++) {
        ans = max(ans, dpmemo[i]);
    }
    cout << ans << endl;
}

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        solve(n);
    }
    return 0;
}