Official
B - Overlapping sheets Editorial by mechanicalpenciI
問題文の制約から、\(0\leq x\leq 100\) かつ \(0\leq y\leq 100\) 以外の領域について考える必要はなく、また、整数の組 \((i,j)\) \((1\leq i\leq 100, 1\leq j\leq 100)\) について、\(i-1\leq x\leq i\) かつ \(j-1\leq y\leq j\) の領域は各シートによって完全に覆われているか全く覆われていないかのどちらかです。よって、次のような問題を解くことを考えれば良いです。
- \(100\times 100\) のマス目があり、上から \(i\) 行目かつ左から \(j\) 列目をマス \((i,j)\) とよぶことにします。また、最初の時点で全てのマスは白く塗られているとします。
- \(1\leq k\leq N\) の順に、\(i\) 回目の操作では、\(A_k\leq i\leq B_k-1\) かつ \(C_k\leq j\leq D_k-1\) をみたす整数の組 \((i,j)\) について、マス \((i,j)\) を黒く塗ることを行います。
- \(N\) 回の操作の後で黒く塗られているマスの個数を求めてください。
これは for 文を用いることによって実際に塗る操作をシミュレーションすることができ、for文とif文を用いて最終的に黒く塗られているマスの個数を数えることで答えを求めることができます。
シミュレーションに必要な計算回数は、愚直に行っても \(N\times (100\times 100)\leq 10^6\) 程度であるため、十分高速にこの問題を解くことができます。よってこの問題を解くことができました。
c++ による実装例:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,a,b,c,d,ans=0;
bool g[100][100]={};
cin>>n;
for(int k=0;k<n;k++){
cin>>a>>b>>c>>d;
for(int i=a;i<b;i++)for(int j=c;j<d;j++)g[i][j]=true;
}
for(int i=0;i<100;i++)for(int j=0;j<100;j++)if(g[i][j])ans++;
cout<<ans<<endl;
return 0;
}
Python による実装例:
n=int(input())
g=[[False for i in range(100)]for i in range(100)]
for k in range(n):
a,b,c,d=map(int, input().split())
for i in range(a,b):
for j in range(c,d):
g[i][j]=True
ans=0
for i in range(100):
for j in range(100):
if g[i][j]==True:
ans+=1
print(ans)
posted:
last update: