AOJ2310 薔薇園の魔女 - ferinの競プロ帳

問題ページ
Rose Garden Witch | Aizu Online Judge

考えたこと

左下からの線分の偏角を微小量dtごとに変化させて全部試すみたいな解法を考える
判定部分でdfsでO(HW)かかるのでとてもじゃないけど精度がたりなさそう
線分を引く位置はどうせ少ないとかがないと不可能そう
格子点の前後以外で連結成分数が変動することはなさそう
各格子点を通る線分を列挙するのにO(HW)
連結成分数を愚直に数えるとdfsでO(HW)で全体O(H^2W^2)でだめそう
連結成分数を数えるパートをO(H+W)とかにしてO(HW(H+W))みたいな方針を考える
線分が通るマスの数がO(max(H,W))とかなのでこのマスだけをうまく見るみたいなの
出来る方法が何も思い浮かばないしそもそも3乗はどうなのか
格子点は(i,j)が互いに素な部分だけを気にすればいいのでちょっと枝刈りできそう
偏角が小さい格子点から順に試していくと気にする頂点がだんだん増えていってうれしいみたいなのを考える
新たに増えた頂点で連結成分数の変動がどうかを高速に判定できる方法がわからない
どう考えてもO(H^2W^2)から落ちない
-----解説を見た-----
直線を偏角順で動かしていくことを考えると連結成分数が変動するのは条件を満たす2*2マスの盤面を通過したとき
連結成分数が変動する場所の(偏角,+1 or -1)を全て列挙して偏角順に見ていく
連結成分数が最大になるタイミングの連結成分数を出力

学び

2*2マスの局所的な範囲で区切ると連結成分数が+1 or -1のタイミングを特定できる。
条件が変化するタイミングに着目

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#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 LLINF = (1LL<<60);
const int INF = (1LL<<30);
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};

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

  int h, w;
  cin >> h >> w;
  vector<string> v(h+2, string(w+2, '.'));
  FOR(i, 1, h+1) {
    cin >> v[i];
    v[i] = '.' + v[i] + '.';
  }

  vector<pair<double,int>> eve;
  REP(i, h+1) REP(j, w+1) {
    // (h-i, j+1) の偏角
    double ang = atan2(h-i, j);
    if(v[i][j] == '#' && v[i+1][j] == '.' && v[i][j+1] == '.' && v[i+1][j+1] == '.') {
      eve.PB({ang, 1});
    }
    if(v[i][j] == '.' && v[i+1][j] == '#' && v[i][j+1] == '#' && v[i+1][j+1] == '#') {
      eve.PB({ang, 1});
    }
    if(v[i][j] == '.' && v[i+1][j] == '.' && v[i][j+1] == '.' && v[i+1][j+1] == '#') {
      eve.PB({ang, -1});
    }
    if(v[i][j] == '#' && v[i+1][j] == '#' && v[i][j+1] == '#' && v[i+1][j+1] == '.') {
      eve.PB({ang, -1});
    }
  }

  sort(ALL(eve));
  int num = 1, ans = 2;
  for(auto i: eve) {
    num += i.second;
    chmax(ans, num);
  }
  cout << ans << endl;

  return 0;
}