AOJ 0509,0585
残り少ないVolume 5。一応JOIのチューターなのでソースを書いてみたりするなど。
0509:
O(N^2)をかけば通る。それより速い解法もあるんじゃないかなあ。どうなんだろう
#include<stdio.h> #include<algorithm> using namespace std; int dp[2][10000]; pair<pair<int,int>,pair<int,int> >event[20000]; int main(){ int a,b; while(scanf("%d%d",&a,&b),a){ int xm=0; int ym=0; for(int i=0;i<a;i++){ int p,q,r,s; scanf("%d%d%d%d",&p,&q,&r,&s); event[i*2]=make_pair(make_pair(p,1),make_pair(q,s)); event[i*2+1]=make_pair(make_pair(r,-1),make_pair(q,s)); xm=max(xm,r); ym=max(ym,s); } std::sort(event,event+a*2); for(int i=0;i<2;i++) for(int j=0;j<ym;j++) dp[i][j]=0; int S=0; int D=0; int at=0; for(int i=0;i<=xm;i++){ int u=i&1; for(int j=0;j<ym;j++)dp[u][j]=dp[!u][j]; for(;at<2*a&&event[at].first.first==i;at++){ for(int j=event[at].second.first;j<event[at].second.second;j++)dp[u][j]+=event[at].first.second; } for(int j=0;j<ym;j++)if(dp[u][j])S++; for(int j=0;j<ym;j++)if((dp[u][j]||dp[!u][j])&&!(dp[u][j]&&dp[!u][j]))D++; for(int j=0;j<ym-1;j++)if((dp[u][j]||dp[u][j+1])&&!(dp[u][j]&&dp[u][j+1]))D++; if(dp[u][0])D++; if(dp[u][ym-1])D++; } printf("%d\n",S); if(b==2)printf("%d\n",D); }}
0585:
典型のあれ書くのが面倒だったのでバケット法で嘘解法しました。ケースによってはこのコードだと落ちるが、ゆるいデータセットなのでセーフ。
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; int x[500000]; int y[500000]; vector<int>bag[201][201]; int dx[]={1,1,1,0,0,0,-1,-1,-1}; int dy[]={1,0,-1,1,0,-1,1,0,-1}; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d%d",x+i,y+i); x[i]+=10000; y[i]+=10000; bag[x[i]/100][y[i]/100].push_back(i); } int ret=999999999; if(a<=100){ for(int i=0;i<a;i++){ for(int j=i+1;j<a;j++)ret=min(ret,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); } printf("%d\n",ret); return 0; } for(int i=0;i<a;i++){ int R=x[i]/100; int W=y[i]/100; for(int j=0;j<9;j++){ if(0<=R+dx[j]&&R+dx[j]<201&&0<=W+dy[j]&&W+dy[j]<201){ for(int k=0;k<bag[R+dx[j]][W+dy[j]].size();k++){ if(i!=bag[R+dx[j]][W+dy[j]][k]) ret=min(ret,(x[i]-x[bag[R+dx[j]][W+dy[j]][k]])*(x[i]-x[bag[R+dx[j]][W+dy[j]][k]])+(y[i]-y[bag[R+dx[j]][W+dy[j]][k]])*(y[i]-y[bag[R+dx[j]][W+dy[j]][k]])); } } } } printf("%d\n",ret); }
UNSOLVED VOLUME 5
0508: String With Rings
どう考えても枝刈りゲー。こういうの苦手だし嫌いだから埋めていない。
0548: Reindeer with no sense of direction
解けぬ(本番では時間を使いまくって解けた) 正しい探索をすると枝刈り楽らしいが、変な解法だとどうしようもない定数倍改善が必要になるらしい。
0581: Gifts
少し面倒なだけのDP。いつでも通せると思う。