日々drdrする人のメモ

今日も明日もdrdr

CodeChef July Challenge 2019: Snake and Apple Tree

CodeChef July Challenge 2019 の問題: Snake and Apple Tree (Code: CNKAPT)
問題ページ: Contest Page | CodeChef

問題概要

 N \times M の二次元盤面があり、各マスは空もしくは壁で構成される。
この盤面には  S 匹のヘビが存在する。

各ヘビは T秒間の間、各秒ごとに以下のいずれかの行動ができる。

  • 上下左右のマスに移動
  • 何もしない
  • りんごの木の実を1個食べる (複数の木がマスに存在しても高々1個のみ食べられる)

各秒ごとに1つのマスには高々1匹しか存在できない。

この盤面には  Z 本のりんごの木が生えて枯れる。
 i 番目の木は  P_i秒目に 座標 (X_i, Y_i)に生えて、  Q_i秒目に枯れる。

 i番目の木の実をヘビが1個食べた時、 H_i のhapinessが得られる。
(木が生えている間は、各秒ごとに1個ずつ食べられる)

 T秒間の行動で、各ヘビが得られるhapinessの総和の最大値を求めよ。

制約

  •  1 \le S \le 25
  •  1 \le N, M \le 256
  •  1 \le N \times M \le 256
  •  1 \le Z \le 5000
  •  1 \le T \le 80
  •  0 \le P_i < Q_i \le T
  •  1 \le H_i \le 10^6

解法

制約的にフローを流したい気持ちになる問題。

まず、以下のように問題を言い換える。

盤面上に S匹のヘビが存在する。

各ヘビは T秒間の間、各秒ごとに以下の行動ができる。( U = \max_i(H_i) とする)

  • 上下左右のマスに移動
    •  Uのhapinessを失う
  • 何もしない
    •  Uのhapinessを失う
  • 生えている i番目のりんごの木の実を食べる
    •  U - H_i のhapinessを失う

 T 秒間の行動で、各ヘビのhapinessの損失の総和の最小値を求めよ。

利益の最大値の代わりに損失の最小値を考えることで、最小費用流の問題としてグラフに落として解くことができる。

グラフは以下のように構築する。

  • 各時間(時間0から時間Tまで)の各マスごとに頂点を用意する
    • 同時刻に各マスにヘビが高々1匹という制約を満たすために、各時間の各マスを2頂点(入頂点、出頂点)に分け、入頂点から出頂点に容量1、コスト0の辺を張る
  • ヘビがいる S個のマスについて、sourceから時刻0の該当マスの入頂点に容量1、コスト0の辺を張る
  • 各時間の全てのマスの出頂点から次の時間の移動先のマスの入頂点に以下のように張る (壁へは張らない)
    • 上下左右の移動: 容量1、コスト U
    • 木がある場合 -> 木の実を食べる: 容量1、コスト U - H_i
    • 木がない場合 -> 何もしない: 容量1、コスト U
  • 時刻Tの各マスの出頂点からsinkに容量1、コスト0の辺を張る

(公式解法では  U = 0 で構築してた。これは負閉路が含まれないから確かにという気持ちになった)


例えば、1×3の盤面(全てのempty cell)において

  • (1, 1) にヘビ
  • (1, 1) に H_i = 4,  (P_i, Q_i) = (1, 3) の木が生える
  • (1, 2) に H_i = 9,  (P_i, Q_i) = (2, 3) の木が生える
  •  T = 2

という状況を考えてみる。(この最適解は(1, 2)に移動 ->  H_i = 9 の実を食べる、である)

 U = 10 と考えた場合、グラフは以下の図のようになる。
張られた辺全ての容量は1とし、黒い辺のコストは0、青い辺のコストは10、赤い辺のコストは  U - H_i とする。

f:id:smijake3:20190717005230p:plain
構築されるグラフの例

このような感じで頂点数・辺数  O(NMT)のグラフとして構築できる。
このグラフの流量 Sの最小費用流を求めることで、この問題の解が求まる。

実装

計算量は  O(S N M T \log(N M T))

提出コード(C++14): Solution: 25149516 | CodeChef

#define N 270
#define S 30
#define T 83

// 最小費用流
#define MAX_N 50000
class MinCostFlow {
  static const ll inf = 1e18;
  struct Edge {
    int to, cap, cost;
    size_t rev;
  };

  vector<Edge> g[MAX_N];
  int h[MAX_N];
  int prv_v[MAX_N], prv_e[MAX_N];
  ll dist[MAX_N];
  int n;

public:
  MinCostFlow(int n) : n(n) {}

