0531 Paint Color
解法
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
#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
#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
解法
一か所変更したら後はその上下が削除条件を満たすか調べていく関数に任せます。
上下に調査していき削除条件を満たす限り調べていき最終的に消去できる範囲を求めます。
#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
解法
問題のほうでルート数の上限が明示されているので何も考えず深さ優先探索で十分間に合います。
#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();
}
}
0536 Shuffle
#include<stdio.h>
#include<vector>
struct card{
int top,last;
};
void setCard(int n){
int m,p,q,r,x,y;
std::vector<card> cards;
std::vector<card> yama1,yama2,yama3;
std::vector<card>::iterator it;
card c,c1,c2;
scanf("%d",&m);
scanf("%d %d %d",&p,&q,&r);
for(int i=0;i<m;i++){
scanf("%d %d",&x,&y);
if(cards.empty()==true){
c.last=n;
c.top=y+1;
cards.push_back(c);
c.last=y;
c.top=x+1;
cards.push_back(c);
c.last=x;
c.top=1;
cards.push_back(c);
}else{
int count=0;
it=cards.begin();
yama1.clear();
yama2.clear();
yama3.clear();
while(count<x){
count+=(*it).last-(*it).top+1;
yama1.push_back(*it);
it++;
}
if(count>x){
c1=yama1.back();
c=yama1.back();
c2=yama1.back();
yama1.pop_back();
c1.last=c1.last-(count-x);
yama1.push_back(c1);
c.top=c1.last+1;
if(count>y){
c.last=c.top+y-x-1;
yama2.push_back(c);
c1.top=c.last+1;
c1.last=c2.last;
yama3.push_back(c1);
yama3.insert(yama3.end(),it,cards.end());
}else if(count==y){
c.last=c2.last;
yama2.push_back(c);
yama3.insert(yama3.end(),it,cards.end());
}else{
c.last=c2.last;
yama2.push_back(c);
while(count<y){
count+=(*it).last-(*it).top+1;
yama2.push_back(*it);
it++;
}
if(count>y){
c=yama2.back();
c1=yama2.back();
yama2.pop_back();
c.last=c.last-(count-y);
yama2.push_back(c);
c1.top=c.last+1;
yama3.push_back(c1);
yama3.insert(yama3.end(),it,cards.end());
}else{
yama3.insert(yama3.end(),it,cards.end());
} }
}else if(x==count){
while(y>count){
count+=(*it).last-(*it).top+1;
yama2.push_back(*it);
it++;
}
if(y<count){
c=yama2.back();
c1=yama2.back();
yama2.pop_back();
c.last=c.last-(count-y);
yama2.push_back(c);
c1.top=c.last+1;
yama3.push_back(c1);
yama3.insert(yama3.end(),it,cards.end());
}else{
yama3.insert(yama3.end(),it,cards.end());
}
}
cards.clear();
cards.insert(cards.end(),yama3.begin(),yama3.end());
cards.insert(cards.end(),yama2.begin(),yama2.end());
cards.insert(cards.end(),yama1.begin(),yama1.end());
}
}
it=cards.begin();
int count=0,ans=0,tl,ts;
//ここまでは多分完璧
bool first=true;
//printf("<ts tl count ans>\n");
while(it!=cards.end()){
count+=(*it).last-(*it).top+1;
if(p<=count){
if(first==true){
first=false;
ts=(*it).last-(count-p);
}else{
ts=(*it).top;
}
if(count<=q){
tl=(*it).last;
}else{
tl=(*it).last-(count-q);
//printf("a");
}
if(r<ts){
ans+=0;
}else if(ts<=r && r<=tl){
ans+=r-ts+1;
}else if(ts<=r && tl<=r){
ans+=tl-ts+1;
}
//printf("<%d %d %d %d>",ts,tl,count,ans);
}
it++;
if(q<=count) break;
}
printf("%d\n",ans);
}
int main(){
int n;
scanf("%d",&n);
while(n!=0){
setCard(n);
scanf("%d",&n);
}
}
0537
解くまで一年もかかった問題。
答えの解説まで読んで解説が難しいので解説をもとに解くのをあきらめた問題。
色々考えて足し算をする順番が大事だと気付く。
2次元空間のメモ化で正しく足し算をする順序にさえ気づけば普通に解くだけなら簡単な問題。
速度が出てないのでもっと賢い方法があるらしい。
#include<stdio.h>
#include<string.h>
int memo[2001][3001];
bool calc(){
int n,m,s,t,d;
scanf("%d %d %d",&n,&m,&s);
if(n+m+s==0) return false;
d=n*n;
m=m-d;
s=s-(d*(d+1))/2;
memset(memo,0,sizeof(memo));
memo[0][0]=1;
for(int p=1;p<=d;p++){
for(int c=0;c<m;c++){
for(int k=0;k<s;k++){
if(k+p>s)break;
memo[c+1][k+p]=(memo[c+1][k+p]+memo[c][k])%100000;
}
}
}
int ans=0;
for(int c=0;c<=m;c++)ans=(ans+memo[c][s])%100000;
printf("%d\n",ans);
return true;
}
int main(){
while(calc()){
}
}
0538 IOIOI
#include<stdio.h>
void search(int n){
const int max=1000001;
int ans=0,size,mode=0,count=0;
char text[max];
scanf("%d %s",&size,text);
for(int i=0;i<size;i++){
if(mode==0 && text[i]=='I'){
count++;
mode=1;
}else if(mode==1 && text[i]=='O'){
mode=0;
}else{
ans+=count-n>0?count-n:0;
count=mode=text[i]=='I'?1:0;
}
}
ans+=count-n>0?count-n:0;
printf("%d\n",ans);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
search(n);
}
}
0539 Pizza
解法
簡単な問題なのでstdの基本機能で片がつきます。
こういう簡単な問題は気楽に解ける分解いていて楽しいものです。
#include<stdio.h>
#include<set>
void setData(int d){
int n,m,p;
scanf("%d %d",&n,&m);
std::set<int> shops;
shops.insert(0);
shops.insert(d);
for(int i=1;i<n;i++){
scanf("%d",&p);
shops.insert(p);
}
std::set<int>::iterator it1,it2;
int d1,d2,ans=0;
for(int i=0;i<m;i++){
scanf("%d",&p);
it1=shops.upper_bound(p);
it2=it1;
it1--;
d1=p-(*it1);
d2=(*it2)-p;
ans+=d1>d2?d2:d1;
}
printf("%d\n",ans);
}
int main(){
int d;
while(1){
scanf("%d",&d);
if(d==0) break;
setData(d);
}
}
0540 Amidakuji
解法
この問題はいくつかあみだくじを書いてみるとすぐに解法がわかります。
どこかの横線である数AとBが入れ替わる場合、その横線を消すとゴールでのAとBの位置が入れ替わる。
この性質を利用して高速に解けます。
入れ替わりのある各段でどの数字が入れ替わったかをmemoに記録しておき、後は最後のループで横線を一つずつ消去した場合を試してはmemoを参照にどの数字が入れ替わったかを調べその状況で得点を入れ替えてからcalcで計算、その後元に戻して次の横線を消す作業を繰り返します。
比較的簡単な分析力問題でしょう。
#include<stdio.h>
#include<set>
#include <algorithm>
#include<string.h>
#include<vector>
struct bar{
int x,y;
bool operator<(const bar b)const{
if(y!=b.y)return y<b.y;
return x<b.x;
}
};
int calc(int dps[1002],int k){
int ans=0;
for(int i=1;i<=k;i++){
ans+=dps[i];
}
return ans;
}
int memo[1002][1002];//n段目の棒を削除した場合n段目までのあみだは同じということを利用して結果を再利用する
bool setData(){
int points[1002];//得点
int n,m,h,k;
scanf("%d %d %d %d",&n,&m,&h,&k);
if(n+m+h+k==0) return false;
for(int i=0;i<n;i++){
scanf("%d",&points[i+1]);//縦棒には1番から番号が付いている
}
bar b;
std::set<bar> bars;
for(int i=0;i<m;i++){
scanf("%d %d",&b.x,&b.y);
bars.insert(b);
}
int nowRow[1002];
//まずは1本も削除しない場合を計算する。
for(int x=1;x<=n;x++){
nowRow[x]=memo[0][x]=x;
}
std::set<bar>::iterator it=bars.begin();
int nowY=(*it).y;
while(it!=bars.end()){
if(nowY!=(*it).y){
memcpy(memo[nowY]+1,nowRow+1,4*n);
nowY=(*it).y;
}else{
std::swap(nowRow[(*it).x],nowRow[(*it).x+1]);
it++;
}
}
int downPoints[1002];
memcpy(memo[nowY]+1,nowRow+1,4*n);
for(int x=1;x<=n;x++){
downPoints[nowRow[x]]=points[x];
}
it=bars.begin();
int temp,r,l,ans;
ans=calc(downPoints,k);
while(it!=bars.end()){
r=memo[(*it).y][(*it).x ];
l=memo[(*it).y][(*it).x+1];
if(r>k && l>k){
it++;
continue;
}
std::swap(downPoints[r],downPoints[l]);
temp=calc(downPoints,k);
ans=ans>temp?temp:ans;
std::swap(downPoints[r],downPoints[l]);
it++;
}
printf("%d\n",ans);
return true;
}
int main(){
while(setData()){
}
}
最終更新:2012年03月09日 09:22