💬

ABC 182 | E - Akari

2020/11/08に公開

競プロ

tech

問題

考えたこと

入力例1だと以下のようになる。(0-indexedで考える)

光源ごとに愚直に光の届く範囲を確認するとおそらく $TLE$ になるので効率的にできないか考える。

以下のような光源とブロックがあったときに行ごとに走査していくことを考える。

左から右に走査し、光源があればそれ以降ブロックがあるまで光が届く範囲とする。

次に右から左に走査し、光源があればそれ以降ブロックがあるまで光が届く範囲とする。

これをすべての行と列にわたって行えば答えとなる。計算量としては $O(HW)$ なので時間内に答えが求められる。

コード

実装時のTips

マス目は $H$ または $W$ が最大1500マスなのでlightLengthのlの最大は10000にしている
最初勘違いして光が光源から左右上下4マスしか届かないと思っていたので以下のようなコードになっている。もっと簡単にするなら光源を見つけたら愚直にブロックまたは壁にあたるまで光を届け、新たな光源があってもその光源は意味がないのでチェックしないようにすればいい。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

ll lightLength(ll type, ll l) {
  if (type == 1) {
    l = 10000;
  } else if (type == 2) {
    l = -1;
  } else {
    l--;
  }
  return l;
}

int main() {
  int h, w, n, m;
  cin >> h >> w >> n >> m;
  vector<vector<int>> matrix(h, vector<int>(w, 0));       // 0: 何もなし, 1: 電球, 2: ブロック
  vector<vector<bool>> light(h, vector<bool>(w, false));  // true: 光っている
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    matrix[a][b] = 1;
  }
  for (int i = 0; i < m; i++) {
    int c, d;
    cin >> c >> d;
    c--;
    d--;
    matrix[c][d] = 2;
  }
  // 行方向に見ていく
  for (int i = 0; i < h; i++) {
    // 左->右
    ll l = -1;
    for (int j = 0; j < w; j++) {
      l = lightLength(matrix[i][j], l);
      if (l >= 0) {
        light[i][j] = true;
      }
    }
    // 右->左
    l = -1;
    for (int j = w - 1; j >= 0; j--) {
      l = lightLength(matrix[i][j], l);
      if (l >= 0) {
        light[i][j] = true;
      }
    }
  }
  // 列方向に見ていく
  for (int j = 0; j < w; j++) {
    ll l = -1;
    // 上->下
    for (int i = 0; i < h; i++) {
      l = lightLength(matrix[i][j], l);
      if (l >= 0) {
        light[i][j] = true;
      }
    }
    // 下->上
    l = -1;
    for (int i = h - 1; i >= 0; i--) {
      l = lightLength(matrix[i][j], l);
      if (l >= 0) {
        light[i][j] = true;
      }
    }
  }
  ll ans = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (light[i][j]) {
        ans++;
      }
    }
  }
  cout << ans << endl;
}

もうちょっとシンプルにしたバージョンは以下。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;

int main() {
  int h, w, n, m;
  cin >> h >> w >> n >> m;
  vector<vector<int>> matrix(h, vector<int>(w));   // 0: 何もなし, 1: 電球, 2: ブロック
  vector<vector<bool>> light(h, vector<bool>(w));  // true: 光っている
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    matrix[a][b] = 1;
  }
  for (int i = 0; i < m; i++) {
    int c, d;
    cin >> c >> d;
    c--;
    d--;
    matrix[c][d] = 2;
  }

  vector<int> ni = {1, 0, -1, 0};
  vector<int> nj = {0, 1, 0, -1};
  for (int k = 0; k < 4; k++) {  // 各方向についてみていく
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        if (matrix[i][j] != 1) continue;
        int ci = i, cj = j;  // 現在のi,j
        light[ci][cj] = true;
        while (true) {
          ci += ni[k];
          cj += nj[k];
          if (ci < 0 || h <= ci || cj < 0 || w <= cj || matrix[ci][cj] == 2 || matrix[ci][cj] == 1) {
            break;
          }
          light[ci][cj] = true;
        }
      }
    }
  }

  ll ans = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (light[i][j]) {
        ans++;
      }
    }
  }
  cout << ans << endl;
}

問題

考えたこと

コード

Discussion