POJ 1009: Edge Detection - SSRS の競プロ日記

問題概要

縦 $H$ マス、横 $W$ マスの二次元グリッドがある。( $W$ のみが入力で与えられる。) 各マスに $0$ 以上 $255$ 以下の整数が書かれている。グリッドの $i$ 行目 $j$ 列目をマス $(i,j)$ と呼ぶ。

マス $(1,1), (1,2), \cdots, (1,W), (2,1), (2,2), \cdots, (2,W), \cdots, (H,1), (H,2), \cdots, (H,W)$ に書かれた数を順に並べた数列が、連長圧縮した形で与えられる。具体的には、この数列は $A_1$ を $B_1$ 個, $A_2$ を $B_2$ 個, ..., $A_N$ を $B_N$ 個順に並べたものである。

これから、以下の操作を全てのマスに対し同時に行う。

操作: マス $(i,j)$ に書かれた数を、そのマスに辺または角で接しているマスに書かれた数とマス $(i,j)$ に書かれた数の差の絶対値の最大値に書き換える。

操作を行った後のグリッドのマス $(1,1), (1,2), \cdots, (1,W), (2,1), (2,2), \cdots, (2,W), \cdots, (H,1), (H,2), \cdots, (H,W)$ に書かれた数を順に並べた数列を、連長圧縮した形で出力せよ。

制約

入力はすべて整数
$2 \leq HW \leq 10^ 9$
$1 \leq N \leq 1000$
$0 \leq A_i \leq 255 (1 \leq i \leq N)$
$B _ 1 + B _ 2 + \cdots + B _ N = HW$
$A _ i \neq A _ {i+1} (1 \leq i \leq N - 1)$

解法 1 ( $O(N^ 2)$ )

グリッドが大きいので、それぞれのマスについて調べることはできません。

連長圧縮した形では扱いにくいので、行をまたぐところで適切に分割し、長方形に変換して座標圧縮をすると、グリッドの大きさが $N \times N$ 以下となり、それぞれのマスの数を調べることができます。

座標圧縮したグリッドの各マスのに対応する長方形の辺と角については、操作を行ったとき結果が異なるので、別に扱う必要があります。

