「AOJ531～540」の編集履歴（バックアップ）一覧に戻る
AOJ531～540 - (2011/11/04 (金) 19:11:29) のソース
----
*0531 Paint Color
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531
ベニヤ板をマスキングテープで区切り、区切られた部分を全て違う色でぬるとき何色必要か。
マスキングテープの頂点情報とベニヤ板のサイズからそれを答えよという問題です。
解法
Y軸と平行に1単位ごとにベニヤ板を区切り、隣の列と同じテープの張られ方をしている列を全てまとめてベニヤ板を圧縮します。
後は列ごとに隣の列と比較しテープの貼られてない領域を点とみて辺でコネクトしていきグラフを作ります。
コネクトされてできた森の数を数えれば答えが出ます。
下記コードは上記の考え方に基づき記述したものです。
実行速度で正答者40位中3位をとったコードですが、コードサイズが膨らんでしまいました。
おそらくもっとシンプルな考え方で色数を計算できるはずですので他の方のコードを参考にしてください。
#include<stdio.h>
#include<vector>
#include<set>
#include <algorithm>
struct point{
int x1,x2,y,inOut;
bool operator<(const point p)const{
if(y!=p.y)return y<p.y;
return inOut>p.inOut;
}
void set(int xi,int xi2,int yi,int inOuti){
x1=xi;
x2=xi2;
y=yi;
inOut=inOuti;
}
};
std::vector<bool> moveOKs;
void connectSearch(std::vector<std::set<int> >& con,int now){
std::set<int>::iterator it=con[now].begin();
moveOKs[now]=false;
while(it!=con[now].end()){
if(moveOKs[(*it)]==true)connectSearch(con,(*it));
it++;
}
}
void setData(int w,int h){
int n;
point p;
scanf("%d",&n);
int x1,y1,x2,y2;
std::vector<point> points;
std::set<int> xs;
moveOKs.clear();
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
p.set(x1,x2,y1,1);
points.push_back(p);
p.set(x1,x2,y2,-1);
points.push_back(p);
xs.insert(x1);
xs.insert(x2);
}
xs.insert(0);
p.set(0,w,0,1);
points.push_back(p);
p.set(0,w,0,-1);
points.push_back(p);
p.set(0,w,h,1);
points.push_back(p);
std::sort(points.begin(),points.end());
std::set<int>::iterator it=xs.begin();
int nowX,colorCount=0,size;
int inOutCount,now,old,turn=0;
std::vector<int> yMemo[2];
std::vector<int> yNoMemo[2];
std::vector<std::set<int> > connect;
std::set<int> dammySet;
while(it!=xs.end()){
nowX=(*it);
inOutCount=0;
now=turn%2;
old=(turn+1)%2;
turn++;
yMemo[now].clear();
yNoMemo[now].clear();
size=points.size()-1;
for(int i=0;i<size;i++){
if(nowX<points[i].x1 || points[i].x2<=nowX)continue;
//printf("(%d %d %d %d %d) \n",i,points[i].x1,points[i].x2,points[i].y,points[i].inOut);
inOutCount+=points[i].inOut;
if(inOutCount==0){
yMemo[now].push_back(points[i ].y);
int tempy=points[i].y;
while(tempy==points[i].y || nowX<points[i].x1 || points[i].x2<=nowX){
i++;
if(points[i].x1<=nowX && nowX<points[i].x2){
inOutCount+=points[i].inOut;
//printf("(%d %d %d %d %d) \n",i,points[i].x1,points[i].x2,points[i].y,points[i].inOut);
}
}
yMemo[now].push_back(points[i].y);
yNoMemo[now].push_back(-1);
}
}
//printf("\n%d\n",yMemo[now].size());
if(yMemo[now].empty()){
it++;
continue;
}
/*
for(int i=0;i<yMemo[now].size();i+=2){
printf("(%d %d)",yMemo[now][i],yMemo[now][i+1]);
}
printf("\n");
*/
size=yMemo[now].size();
unsigned int oldP=0,nowP=0;
int y1,y2,y3,y4;
while(oldP<yMemo[old].size() && nowP<yMemo[now].size()){
y1=yMemo[old][oldP ];
y2=yMemo[old][oldP+1];
y3=yMemo[now][nowP ];
y4=yMemo[now][nowP+1];
if(y2<=y3){
oldP+=2;
}else if(y1>=y4){
if(yNoMemo[now][nowP/2]==-1){
yNoMemo[now][nowP/2]=colorCount;
connect.push_back(dammySet);
colorCount++;
moveOKs.push_back(true);
}
nowP+=2;
}else{
if(yNoMemo[now][nowP/2]==-1){
yNoMemo[now][nowP/2]=yNoMemo[old][oldP/2];
}else{
connect[yNoMemo[now][nowP/2]].insert(yNoMemo[old][oldP/2]);
connect[yNoMemo[old][oldP/2]].insert(yNoMemo[now][nowP/2]);
}
if(y2>y4){
nowP+=2;
}else if(y2<y4){
oldP+=2;
}else{
nowP+=2;
oldP+=2;
}
}
}
for(unsigned int i=nowP;i<yMemo[now].size();i+=2){
if(yNoMemo[now][i/2]==-1){
yNoMemo[now][i/2]=colorCount;
connect.push_back(dammySet);
colorCount++;
moveOKs.push_back(true);
}
}
it++;
}
int sum=0;
for(unsigned int i=0;i<moveOKs.size();i++){
if(moveOKs[i]==true){
sum++;
connectSearch(connect,i);
}
}
printf("%d\n",sum);
}
int main(){
int w,h;
while(1){
scanf("%d %d",&w,&h);
if(w==0 && h==0) break;
setData(w,h);
}
}
----
*0532 Time Card
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0532
タイムカードの勤務記録から勤務時間を算出する問題。
解法
簡単な問題なので書くだけです。
#include<stdio.h>
int main(){
int h,m,s,h2,m2,s2;
for(int i=0;i<3;i++){
scanf("%d %d %d %d %d %d",&h,&m,&s,&h2,&m2,&s2);
int wtime=(h2-h)*3600+(m2-m)*60+(s2-s);
printf("%d %d %d\n",wtime/3600,(wtime%3600)/60,wtime%60);
}
}
----
*0533 Contest
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0533
2大学の学生10人と10人の上位3人の得点を集計する問題。
解法
そのまま書くだけです。
#include<stdio.h>
#include <algorithm>
int main(){
int s[20];
for(int i=0;i<20;i++)scanf("%d",&s[i]);
std::sort(s,s+10);
std::sort(s+10,s+20);
printf("%d %d\n",s[9]+s[8]+s[7],s[19]+s[18]+s[17]);
}
----
*0534 Chain
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0534
ぷよぷよと同じ連鎖を計算する問題。
一列のみだがプヨの数が一万個と少し多いので計算方法に工夫が必要。
解法
一か所変更したら後はその上下が削除条件を満たすか調べていく関数に任せます。
上下に調査していき削除条件を満たす限り調べていき最終的に消去できる範囲を求めます。
#include<stdio.h>
int dellSearch(int nowP,int col[10002]){
int upP=nowP,downP=nowP,count=4;
int nowColor,ansUp=nowP+1,ansDown=nowP;
while(count>3){
count=0;
if(upP==downP)count=-1;
if(col[upP]==-1 || col[downP]==-1) break;
nowColor=col[upP];
while(col[upP]==nowColor){
upP++;
count++;
}
while(col[downP]==nowColor){
downP--;
count++;
}
if(count>3){
ansUp=upP;
ansDown=downP;
}
}
return ansUp-ansDown-1;
}
void setData(int n){
int col[10002];
for(int i=1;i<=n;i++){
scanf("%d",&col[i]);
}
col[0]=col[n+1]=-1;//番兵
int temp,t,ans=0;
for(int i=1;i<=n;i++){
temp=col[i];
for(int k=1;k<4;k++){
col[i]=k;
t=dellSearch(i,col);
ans=ans>t?ans:t;
}
col[i]=temp;
}
printf("%d\n",n-ans);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
setData(n);
}
}
----
*0535 Crossing Black Ice
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0535
升目に区切られたマップで氷を割りながらスケートを楽しむとき最も長い経路を求めるという問題。
解法
問題のほうでルート数の上限が明示されているので何も考えず深さ優先探索で十分間に合います。
#include<stdio.h>
int w,h,ans;
int dxs[4]={1,0,-1,0};
int dys[4]={0,1,0,-1};
int map[91][91];
void saiki(int x,int y,int deep){
if(x<0 || w<=x || y<0 || h<=y) return;
if(map[y][x]==0)return;
map[y][x]=0;
ans=ans>deep?ans:deep;
int nx,ny;
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
saiki(nx,ny,deep+1);
}
map[y][x]=1;
}
void setData(){
ans=0;
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
scanf("%d",&map[y][x]);
}
}
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
saiki(x,y,1);
}
}
printf("%d\n",ans);
}
int main(){
while(1){
scanf("%d %d",&w,&h);
if(w==0 && h==0) break;
setData();
}
}
