C - 都市計画と道路整備 / Urban Planning and Road Development 解説 by admin
Claude 4.6 Opus (Thinking)概要
矩形領域の空き地を道路に変える工事を \(Q\) 回行い、各工事後に「道路に面している建物」の総数を求める問題です。工事領域の境界だけに着目し、新たに道路になったセルの隣にある建物を効率的に検出します。
考察
重要な気づき
単調増加性: 道路は増える一方（E→R）で、一度「道路に面した」建物はずっと面したままです。よってカウンタは増加のみで、差分更新が有効です。
建物が工事範囲に含まれない: 問題の保証により、工事範囲の内部には建物が存在しません。したがって、新たに道路になったセルが影響を与えうる建物は、工事矩形の外側かつ矩形の辺に隣接する位置にしか存在しません。
BBBBB ← 上辺の外側（行 U-1）に建物があるかも
RRRRR ← 上辺（行 U）：ここが新たに道路になったら上の建物に影響
RRRRR ← 内部：隣接セルも全て矩形内（建物なし）→ 影響なし
RRRRR ← 下辺（行 D）
BBBBB ← 下辺の外側（行 D+1）に建物があるかも
- 境界だけ調べればよい: 上の観察から、チェックすべきセルは矩形の上辺・下辺・左辺・右辺の計 \(O(\text{周長})\) 個だけです。制約で周長の総和が \(\leq 5 \times 10^6\) と保証されています。
素朴なアプローチの問題
工事ごとに矩形全体を走査すると \(O(HW \times Q)\) となり、\(HW \leq 2 \times 10^6\), \(Q \leq 10^5\) では間に合いません。
アルゴリズム
データ構造
各行の道路区間: 行ごとに
set<pair<int,int>>で道路セルの区間 \([l, r]\) を管理します（ソート済み・重複なし）。これにより：- あるセルが道路かどうかを \(O(\log W)\) で判定（
isRoad） - 範囲内の「まだ道路でないセル（ギャップ）」を効率的に列挙
- 新しい道路区間のマージ（
mergeInterval）
- あるセルが道路かどうかを \(O(\log W)\) で判定（
facing配列: 各建物が道路に面しているかの真偽値。カウンタ
cntで総数を管理。
各工事の処理手順
工事 \([U, D] \times [L, R]\)（0-indexed に変換）に対して：
上辺（行 \(U\)）: 列 \([L, R]\) 中でまだ道路でないセルを区間集合から見つけ、そのセル \((U, j)\) に対して上の隣 \((U-1, j)\) が未マーク建物なら
cnt++。1行矩形なら下の隣もチェック。左端・右端なら外側もチェック。下辺（行 \(D\)、\(U \neq D\) のとき）: 同様に、下の隣 \((D+1, j)\) をチェック。
左辺（行 \(U{+}1\) ～ \(D{-}1\)、列 \(L\)）: セルが新規道路なら左の隣 \((i, L{-}1)\) をチェック。1列矩形なら右もチェック。
右辺（\(L \neq R\) のとき、列 \(R\)）: セルが新規道路なら右の隣 \((i, R{+}1)\) をチェック。
道路区間のマージ: 行 \(U\) ～ \(D\) の各行で \([L, R]\) を区間集合にマージ。
cntを出力。
区間マージ (mergeInterval)
行の区間集合に \([l, r]\) を追加する際、重なるまたは隣接する既存区間を全て統合します。
既存: [2,4] [7,9] に [3,8] を追加
→ 統合して [2,9] になる
計算量
- 時間計算量: \(O\!\left(HW + \displaystyle\sum_{k=1}^{Q} P_k \cdot \log W\right)\)
- \(P_k = 2(D_k - U_k + 1) + 2(R_k - L_k + 1)\) は第 \(k\) 回工事の矩形の周長
- 周長の総和は \(\leq 5 \times 10^6\)
- 区間マージの償却コストは、区間が統合されるたびに減るため全体で \(O(HW)\)
- 空間計算量: \(O(HW)\)（グリッド、facing配列、区間集合）
実装のポイント
0-indexed への変換: 入力は 1-indexed なので、読み込み時に
U--; D--; L--; R--;を忘れないこと。角の二重カウント防止: 上辺・下辺で左端・右端のセルを処理する際、左辺・右辺の処理と重複しないように、左辺・右辺の走査範囲を
U+1～D-1に限定しています。ギャップの列挙: 行の区間集合を走査して \([L, R]\) 内のまだ道路でないセルを見つける処理は、
lower_boundで開始位置を特定してから順にギャップを収集します。markBuildingのガード: 範囲外チェック・建物チェック・既にマーク済みかのチェックを一括で行い、重複カウントを防止します。ソースコード
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int H,W,Q;
cin>>H>>W>>Q;
vector<string> grid(H);
for(int i=0;i<H;i++) cin>>grid[i];
// Per-row interval set of road columns (0-indexed)
// Using set<pair<int,int>> where each pair is [l,r] inclusive, sorted, non-overlapping
vector<set<pair<int,int>>> road(H);
// Initialize road intervals from grid
for(int i=0;i<H;i++){
int j=0;
while(j<W){
if(grid[i][j]=='R'){
int l=j;
while(j<W && grid[i][j]=='R') j++;
road[i].insert({l,j-1});
} else j++;
}
}
auto isRoad=[&](int i,int j)->bool{
if(i<0||i>=H||j<0||j>=W) return false;
auto it=road[i].upper_bound({j, INT_MAX});
if(it==road[i].begin()) return false;
--it;
return it->first<=j && j<=it->second;
};
// Track which buildings face road
vector<vector<bool>> facing(H, vector<bool>(W, false));
int cnt=0;
// Initial count
int dx[]={-1,1,0,0}, dy[]={0,0,-1,1};
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(grid[i][j]=='B'){
for(int d=0;d<4;d++){
int ni=i+dx[d], nj=j+dy[d];
if(ni>=0&&ni<H&&nj>=0&&nj<W&&grid[ni][nj]=='R'){
facing[i][j]=true;
cnt++;
break;
}
}
}
}
}
auto markBuilding=[&](int i,int j){
if(i>=0&&i<H&&j>=0&&j<W&&grid[i][j]=='B'&&!facing[i][j]){
facing[i][j]=true;
cnt++;
}
};
// Merge interval [l,r] into road[row], return which cells were newly added (on specified positions only)
auto mergeInterval=[&](int row, int l, int r){
auto it=road[row].lower_bound({l, -1});
if(it!=road[row].begin()){
--it;
if(it->second < l-1) ++it;
}
int nl=l, nr=r;
while(it!=road[row].end() && it->first<=r+1){
nl=min(nl, it->first);
nr=max(nr, it->second);
it=road[row].erase(it);
}
road[row].insert({nl,nr});
};
// Check if cell (i,j) was road before (we need to check before merging)
// We'll collect border cells, check, then merge
for(int q=0;q<Q;q++){
int U,D,L,R;
cin>>U>>D>>L>>R;
U--;D--;L--;R--; // 0-indexed
// Collect border cells and check which are newly becoming road
// Top border: row U, cols L..R -> check neighbor (U-1, j)
// Bottom border: row D, cols L..R -> check neighbor (D+1, j)
// Left border: rows U..D, col L -> check neighbor (i, L-1)
// Right border: rows U..D, col R -> check neighbor (i, R+1)
// Process top row
{
int i=U;
// find cells in [L,R] that are not yet road in row i
// then after marking, check (i-1,j) for building
vector<pair<int,int>> gaps;
auto it=road[i].lower_bound({L,-1});
if(it!=road[i].begin()){
--it;
if(it->second<L) ++it;
}
int cur=L;
while(it!=road[i].end() && it->first<=R){
if(cur < it->first){
gaps.push_back({cur, it->first-1});
}
cur=max(cur, it->second+1);
++it;
}
if(cur<=R) gaps.push_back({cur,R});
for(auto&[gl,gr]:gaps){
for(int j=gl;j<=gr;j++){
// cell (i,j) is newly road
markBuilding(i-1,j);
if(i==D) markBuilding(i+1,j);
if(j==L) markBuilding(i,j-1);
if(j==R) markBuilding(i,j+1);
}
}
}
// Process bottom row (if different from top)
if(D!=U){
int i=D;
vector<pair<int,int>> gaps;
auto it=road[i].lower_bound({L,-1});
if(it!=road[i].begin()){
--it;
if(it->second<L) ++it;
}
int cur=L;
while(it!=road[i].end() && it->first<=R){
if(cur < it->first){
gaps.push_back({cur, it->first-1});
}
cur=max(cur, it->second+1);
++it;
}
if(cur<=R) gaps.push_back({cur,R});
for(auto&[gl,gr]:gaps){
for(int j=gl;j<=gr;j++){
markBuilding(i+1,j);
if(j==L) markBuilding(i,j-1);
if(j==R) markBuilding(i,j+1);
}
}
}
// Process left column (rows U+1..D-1 if they exist, to avoid double counting corners)
{
int j=L;
for(int i=U+(D!=U?1:0); i<=D-(D!=U?1:0); i++){
if(!isRoad(i,j)){
markBuilding(i,j-1);
if(j==R) markBuilding(i,j+1);
}
}
}
// Process right column (if different from left)
if(R!=L){
int j=R;
for(int i=U+(D!=U?1:0); i<=D-(D!=U?1:0); i++){
if(!isRoad(i,j)){
markBuilding(i,j+1);
}
}
}
// Now merge [L,R] into all rows U..D
for(int i=U;i<=D;i++){
mergeInterval(i,L,R);
}
cout<<cnt<<'\n';
}
return 0;
}
この解説は claude4.6opus-thinking によって生成されました。