グリッドの周囲に番兵を配置すると、実装がしやすいです。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main(){
  while (true){
    int W;
    cin >> W;
    if (W == 0){
      break;
    }
    vector<int> p;
    int sum = 0;
    vector<int> r(1, 0);
    vector<int> h;
    vector<int> L, R, H;
    while (true){
      int a, b;
      cin >> a >> b;
      if (a == 0 && b == 0){
        break;
      }
      int tmp = W - sum % W;
      if (b <= tmp){
        p.push_back(a);
        L.push_back(sum % W);
        R.push_back(sum % W + b);
        H.push_back(h.size());
        if (b == tmp){
          h.push_back(1);
        }
      } else {
        if (sum % W != 0){
          p.push_back(a);
          L.push_back(sum % W);
          R.push_back(W);
          H.push_back(h.size());
          b -= tmp;
          sum += tmp;
          h.push_back(1);
        }
        if (b >= W){
          int q = b / W;
          p.push_back(a);
          L.push_back(0);
          R.push_back(W);
          H.push_back(h.size());
          h.push_back(1);
          if (q >= 3){
            p.push_back(a);
            L.push_back(0);
            R.push_back(W);
            H.push_back(h.size());
            h.push_back(q - 2);
          }
          if (q >= 2){
            p.push_back(a);
            L.push_back(0);
            R.push_back(W);
            H.push_back(h.size());
            h.push_back(1);
          }
        }
        if (b % W != 0){
          p.push_back(a);
          L.push_back(0);
          R.push_back(b % W);
          H.push_back(h.size());
        }
      }
      sum += b;
      r.push_back(sum % W);
    }
    sort(r.begin(), r.end());
    r.erase(unique(r.begin(), r.end()), r.end());
    int H2 = h.size();
    int W2 = r.size();
    vector<int> w(W2);
    for (int i = 0; i < W2 - 1; i++){
      w[i] = r[i + 1] - r[i];
    }
    w[W2 - 1] = W - r[W2 - 1];
    int N = p.size();
    vector<vector<int>> A(H2 + 2, vector<int>(W2 + 2));
    for (int i = 0; i < N; i++){
      L[i] = lower_bound(r.begin(), r.end(), L[i]) - r.begin() + 1;
      R[i] = lower_bound(r.begin(), r.end(), R[i]) - r.begin() + 1;
      for (int j = L[i]; j < R[i]; j++){
        A[H[i] + 1][j] = p[i];
      }
    }
    for (int i = 1; i <= W2; i++){
      A[0][i] = A[1][i];
      A[H2 + 1][i] = A[H2][i];
    }
    for (int i = 0; i < H2 + 2; i++){
      A[i][0] = A[i][1];
      A[i][W2 + 1] = A[i][W2];
    }
    vector<pair<int, int>> rle;
    for (int i = 1; i <= H2; i++){
      if (h[i - 1] == 1){
        for (int j = 1; j <= W2; j++){
          if (w[j - 1] == 1){
            int mx = 0;
            for (int dx = -1; dx <= 1; dx++){
              for (int dy = -1; dy <= 1; dy++){
                mx = max(mx, abs(A[i][j] - A[i + dx][j + dy]));
              }
            }
            rle.push_back(make_pair(mx, 1));
          } else {
            int mx1 = 0;
            for (int dx = -1; dx <= 1; dx++){
              for (int dy = -1; dy <= 0; dy++){
                mx1 = max(mx1, abs(A[i][j] - A[i + dx][j + dy]));
              }
            }
            rle.push_back(make_pair(mx1, 1));
            if (w[j - 1] >= 3){
              int mx3 = 0;
              for (int dx = -1; dx <= 1; dx++){
                mx3 = max(mx3, abs(A[i][j] - A[i + dx][j]));
              }
              rle.push_back(make_pair(mx3, w[j - 1] - 2));
            }
            int mx2 = 0;
            for (int dx = -1; dx <= 1; dx++){
              for (int dy = 0; dy <= 1; dy++){
                mx2 = max(mx2, abs(A[i][j] - A[i + dx][j + dy]));
              }
            }
            rle.push_back(make_pair(mx2, 1));
          }
        }
      } else {
        rle.push_back(make_pair(0, h[i - 1] * W));
      }
    }
    int N2 = rle.size();
    vector<pair<int, int>> ans;
    ans.push_back(rle[0]);
    for (int i = 1; i < N2; i++){
      if (rle[i].first == rle[i - 1].first){
        ans.back().second += rle[i].second;
      } else {
        ans.push_back(rle[i]);
      }
    }
    int N3 = ans.size();
    cout << W << endl;
    for (int i = 0; i < N3; i++){
      cout << ans[i].first << ' ' << ans[i].second << endl;
    }
    cout << 0 << ' ' << 0 << endl;
  }
  cout << 0 << endl;
}

解法 2 ( $O(N)$ )

解法 1 では横方向の座標圧縮をすべての行に同じように適用していましたが、操作後の数値が変化する可能性があるのは現在見ている行とその上下の行の数値の境目のみなので、それらについてのみ座標圧縮を行うと、計算量が $O(N)$ に落ちます。

