AOJ0542 認証レベル

問題ページ

第一感二分探索で「承認レベルがxのときにy個以上の部屋を訪れられるか？」に答える方法だった。判定にO(HW)かけると1つの事務所につきO(HWlogL)になってしまう。今回の条件だと2つの事務所で訪れる部屋の数を合計Rになるように割り振る必要がありO(RHWlogL)は無理。
判定でO(HW)かけてるところで同じところを何度も探索してるのが無駄な感じがする。ここをうまくやって各事務所でx個以上の部屋を訪れるのに必要な最小の認証レベルを求められれば、あとはO®で割り振り方について探索して解けそう。認証レベルがiまでの部屋の集合をうまく持ちつつiをだんだん増やしていき、入り口とつながってる集合の大きさを随時把握するみたいな感じにするとよさそう。この集合の更新はマージの形式になるのでunionfindが使えそう。隣接した部屋が同一の集合にマージされるタイミングはいつか考える。これは隣接した部屋のうち認証レベルが高い方の認証レベルにiをあわせたタイミングになる。unionfindで持っていれば集合のサイズを把握するのはO(α(HW))でできる。したがって各事務所についてO(Lα(HW))かければできそう。
しかしO(L)はかけられない。集合がマージされるタイミングに注目すると部屋に設定されている認証レベルのタイミングしかない。したがってO(L)個すべて試すのではなく座圧してO(HW)通りのみ試せばよい。
まとめると、

O(HWα(HW)) で各事務所でx個以上の部屋を訪れるのに必要な最小の認証レベルを求める
O® で事務所1にi個、事務所2にr-i個の部屋を訪れるとしたときの認証レベルを求める

となる。

持たないといけないインデックスがいろいろあって頭がバグる。更新されるタイミングに注目したり、見る順番を変えると差分だけ見ればよくなってうまくいくとかはよくあるパターンだと思う。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136


#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;
template <typename T> using VVV = vector<VV<T>>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class UnionFind {
public:
  const static int MAX_N = 250010;
  int par[MAX_N];
  int s[MAX_N];
  UnionFind() { init(); }
  UnionFind(int n) { init(n); }
  void init() { for(int i=0; i<MAX_N; ++i) par[i] = i, s[i] = 1; }
  void init(int n) { for(int i=0; i<n; ++i) par[i] = i, s[i] = 1; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(s[x] < s[y]) par[x] = y, s[y] = s[x] + s[y];
    else par[y] = x, s[x] = s[x] + s[y];
  }
  bool same(int x, int y) { return find(x) == find(y);}
};
UnionFind uf;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(1) {
    int r;
    cin >> r;
    if(!r) break;
    int h, w, x, y;
    VV<int> a;

    auto func = [&]() -> V<int> {
      V<int> v;
      REP(i, h) REP(j, w) v.PB(a[i][j]);
      sort(ALL(v));
      v.erase(unique(ALL(v)), v.end());

      VV<int> g2(v.size());
      REP(i, h) REP(j, w) {
        g2[lower_bound(ALL(v), a[i][j]) - v.begin()].PB(i*w+j);
      }

      VV<int> g(h*w);
      REP(i, h) REP(j, w) {
        REP(k, 4) {
          int nx = j + dx[k], ny = i + dy[k];
          if(IN(0LL,w,nx) && IN(0LL,h,ny) && a[i][j]>=a[ny][nx]) {
            g[i*w+j].PB(ny*w+nx);
          }
        }
      }

      // b[i] = (部屋をi個訪れるときに必要な最小の認証レベル)
      V<int> b(h*w+1, INF);
      b[0] = 0, b[1] = 1;
      uf.init(h*w);
      REP(i, v.size()) {
        for(auto j: g2[i]) {
          for(auto k: g[j]) {
            uf.unite(j, k);
          }
        }
        chmin(b[uf.s[uf.find(y*w+x)]], v[i]);
      }
      return b;
    };

    cin >> w >> h >> x >> y, x--, y--;
    a = VV<int>(h, V<int>(w));
    REP(i, h) REP(j, w) cin >> a[i][j];
    V<int> p = func();
    for(int i=p.size()-2; i>=0; --i) {
      chmin(p[i], p[i+1]);
    }

    cin >> w >> h >> x >> y, x--, y--;
    a = VV<int>(h, V<int>(w));
    REP(i, h) REP(j, w) cin >> a[i][j];
    V<int> q = func();
    for(int i=q.size()-2; i>=0; --i) {
      chmin(q[i], q[i+1]);
    }

    int ret = INF;
    REP(i, r+1) {
      if(!IN(0LL,(int)p.size(),i) || !IN(0LL,(int)q.size(),r-i)) continue;
      chmin(ret, p[i]+q[r-i]);
    }
    cout << ret << endl;
  }

  return 0;
}