スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Facebook Hacker Cup 2013 Round 1 C : Dead Pixels

H × W のグリッド上に高々 N 個の点が与えられる。
Q × P の長方形を、点を一つも含まないようにグリッド上に置く方法は何通りあるか?
長方形を回転させたり、四隅が整数座標ではないところに置いてはいけない。

・ 1 ≦ Q ≦ H ≦ 40000
・ 1 ≦ P ≦ W ≦ 40000
・ 1 ≦ N ≦ min(10^6, HW)

解答

まず、長方形の上端を y = 0 に置くときを考える。
すると、0 ≦ y < Q をみたす点が障害になる。
これらの x 座標をすべて列挙して、O(W) で x 方向になめると、y = 0 の置き方の総数が求められる。

次に、長方形の上端が y = 1 である場合の数を数えたいなら、
y = 0 の点をリストから削除して、y = Q の点を新たにリストに加えれた後、x 方向になめる。

以下同様に処理できる。

計算量は O(HW + N log N)。

ソースコード

#include<cstdio>
#include<vector>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

int solve(){
int w,h,p,q,n; scanf("%d%d%d%d%d",&w,&h,&p,&q,&n);
static int x[1000000],y[1000000];
{
ll a,b,c,d;
scanf("%d%d%lld%lld%lld%lld",x,y,&a,&b,&c,&d);
rep(i,n-1){
x[i+1]=(x[i]*a+y[i]*b+1)%w;
y[i+1]=(x[i]*c+y[i]*d+1)%h;
}
}

vector<int> X[40000];
rep(i,n) X[y[i]].push_back(x[i]);
rep(i,h){
sort(X[i].begin(),X[i].end());
X[i].erase(unique(X[i].begin(),X[i].end()),X[i].end());
}

int ans=0,cnt[40000]={};
rep(i,q){
rep(j,X[i].size()) cnt[X[i][j]]++;
}
rep(i,h-q+1){
int pre=0;
rep(j,w+1) if(j==w || cnt[j]>0) {
ans+=max((j-pre)-p+1,0);
pre=j+1;
}

if(i<h-q){
rep(j,X[ i ].size()) cnt[X[ i ][j]]--;
rep(j,X[i+q].size()) cnt[X[i+q][j]]++;
}
}

return ans;
}

int main(){
int T,t; scanf("%d",&T);
for(t=1;t<=T;t++) printf("Case #%d: %d\n",t,solve());
return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。