$O(N \log N)$ にならないように、ソートをマージにしたり、二分探索をしゃくとり法にすることが必要です。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int main(){
  while (true){
    int W;
    cin >> W;
    if (W == 0){
      break;
    }
    vector<vector<pair<int, int>>> row;
    vector<int> h;
    int sum = 0;
    while (true){
      int a, b;
      cin >> a >> b;
      if (a == 0 && b == 0){
        break;
      }
      int r = W - sum % W;
      if (b <= r){
        if (sum % W == 0){
          row.push_back(vector<pair<int, int>>(0));
          h.push_back(1);
        }
        row.back().push_back(make_pair(a, b));
      } else {
        if (sum % W != 0){
          row.back().push_back(make_pair(a, r));
          b -= r;
          sum += r;
        }
        if (b >= W){
          int q = b / W;
          row.push_back(vector<pair<int, int>>(1, make_pair(a, W)));
          h.push_back(1);
          if (q >= 3){
            row.push_back(vector<pair<int, int>>(1, make_pair(a, W)));
            h.push_back(q - 2);
          }
          if (q >= 2){
            row.push_back(vector<pair<int, int>>(1, make_pair(a, W)));
            h.push_back(1);
          }
        }
        if (b % W != 0){
          row.push_back(vector<pair<int, int>>(0));
          h.push_back(1);
          row.back().push_back(make_pair(a, b % W));
        }
      }
      sum += b;
    }
    int H = row.size();
    vector<pair<int, int>> tmp1 = row.front();
    row.insert(row.begin(), tmp1);
    vector<pair<int, int>> tmp2 = row.back();
    row.push_back(tmp2);
    for (int i = 0; i <= H + 1; i++){
      int cnt = row[i].size();
    }
    vector<pair<int, int>> rle;
    for (int i = 1; i <= H; i++){
      if (h[i - 1] == 1){
        vector<vector<int>> c(3);
        for (int j = 0; j < 3; j++){
          int sum = 0;
          int cnt = row[i + j - 1].size();
          for (int k = 0; k < cnt; k++){
            c[j].push_back(sum);
            sum += row[i + j - 1][k].second;
          }
        }
        vector<int> c1;
        merge(c[0].begin(), c[0].end(), c[1].begin(), c[1].end(), back_inserter(c1));
        vector<int> c2;
        merge(c1.begin(), c1.end(), c[2].begin(), c[2].end(), back_inserter(c2));
        c2.erase(unique(c2.begin(), c2.end()), c2.end());
        int N = c2.size();
        vector<int> w(N);
        for (int j = 0; j < N - 1; j++){
          w[j] = c2[j + 1] - c2[j];
        }
        w[N - 1] = W - c2[N - 1];
        vector<vector<int>> a(N, vector<int>(3));
        for (int j = 0; j < 3; j++){
          int cnt = c[j].size();
          c[j].push_back(W);
          int L = 0;
          for (int k = 0; k < cnt; k++){
            int R = L;
            while (c2[R] < c[j][k + 1]){
              R++;
              if (R >= N){
                break;
              }
            }
            for (int l = L; l < R; l++){
              a[l][j] = row[i + j - 1][k].first;
            }
            L = R;
          }
        }
        vector<int> tmp3 = a.front();
        a.insert(a.begin(), tmp3);
        vector<int> tmp4 = a.back();
        a.push_back(tmp4);
        for (int j = 1; j <= N; j++){
          if (w[j - 1] == 1){
            int mx = 0;
            for (int k = j - 1; k <= j + 1; k++){
              for (int l = 0; l < 3; l++){
                mx = max(mx, abs(a[j][1] - a[k][l]));
              }
            }
            rle.push_back(make_pair(mx, 1));
          } else {
            int mx1 = 0;
            for (int k = j - 1; k <= j; k++){
              for (int l = 0; l < 3; l++){
                mx1 = max(mx1, abs(a[j][1] - a[k][l]));
              }
            }
            rle.push_back(make_pair(mx1, 1));
            if (w[j - 1] >= 3){
              int mx = max(abs(a[j][1] - a[j][0]), abs(a[j][1] - a[j][2]));
              rle.push_back(make_pair(mx, w[j - 1] - 2));
            }
            int mx2 = 0;
            for (int k = j; k <= j + 1; k++){
              for (int l = 0; l < 3; l++){
                mx2 = max(mx2, abs(a[j][1] - a[k][l]));
              }
            }
            rle.push_back(make_pair(mx2, 1));
          }
        }
      } else {
        rle.push_back(make_pair(0, h[i - 1] * W));
      }
    }
    int M = rle.size();
    vector<pair<int, int>> ans;
    ans.push_back(rle[0]);
    for (int i = 1; i < M; i++){
      if (rle[i].first == rle[i - 1].first){
        ans.back().second += rle[i].second;
      } else {
        ans.push_back(rle[i]);
      }
    }
    int M2 = ans.size();
    cout << W << endl;
    for (int i = 0; i < M2; i++){
      cout << ans[i].first << ' ' << ans[i].second << endl;
    }
    cout << 0 << ' ' << 0 << endl;
  }
  cout << 0 << endl;
}

問題概要

制約

解法 1 ()

解法 2 ()

解法 1 ( $O(N^ 2)$ )

解法 2 ( $O(N)$ )