  void add_edge(int fr, int to, int cap, int cost) {
    g[fr].emplace_back(Edge{to, cap, cost, g[to].size()});
    g[to].emplace_back(Edge{fr, 0, -cost, g[fr].size()-1});
  }

  ll flow(int s, int t, ll f) {
    ll res = 0;
    for(int i=0; i<n; ++i) h[i] = prv_v[i] = prv_e[i] = 0;

    while(f) {
      for(int i=0; i<n; ++i) dist[i] = inf;
      dist[s] = 0;

      priority_queue<P, vector<P>, greater<P> > que;
      que.push(P(0, s));
      while(!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if(dist[v] < p.first) continue;

        for(int i=0; i<g[v].size(); ++i) {
          Edge &e = g[v][i];
          if(e.cap > 0 && dist[v] + e.cost + h[v] - h[e.to] < dist[e.to]) {
            dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
            prv_v[e.to] = v; prv_e[e.to] = i;
            que.push(P(dist[e.to], e.to));
          }
        }
      }
      if(dist[t] == inf) {
        return -1;
      }
      for(int i=0; i<n; ++i) h[i] += dist[i];

      ll d = f;
      int v = t;
      while(v != s) {
        d = min(d, (ll) g[prv_v[v]][prv_e[v]].cap);
        v = prv_v[v];
      }
      f -= d;
      res += d * h[t];
      v = t;
      while(v != s) {
        Edge &e = g[prv_v[v]][prv_e[v]];
        e.cap -= d;
        g[v][e.rev].cap += d;
        v = prv_v[v];
      }
    }
    return res;
  }
};

char mp[N][N];

int n, m, z, t;
int sn;
int sx[S], sy[S];
int apple[T][N][N];

int main() {
  cin >> n >> m >> z >> t;
  rep(i, n) {
    cin >> mp[i];
    rep(j, m) {
      if(mp[i][j] == 'S') {
        sx[sn] = i; sy[sn] = j;
        ++sn;
      }
    }
  }

  int base = n*m*(t+1);
  int n0 = base*2;
  const int bloss = 1000000;
  MinCostFlow mct(n0+2);

  // 各マスに生える木の情報の計算
  rep(j, z) {
    int x, y, p, q, h;
    cin >> x >> y >> p >> q >> h;
    repl(i, p, q-1) {
      // 各マスには、同時刻のうちhapinessが最も高い木のみが生えていると考えてよい
      apple[i][x-1][y-1] = max(apple[i][x-1][y-1], h);
    }
  }
  // (i, j, k) の入頂点 -> (i, j, k) の出頂点 (容量1)
  // 各秒では各マスに高々1匹しか存在できない制約のために必要
  rep(k, t+1) {
    rep(i, n) rep(j, m) {
      int idx = k*m*n + i*m + j;
      if(mp[i][j] != '#') mct.add_edge(idx, base + idx, 1, 0);
    }
  }
  // - 上下左右の移動 (容量1, 損失U)
  // - 何もしない (容量1, 損失U)
  // - 木の実を食べる (容量1, 損失U - H_i)
  rep(k, t) {
    rep(i, n) {
      rep(j, m) {
        if(mp[i][j] == '#') continue;
        int idx = k*m*n + i*m + j;
        int to = idx + m*n;
        mct.add_edge(base + idx, to, 1, bloss - apple[k][i][j]);
        if(i > 0 && mp[i-1][j] != '#') mct.add_edge(base + idx, to - m, 1, bloss);
        if(j > 0 && mp[i][j-1] != '#') mct.add_edge(base + idx, to - 1, 1, bloss);
        if(i < n-1 && mp[i+1][j] != '#') mct.add_edge(base + idx, to + m, 1, bloss);
        if(j < m-1 && mp[i][j+1] != '#') mct.add_edge(base + idx, to + 1, 1, bloss);
      }
    }
  }
  // source -> S匹のヘビの初期位置 (sx_i, sy_i, 0) (容量1)
  rep(i, sn) {
    mct.add_edge(n0, sx[i]*m + sy[i], 1, 0);
  }
  // (i, j, T) の出頂点 -> sink (容量1)
  rep(i, n) {
    rep(j, m) {
      if(mp[i][j] == '#') continue;
      mct.add_edge(base + t*m*n + i*m + j, n0+1, 1, 0);
    }
  }
  ll flow = mct.flow(n0, n0+1, sn);
  // (初期のhapiness U×S×T) - (損失の総和の最小値) が答え
  cout << (ll) bloss * sn * t - flow << endl;
  return 0;
}