Connected Grid States(グリッドの連結性を持つDPの状態遷移) (other/connected-grid-states.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-01 23:44:47+09:00
• Include: #include "other/connected-grid-states.hpp"

グリッドの連結性を持つDPの状態遷移を計算します。

それぞれの Union Find の状態に番号付けして、そのマスに ‘#’、’.’ を置くそれぞれの場合の遷移先の番号を $O(1)$ で求められるようにします。

コンストラクタ

ConnectedGridStates(int n)

横幅が n のグリッドの各連結状態について、状態遷移を前計算します。

制約

• $1 \leq n$

計算量

$n$ に対して指数オーダーです。状態数の合計を $s$ として $O(ns \log s)$ です。

$n \leq 11$ くらいが限度だと思います。

参考: 状態数の合計

1: 3
2: 11
3: 34
4: 102
5: 306
6: 914
7: 2722
8: 8080
9: 23929
10: 70747
11: 208944
12: 616706
13: 1819663

何も存在しない状態の番号は $0$ または $states[k].size - 1$ であることを保証します。

前者は過去に壁が存在したことがない、後者は過去に壁が存在したことがある状態を意味します。

set_wall

int set_wall(int k, int state)

$k$ 列目で状態 $state$ にいるときに、$k$ 列目のマスに壁を置いた場合の遷移先を返します。

制約

• $0 \leq k \lt n$
• $0 \leq state \lt states[k].size$

計算量

• $O(1)$

set_ground

int set_ground(int k, int state)

$k$ 列目で状態 $state$ にいるときに、$k$ 列目のマスに壁を置いた場合の遷移先を返します。

制約

• $0 \leq k \lt n$
• $0 \leq state \lt states[k].size$

計算量

• $O(1)$

operator []

operator [k]

$k$ 列目のすべての状態を返します。

$[k][state]$ とすることで、$k$ 列目の状態 $state$ の Union Find の状態を確認できます。

便宜的に $n \leq k \lt 2n$ を与えたとき、$k - n$ 列目のすべての状態を返します。

制約

• $0 \leq k \lt 2n$

計算量

• $O(1)$

Code

struct ConnectedGridStates {
 private:
  vector<vector<vector<int> > > states;
  vector<vector<int> > nxt_wall, nxt_ground;
  int width;

 public:
  explicit ConnectedGridStates(int width)
      : width(width), states(width), nxt_wall(width), nxt_ground(width) {
    assert(width > 0);

    auto modify = [&](vector<int> B) {
      vector<int> id(width, -1);
      int now = 0;
      for (int i = 0; i < width; i++) {
        if (B[i] != -1) {
          if (id[B[i]] == -1) {
            id[B[i]] = now++;
          }
          B[i] = id[B[i]];
        }
      }
      return B;
    };

    vector<map<vector<int>, int> > ids(width);
    queue<pair<int, int> > que;  // {col, state_id}

    {
      vector<int> state(width, -1);
      states[0].emplace_back(state);
      ids[0].emplace(state, 0);
      nxt_wall[0].emplace_back(-1);
      nxt_ground[0].emplace_back(-1);
      que.emplace(0, 0);
    }

    auto push = [&](int nxt, const vector<int> &state) -> int {
      auto it = ids[nxt].emplace(state, states[nxt].size());
      if (it.second) {
        states[nxt].emplace_back(state);
        nxt_wall[nxt].emplace_back(-1);
        nxt_ground[nxt].emplace_back(-1);
        que.emplace(nxt, it.first->second);
      }
      return it.first->second;
    };

    while (not que.empty()) {
      auto [i, id] = que.front();
      que.pop();
      int j = i + 1 == width ? 0 : i + 1;
      auto &state = states[i][id];
      int mx = *max_element(state.begin(), state.end());
      {  // '.'
        if (state[i] == -1) {
          nxt_ground[i][id] = push(j, state);
        } else {
          bool ok = false;
          for (int k = 0; k < width; k++) {
            ok |= i != k and state[k] == state[i];
          }
          if (ok) {
            auto to = state;
            to[i] = -1;
            nxt_ground[i][id] = push(j, modify(to));
          } else if (mx >= 1) {  // disconnected
            nxt_ground[i][id] = -1;
          } else {  // disappeared
            nxt_ground[i][id] = -2;
          }
        }
      }
      {  // '#'
        auto to = state;
        if (i == 0) {
          if (state[i] == -1) {
            to[i] = mx + 1;
          }
        } else {
          if (state[i] == -1) {
            if (state[i - 1] == -1) {
              to[i] = mx + 1;
            } else {
              to[i] = state[i - 1];
            }
          } else if (state[i - 1] != -1) {
            for (int k = 0; k < width; k++) {
              if (state[k] == state[i]) {
                to[k] = state[i - 1];
              }
            }
          }
        }
        nxt_wall[i][id] = push(j, modify(to));
      }
    }
    for (int i = 0; i < width; i++) {
      int j = i + 1 == width ? 0 : i + 1;
      int sz = (int)states[j].size();
      for (auto &k : nxt_ground[i]) {
        if (k == -2) k = sz;
      }
      for (auto &k : nxt_wall[i]) {
        if (k == -2) k = sz;
      }
      nxt_ground[i].emplace_back(sz);
      nxt_wall[i].emplace_back(-1);
    }
    for (int i = 0; i < width; i++) {
      states[i].emplace_back(width, -1);
    }
  }

  inline int set_wall(int k, int state) const { return nxt_wall[k][state]; }

  inline int set_ground(int k, int state) const { return nxt_ground[k][state]; }

  inline const vector<vector<int> > &operator[](int k) const {
    return states[k >= width ? k - width : k];
  }
};

#line 1 "other/connected-grid-states.hpp"
struct ConnectedGridStates {
 private:
  vector<vector<vector<int> > > states;
  vector<vector<int> > nxt_wall, nxt_ground;
  int width;

 public:
  explicit ConnectedGridStates(int width)
      : width(width), states(width), nxt_wall(width), nxt_ground(width) {
    assert(width > 0);

    auto modify = [&](vector<int> B) {
      vector<int> id(width, -1);
      int now = 0;
      for (int i = 0; i < width; i++) {
        if (B[i] != -1) {
          if (id[B[i]] == -1) {
            id[B[i]] = now++;
          }
          B[i] = id[B[i]];
        }
      }
      return B;
    };

    vector<map<vector<int>, int> > ids(width);
    queue<pair<int, int> > que;  // {col, state_id}

    {
      vector<int> state(width, -1);
      states[0].emplace_back(state);
      ids[0].emplace(state, 0);
      nxt_wall[0].emplace_back(-1);
      nxt_ground[0].emplace_back(-1);
      que.emplace(0, 0);
    }

    auto push = [&](int nxt, const vector<int> &state) -> int {
      auto it = ids[nxt].emplace(state, states[nxt].size());
      if (it.second) {
        states[nxt].emplace_back(state);
        nxt_wall[nxt].emplace_back(-1);
        nxt_ground[nxt].emplace_back(-1);
        que.emplace(nxt, it.first->second);
      }
      return it.first->second;
    };

    while (not que.empty()) {
      auto [i, id] = que.front();
      que.pop();
      int j = i + 1 == width ? 0 : i + 1;
      auto &state = states[i][id];
      int mx = *max_element(state.begin(), state.end());
      {  // '.'
        if (state[i] == -1) {
          nxt_ground[i][id] = push(j, state);
        } else {
          bool ok = false;
          for (int k = 0; k < width; k++) {
            ok |= i != k and state[k] == state[i];
          }
          if (ok) {
            auto to = state;
            to[i] = -1;
            nxt_ground[i][id] = push(j, modify(to));
          } else if (mx >= 1) {  // disconnected
            nxt_ground[i][id] = -1;
          } else {  // disappeared
            nxt_ground[i][id] = -2;
          }
        }
      }
      {  // '#'
        auto to = state;
        if (i == 0) {
          if (state[i] == -1) {
            to[i] = mx + 1;
          }
        } else {
          if (state[i] == -1) {
            if (state[i - 1] == -1) {
              to[i] = mx + 1;
            } else {
              to[i] = state[i - 1];
            }
          } else if (state[i - 1] != -1) {
            for (int k = 0; k < width; k++) {
              if (state[k] == state[i]) {
                to[k] = state[i - 1];
              }
            }
          }
        }
        nxt_wall[i][id] = push(j, modify(to));
      }
    }
    for (int i = 0; i < width; i++) {
      int j = i + 1 == width ? 0 : i + 1;
      int sz = (int)states[j].size();
      for (auto &k : nxt_ground[i]) {
        if (k == -2) k = sz;
      }
      for (auto &k : nxt_wall[i]) {
        if (k == -2) k = sz;
      }
      nxt_ground[i].emplace_back(sz);
      nxt_wall[i].emplace_back(-1);
    }
    for (int i = 0; i < width; i++) {
      states[i].emplace_back(width, -1);
    }
  }

  inline int set_wall(int k, int state) const { return nxt_wall[k][state]; }

  inline int set_ground(int k, int state) const { return nxt_ground[k][state]; }

  inline const vector<vector<int> > &operator[](int k) const {
    return states[k >= width ? k - width : k];
  }
};

Back to top page