cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub rniya/cp-library

:heavy_check_mark: Dice
(src/util/Dice.hpp)

概要

サイコロを扱うライブラリ. 主に ICPC 国内予選用.

サイコロは隣接する 2 面の情報が与えられれば各面の数字の情報は一意に定まる.

実装においては面に 0 から 5 の番号をつけ, それぞれ上面, 前面, 右面, 左面, 背面, 底面に対応させている. また, roll や rollc での回転方向については,

となっている.

メンバ関数 効果 時間計算量
Dice(TOP, FRONT) 上面の数字 TOP と 前面の数字 FRONT から適切なサイコロを構築する. $O(1)$
Dice(v) 上面, 前面, 右面, 左面, 背面, 底面の順に数が詰まった配列 v からサイコロを構築する. $O(1)$
top() 上面に書かれた数字を返す. $O(1)$
front() 前面に書かれた数字を返す. $O(1)$
right() 右面に書かれた数字を返す. $O(1)$
left() 左面に書かれた数字を返す. $O(1)$
back() 背面に書かれた数字を返す. $O(1)$
bottom() 底面に書かれた数字を返す. $O(1)$
operator[k] 対応する番号の面に書かれた数字を返す. $O(1)$
roll(k) 対応する番号の方向にサイコロを移動させる. $O(1)$
rollc(c) 移動方向を文字で指定して実行する. $O(1)$
hash() サイコロの hash 値を計算して返す. $O(1)$
make_all() サイコロを自由に転がすことで有り得る全状態を返す. これは合計で 24 個存在する. $O(1)$
identifier() サイコロを自由に転がすことでできる面に書かれた数字についての辞書順最小のサイコロを返す. 2 つのサイコロが同型かどうかの判定の際などに用いる. $O(1)$

Verified with

Code

#pragma once
#include <algorithm>
#include <array>
#include <cassert>
#include <string>
#include <vector>

struct Dice {
    std::array<int, 6> surface;

    Dice(int TOP = 1, int FRONT = 2) {
        assert(1 <= TOP and TOP <= 6);
        assert(1 <= FRONT and FRONT <= 6);
        assert(TOP + FRONT != 7);
        surface[0] = TOP;
        surface[1] = FRONT;
        surface[2] = dice[TOP - 1][FRONT - 1];
        surface[3] = 7 - surface[2];
        surface[4] = 7 - surface[1];
        surface[5] = 7 - surface[0];
    }

    Dice(const std::vector<int>& v) {
        assert(v.size() == 6);
        for (size_t i = 0; i < 6; i++) surface[i] = v[i];
    }

    const int& top() const { return surface[0]; }
    const int& front() const { return surface[1]; }
    const int& right() const { return surface[2]; }
    const int& left() const { return surface[3]; }
    const int& back() const { return surface[4]; }
    const int& bottom() const { return surface[5]; }
    const int& operator[](int k) const { return surface[k]; }

    int& top() { return surface[0]; }
    int& front() { return surface[1]; }
    int& right() { return surface[2]; }
    int& left() { return surface[3]; }
    int& back() { return surface[4]; }
    int& bottom() { return surface[5]; }
    int& operator[](int k) { return surface[k]; }

    bool operator==(const Dice& d) const { return surface == d.surface; }
    bool operator!=(const Dice& d) const { return surface != d.surface; }
    bool operator<(const Dice& d) const { return surface < d.surface; }

    int roll(int k) {  // x++, x--, y++, y--, turn right, turn left
        assert(0 <= k and k < 6);
        int tmp = surface[code[k][0]];
        for (int i = 0; i < 3; i++) surface[code[k][i]] = surface[code[k][i + 1]];
        surface[code[k][3]] = tmp;
        return surface[0];
    }

    int rollc(char c) {
        for (int k = 0; k < 6; k++) {
            if (direction[k] != c) continue;
            return roll(k);
        }
        assert(false);
    }

    int hash() const {
        int res = 0;
        for (size_t i = 0; i < 6; i++) {
            assert(1 <= surface[i] and surface[i] <= 6);
            (res *= 6) += surface[i] - 1;
        }
        return res;
    }

