AOJ 1181: 偏りのあるサイコロ / Biased Dice

サイコロライブラリがあればすぐだった。

solution

問題文通りに実装するだけ。$O(n \sqrt{n})$だと思う。

implementation

#include <array>
#include <cassert>
#include <cstdio>
#include <map>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

struct dice_t { // regular hexahedron group
    //       ______
    //      \      \      4
    //     / \   C  \    2156
    //    / A \______\    3 ^
    //    \ A /    B /   ^^ |
    //     \ /   B  /    ab bottom
    //      v__B___/
    int a, b; // in [1, 6]
    int c() const {
        static const int table[6][6] = {
            { 0, 3, 5, 2, 4, 0 },
            { 4, 0, 1, 6, 0, 3 },
            { 2, 6, 0, 0, 1, 5 },
            { 5, 1, 0, 0, 6, 2 },
            { 3, 0, 6, 1, 0, 4 },
            { 0, 4, 2, 5, 3, 0 },
        };
        assert (table[a-1][b-1] != 0);
        return  table[a-1][b-1];
    }
};
dice_t rotate_up(   dice_t dice) { return (dice_t) { dice.a, 7 - dice.c() }; }
dice_t rotate_right(dice_t dice) { return (dice_t) { 7 - dice.c(), dice.b }; }
dice_t rotate_down( dice_t dice) { return (dice_t) { dice.a, dice.c() }; }
dice_t rotate_left( dice_t dice) { return (dice_t) { dice.c(), dice.b }; }
bool operator == (dice_t x, dice_t y) { return x.a == y.a and x.b == y.b; }

const int dy[4] = { 1, -1, 0, 0 };
const int dx[4] = { 0, 0, 1, -1 };
int main() {
    while (true) {
        int n; scanf("%d", &n);
        if (n == 0) break;
        map<pair<int, int>, int> rank;
        map<pair<int, int>, int> value;
        while (n --) {
            int c, b; scanf("%d%d", &c, &b);
            dice_t dice = rotate_right((dice_t) { c, b });
            int y = 0;
            int x = 0;
            while (true) {
                int dir = -1;
                int num = -1;
                auto update = [&](int d, int n) {
                    if (not (n == 4 or n == 5 or n == 6)) return;
                    int ny = y + dy[d];
                    int nx = x + dx[d];
                    if (rank[make_pair(ny, nx)] >= rank[make_pair(y, x)]) return;
                    if (num < n) {
                        dir = d;
                        num = n;
                    }
                };
                update(0, 7 - dice.b);
                update(1, dice.b);
                update(2, 7 - dice.a);
                update(3, dice.a);
                if (dir == -1) break;
                y += dy[dir];
                x += dx[dir];
                dice =
                    dir == 0 ? rotate_up(dice) :
                    dir == 1 ? rotate_down(dice) :
                    dir == 2 ? rotate_right(dice) :
                               rotate_left(dice);
            }
            rank[make_pair(y, x)] += 1;
            value[make_pair(y, x)] = dice.c();
        }
        array<int, 6> result = {};
        for (auto it : value) {
            result[it.second - 1] += 1;
        }
        repeat (i, 6) {
            printf("%d%c", result[i], i + 1 < 6 ? ' ' : '\n');
        }
    }
    return 0;
}