「AOJ531～540」の編集履歴（バックアップ）一覧に戻る
AOJ531～540 - (2012/03/09 (金) 09:22:46) のソース
----
*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();
}
}
----
*0536 Shuffle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0536
10億枚のカードを5000回シャッフルし、その中からｐ枚目からｑ枚目の中にｒ以下のカードが何枚あるかを高速に動作するコードで答えよという問題です。
解法
http://www.ioi-jp.org/joi/2008/2009-yo-prob_and_sol/2009-yo-t5/review/2009-yo-t5-review.html
リンク先と同じく基本は模範解答と同じく束として扱ってます。
高速化のためにショートカットを入れています。
山に分けるとき束をさらに束ねて山を作り計算を高速化という発想です。
単純肉体労働の作業時に出来るだけ塊で物を運ぶのと大差ない発想です。
山が3つなのでちょっと手抜きをしてコードを書きましたがループを使えばもう少しコードが短くなるはずです。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0538
100文字の文字列の中から(IO){n}I(正規表現)を見つける問題。
解法
規則正しさを利用して状態遷移マシンで解いてみました。
正規表現で解くのもいいかもしれません。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0539
環状線沿いのピザ屋の配置と注文情報から総配達距離を算出する問題。
解法
簡単な問題なので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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0540
あみだくじで端からK本選びゴールにある得点の合計がいくつになるか、横線を一本だけ消せるという条件で最低得点を求めよという問題。
解法
この問題はいくつかあみだくじを書いてみるとすぐに解法がわかります。
どこかの横線である数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];//ｎ段目の棒を削除した場合ｎ段目までのあみだは同じということを利用して結果を再利用する
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()){
}
}