    std::vector<Dice> make_all() {
        std::vector<Dice> res;
        for (int i = 0; i < 6; i++) {
            Dice d(*this);
            if (i == 1) d.roll(2);
            if (i == 2) d.roll(3);
            if (i == 3) d.roll(3), d.roll(3);
            if (i == 4) d.roll(5);
            if (i == 5) d.roll(4);
            for (int j = 0; j < 4; j++) {
                res.emplace_back(d);
                d.roll(0);
            }
        }
        return res;
    }

    Dice identifier() {
        auto dices = make_all();
        return *std::min_element(dices.begin(), dices.end());
    }

private:
    const int dice[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}};
    const int code[6][4] = {{0, 3, 5, 2}, {0, 2, 5, 3}, {0, 1, 5, 4}, {0, 4, 5, 1}, {1, 2, 4, 3}, {1, 3, 4, 2}};
    const char direction[6] = {'E', 'W', 'N', 'S', 'R', 'L'};
};
#line 2 "src/util/Dice.hpp"
#include <algorithm>
#include <array>
#include <cassert>
#include <string>
#include <vector>

struct Dice {
    std::array<int, 6> surface;

    Dice(int TOP = 1, int FRONT = 2) {
        assert(1 <= TOP and TOP <= 6);
        assert(1 <= FRONT and FRONT <= 6);
        assert(TOP + FRONT != 7);
        surface[0] = TOP;
        surface[1] = FRONT;
        surface[2] = dice[TOP - 1][FRONT - 1];
        surface[3] = 7 - surface[2];
        surface[4] = 7 - surface[1];
        surface[5] = 7 - surface[0];
    }

    Dice(const std::vector<int>& v) {
        assert(v.size() == 6);
        for (size_t i = 0; i < 6; i++) surface[i] = v[i];
    }

    const int& top() const { return surface[0]; }
    const int& front() const { return surface[1]; }
    const int& right() const { return surface[2]; }
    const int& left() const { return surface[3]; }
    const int& back() const { return surface[4]; }
    const int& bottom() const { return surface[5]; }
    const int& operator[](int k) const { return surface[k]; }

    int& top() { return surface[0]; }
    int& front() { return surface[1]; }
    int& right() { return surface[2]; }
    int& left() { return surface[3]; }
    int& back() { return surface[4]; }
    int& bottom() { return surface[5]; }
    int& operator[](int k) { return surface[k]; }

    bool operator==(const Dice& d) const { return surface == d.surface; }
    bool operator!=(const Dice& d) const { return surface != d.surface; }
    bool operator<(const Dice& d) const { return surface < d.surface; }

    int roll(int k) {  // x++, x--, y++, y--, turn right, turn left
        assert(0 <= k and k < 6);
        int tmp = surface[code[k][0]];
        for (int i = 0; i < 3; i++) surface[code[k][i]] = surface[code[k][i + 1]];
        surface[code[k][3]] = tmp;
        return surface[0];
    }

    int rollc(char c) {
        for (int k = 0; k < 6; k++) {
            if (direction[k] != c) continue;
            return roll(k);
        }
        assert(false);
    }

    int hash() const {
        int res = 0;
        for (size_t i = 0; i < 6; i++) {
            assert(1 <= surface[i] and surface[i] <= 6);
            (res *= 6) += surface[i] - 1;
        }
        return res;
    }

    std::vector<Dice> make_all() {
        std::vector<Dice> res;
        for (int i = 0; i < 6; i++) {
            Dice d(*this);
            if (i == 1) d.roll(2);
            if (i == 2) d.roll(3);
            if (i == 3) d.roll(3), d.roll(3);
            if (i == 4) d.roll(5);
            if (i == 5) d.roll(4);
            for (int j = 0; j < 4; j++) {
                res.emplace_back(d);
                d.roll(0);
            }
        }
        return res;
    }

    Dice identifier() {
        auto dices = make_all();
        return *std::min_element(dices.begin(), dices.end());
    }

private:
    const int dice[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}};
    const int code[6][4] = {{0, 3, 5, 2}, {0, 2, 5, 3}, {0, 1, 5, 4}, {0, 4, 5, 1}, {1, 2, 4, 3}, {1, 3, 4, 2}};
    const char direction[6] = {'E', 'W', 'N', 'S', 'R', 'L'};
};
Back to top page