dice

dice.cc

constexpr int dice_lines[][4] = {
  {2,3,5,4},
  {1,4,6,3},
  {1,2,6,5}
};

enum Face {
  U, D, L, R, F, B
};

struct Dice {
  int get_right(int u, int f) {
    if (u > 3) {
      return 7 - get_right(7 - u, f);
    }
    const int *line;
    if (u == 1) line = dice_lines[0];
    if (u == 2) line = dice_lines[1];
    if (u == 3) line = dice_lines[2];
    for (int i = 0; i < 4; ++i) {
      if (line[i] == f) return line[-~i % 4];
    }
    assert(false);
  }

  int up; int down;
  int left; int right;
  int front; int back;
  Dice (int u, int f) : up(u), front(f) {
    assert(1 <= u && u <= 6);
    assert(1 <= f && f <= 6);
    assert(u != f);
    assert(u + f != 7);
    right = get_right(u, f);
    left = 7 - right;
    down = 7 - up;
    back = 7 - front;
  }

  void roll(Face f) {
    if (f == U) return;
    if (f == D) return;

    if (f == R) { // roll to right
      int tmp = up;
      up = left;
      left = down;
      down = right;
      right = tmp;
    } else if (f == L) {
      int tmp = up;
      up = right;
      right = down;
      down = left;
      left = tmp;
    } else if (f == F) {
      int tmp = up;
      up = back;
      back = down;
      down = front;
      front = tmp;
    } else if (f == B) {
      int tmp = up;
      up = front;
      front = down;
      down = back;
      back = tmp;
    }
    assert(up + down == 7);
    assert(left + right == 7);
    assert(front + back == 7);
  }

};

ostream& operator<<(ostream& os, Dice d) {
  os << "(dice "
     << d.up << ' '
     << d.front << ' '
     << d.right << ' '
     << d.down << ' '
     << d.back << ' '
     << d.left << ")" << endl;
  return os;
}

例題

  • Biased Dice | AOJ
    • 回答例
代数
  • モノイド
    • Min/Max モノイド
    • Sum モノイド
  • (乗法)群と加法群
  • 環
  • 体
  • 加群
  • 有理数
  • 虚数
  • 行列
  • 超数
  • 全順序化
  • ModInt
  • 作用
    • 代入作用
    • 加算作用
グラフ

最短路

  • ダイクストラ法
  • ワーシャル-フロイド法
  • ベルマンフォード法

無向グラフ

  • 二部グラフ判定
  • 直径

最小全域木

  • プリム法
  • クラスカル法

木

  • 高さ
  • 直径
  • 最小共通祖先

有向グラフ

  • 最大流量
  • トポロジカルソート
  • 強連結成分分解
数列
  • 最長増加部分列
  • 中央値ヒープ
  • スライド最小値

累積処理

  • 一次元累積和
  • 二次元累積和

区間木

  • BIT
    • 累積和に関するBIT
  • セグメントツリー
    • RMQ
    • 加法セグメントツリー
    • 乗法セグメントツリー
  • 遅延セグメントツリー
    • 区間代入 RMQ
    • 区間加算 RMQ
    • 区間加算 加法セグメントツリー
二次元ユークリッド幾何

図形の定義

  • 点
  • 直線, 線分
  • 多角形
  • 円

線分

  • 線分と点の接触判定
  • 線分と線分の交差判定

多角形

  • 三角形の外接円
  • 多角形の内外判定
  • 凸包

円

  • 円と円との接触関係

最近点対

  • 平面上の分割統治法

その他

  • 極座標
  • Convex-Hull Trick (CHT)

格子点上の幾何

  • 点
  • 直線
集合
  • UnionFind
  • BitSet
  • 部分集合及びその部分集合の列挙
  • 多重集合
アルゴリズム

動的計画法

  • 01-ナップザック

二分探索

  • 二分探索

フーリエ変換

  • 畳み込み

循環検出

  • フロイドのρアルゴリズム

連立一次方程式

  • Gauss-Jordan の消去法
最適化
  • 燃やす埋める問題
自然数/整数

関数

  • GCD
  • 拡張GCD
  • 二項係数 (パスカルの三角形)
  • 二項係数 (ModInt)
  • 離散対数
  • 完全順列
  • オイラーの関数
  • メビウス関数
  • 自然数の対 ↔ 自然数 の変換
  • 最小自由数 (最小除外数)

素数

  • エラトステネスの篩
  • ミラー・ラビン素数判定
  • フェルマーの小定理
  • 素因数分解

その他定理

  • 中国人剰余定理

多倍長

  • ビッグエンディアンベクタ

組み合わせのイテレーター

  • 階乗 - n!
  • 冪乗 - nm
  • 二項係数 - nCm

乱数

  • 線形合同法
  • Xor-Shift 法
文字列 (Vector)
  • 接尾辞配列

文字列検索

  • Shift-And
  • Z-alogirhtm
  • 接尾辞配列による文字列検索

回文

  • manacher

圧縮

  • Run-length
時間/時刻
  • 制限時間付きループ

暦

  • ツェラーの公式
  • 閏年判定
ハッシュ
  • Zobrist Hash
  • Rolling Hash
collections
  • defaultmap
  • リスト内包表記マクロ
misc
  • k-means
  • 一般化15パズル
  • numeric sort
  • 乱択3-SAT
  • スターリングの近似式
  • サイコロ
  • 近傍
  • 2-SAT
  • 座標圧縮