1045 Split Up!
#include<stdio.h>
#include<set>
int sum,herf,n,datas[21],t,ans,nHerf;
std::set<int> herfSum;
std::set<int>::iterator it;
void saikiB(int deep,int now){
if(deep<n){
saikiB(deep+1,now+datas[deep]);
saikiB(deep+1,now);
}else{
if(now<=herf){
it=herfSum.upper_bound(herf-now);
if((*it)!=0)it--;
now+=(*it);
t=sum-now*2;
}else{
t=now*2-sum;
}
ans=ans>t?t:ans;
}
}
void saikiA(int deep,int now){
if(deep<nHerf){
saikiA(deep+1,now+datas[deep]);
saikiA(deep+1,now);
}else{
herfSum.insert(now);
}
}
int main(){
while(scanf("%d",&n)){
if(n==0)break;
sum=0;
ans=2000000000;
herfSum.clear();
for(int i=0;i<n;i++){
scanf("%d",&datas[i]);
sum+=datas[i];
}
herf=sum/2;
nHerf=n/2;
saikiA(0,0);
saikiB(nHerf,0);
printf("%d\n",ans);
}
}
1046 Ghost Buster!
#include<stdio.h>
#include<string.h>
// 0 1 2 3 4 5 6 7 8
const int dxs[]={0,0,0,0,-1,0,1,0, 0};
const int dys[]={0,0,1,0, 0,0,0,0,-1};
const int max=100000000;
char map[21][21];
bool gMoveMemo[21][21];
int moveMemo[21][21];
int h,w;
bool areaOut(int x,int y){
if(x<0||x>=w||y<0||y>=h) return true;
return false;
}
void saiki(int x,int y,int deep){
if(areaOut(x,y)||map[y][x]=='#'||moveMemo[y][x]<=deep) return;
moveMemo[y][x]=deep;
saiki(x+1,y,deep+1);
saiki(x-1,y,deep+1);
saiki(x,y+1,deep+1);
saiki(x,y-1,deep+1);
}
void print(){
for(int y=0;y<h;y++){
for(int x=0;x<w;x++){
printf("%2d",moveMemo[y][x]==max?-1:moveMemo[y][x]);
}
printf("\n");
}
}
bool setData(){
scanf("%d %d",&h,&w);
if(h+w==0)return false;
int sx,sy,gx,gy;
memset(gMoveMemo,true,sizeof(gMoveMemo));
for(int y=0;y<h;y++){
scanf("%s",&map[y]);
for(int x=0;x<w;x++){
moveMemo[y][x]=max;
if(map[y][x]=='A'){
sx=x;
sy=y;
}else if(map[y][x]=='B'){
gx=x;
gy=y;
}
}
}
saiki(sx,sy,0);
//print();
char com[12];
scanf("%s",com);
int size=strlen(com),count=1,nx,ny,ans=max,ansX,ansY,turn=0;
while(count!=0&&ans>turn){
count=0;
for(int p=0;p<size;p++){
nx=dxs[com[p]-'0']+gx;
ny=dys[com[p]-'0']+gy;
turn++;
if(areaOut(nx,ny)==false){
gx=nx;
gy=ny;
}
if(moveMemo[gy][gx]<=turn){
gMoveMemo[gy][gx]=false;
count++;
if(ans>turn){
ans=turn;
ansX=gx;
ansY=gy;
}
}else if(gMoveMemo[gy][gx]==true){
count++;
gMoveMemo[gy][gx]=false;
}else if(moveMemo[gy][gx]!=max){
count++;
}
}
}
if(ans==max)printf("impossible\n");
else printf("%d %d %d\n",ans,ansY,ansX);
return true;
}
int main(){
while(setData()){
}
}
1047 Crop Circle
解法
数学の公式通りに円の交点を求め、円i上の交点を反時計回りにmemo[i]に入れていきます。
memo[i]の要素AiとAi+1が外部を構成するなら円弧AiAi+1の中点Biも外周に属します。
Biが外周に属するなら円弧AiAi+1の長さを足していけばこの問題は解けます。
小数点以下12桁指定でないと丸め誤差で不正回を食らうようなのでその点だけ要注意です。
#include<stdio.h>
#include<math.h>
#include<set>
struct circle{
double x,y,r,x2,y2,r2;
int no;
bool bad;//同心円でサイズが小さいことが判明したのは使わない
void set(int ino){
no=ino;
x2=x*x;
y2=y*y;
r2=r*r;
bad=false;
}
};
void setPoint(circle& c1,circle& c2,std::set<double> memo[101]){
if(c1.bad||c2.bad)return;//使わない円が来た
if(c1.x==c2.x&&c1.y==c2.y){
//計算誤差が怖いので念のため下と処理を分けておく
if(c1.r<c2.r)c1.bad=true;
else c2.bad=true;
return;
}
double len=sqrt(pow(c1.x-c2.x,2)+pow(c1.y-c2.y,2));
if(len<=fabs(c1.r-c2.r)){
//円の内側に入っていた
if(c1.r>=c2.r)c2.bad=true;
else c1.bad=true;
return;
}
if(c1.r+c2.r>len&&len>fabs(c1.r-c2.r)){
//交点が二つあることが判明したので
double x,y1,y2,cosA,sinA,tempX,tempY,ansR;
x=(c1.r2-c2.r2+len*len)/(2.0*len);
y1=sqrt(c1.r2-x*x);
y2=-y1;
//回転する
cosA=(c2.x-c1.x)/len;
sinA=(c2.y-c1.y)/len;
tempX=(cosA*x-sinA*y1);
tempY=sinA*x+cosA*y1;
//printf("<x=%lf,y=%lf>",tempX+c1.x,tempY+c1.y);
tempX=tempX/c1.r;
if(tempX>=1.0){
ansR=0;
}else if(tempX<=-1.0){
ansR=M_PI;
}else{
ansR=tempY<0?2*M_PI-acos(tempX):acos(tempX);
}
memo[c1.no].insert(ansR);
//二つ目の点を求める
tempX=(cosA*x-sinA*y2);
tempY=sinA*x+cosA*y2;
//printf("<x=%lf,y=%lf>\n",tempX+c1.x,tempY+c1.y);
tempX=tempX/c1.r;
//printf("(%lf)\n",tempX);
if(tempX>=1.0){
ansR=0;
}else if(tempX<=-1.0){
ansR=M_PI;
}else{
ansR=tempY<0?2*M_PI-acos(tempX):acos(tempX);
}
memo[c1.no].insert(ansR);
}
}
void setData(int n){
circle c,cs[101],c2;
for(int i=0;i<n;i++){
scanf("%lf %lf %lf",&c.x,&c.y,&c.r);
c.set(i);
cs[i]=c;
}
std::set<double> memo[101];//交点のメモ、各円に対して時計回りで記憶する
for(int i=0;i<n;i++){
memo[i].insert(0);//この円は交点を持つので
memo[i].insert(2*M_PI);//番兵
for(int j=0;j<n;j++){
if(i==j)continue;
setPoint(cs[i],cs[j],memo);
}
}
double ans=0;
std::set<double>::iterator it,nIt;
for(int i=0;i<n;i++){
if(cs[i].bad==true)continue;//別の円の内側に入っていた
//円を反時計回りに切り分けてその範囲が他の円に入るかを調べる
it=memo[i].begin();
nIt=it;
nIt++;
c=cs[i];
double r1,r2,r3,x1,y1,len1;
for(;nIt!=memo[i].end();it++,nIt++){
r1=(*it);
r2=(*nIt);
r3=(r1+r2)/2.0;
x1=c.r*cos(r3)+c.x;//切り分けた真中の点を求める
y1=c.r*sin(r3)+c.y;
bool bad=false;
for(int j=0;j<n;j++){
if(i==j)continue;
if(cs[j].bad==true)continue;
c2=cs[j];
len1=(x1-c2.x)*(x1-c2.x)+(y1-c2.y)*(y1-c2.y);
if(len1<c2.r2){
bad=true;
break;
}
}
if(bad==false){
ans+=c.r*(r2-r1);
}
}
}
printf("%.12lf\n",ans);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
setData(n);
}
}
1048 Provident Housewife
解法
まずどの店も到達できることが保証されています。
次に一番安い金額に納めるという条件が最優先なので全ての店を回って一番安い店だけで買い物した場合から最低購入金額が決まります。
後はその品物を一番安く売ってる店以外で物を買わないことに決めて店を回り、(一番安い金額で変えた品物のセットと今いるスーパーの組)を点に見立ててダイクストラ法で解きます。
#include<stdio.h>
#include<map>
#include<set>
#include<string>
#include<iostream>
#include<vector>
#include<queue>
struct Way{
int len,no;
};
struct Bay{
int shopNo,perm,len;
bool operator<(const Bay& b)const{
return len>b.len;
}
};
void calc(int n){
std::map<std::string,int> goodsMin;
std::map<std::string,int> goodsToBit;
std::map<std::string,int> shops[110];
int shopBits[110]={0};
int k,v;
std::string name;
for(int i=1;i<=n;i++){
std::cin>>k;
for(int j=0;j<k;j++){
std::cin>>name>>v;
if(goodsMin.find(name)==goodsMin.end()||goodsMin[name]>v){
goodsMin[name]=v;
}
shops[i][name]=v;
}
}
int q,bit=1,allSet=0;
scanf("%d",&q);
for(int i=0;i<q;i++){
std::cin>>name;
goodsToBit[name]=bit;
allSet+=bit;
bit*=2;
}
for(int i=1;i<=n;i++){
for(std::map<std::string,int>::iterator it=shops[i].begin();it!=shops[i].end();it++){
name=(*it).first;
v =(*it).second;
if(goodsToBit.find(name)!=goodsToBit.end()){
if(goodsMin[name]==v){
shopBits[i]|=goodsToBit[name];//namne商品が一番安い店なのでここ以外で買わない
}
}
}
}
int ans=0;
for(std::map<std::string,int>::iterator it=goodsToBit.begin();it!=goodsToBit.end();it++){
if(goodsMin.find((*it).first)==goodsMin.end()){
ans=-1;
break;
}else{
ans+=goodsMin[(*it).first];
}
}
//for(int i=0;i<=n;i++){
// printf("%d ",shopBits[i]);
//}
std::vector<Way> G[110];
Way way;
int m,s,t;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d %d %d",&s,&t,&way.len);
way.no=t;
G[s].push_back(way);
way.no=s;
G[t].push_back(way);
}
if(ans==-1){
printf("impossible\n");
return ;
}
std::map<int,int> memo[110];
std::priority_queue<Bay> qu;
Bay bay,nextBay;
bay.shopNo=bay.len=bay.perm=0;
qu.push(bay);
while(qu.empty()==false){
bay=qu.top();
qu.pop();
if(bay.shopNo==0&&bay.perm==allSet)break;
if(memo[bay.shopNo].find(bay.perm)!=memo[bay.shopNo].end()&&memo[bay.shopNo][bay.perm]<=bay.len)continue;
memo[bay.shopNo][bay.perm]=bay.len;
for(int i=0;i<G[bay.shopNo].size();i++){
way=G[bay.shopNo][i];
nextBay.perm=(bay.perm|shopBits[way.no]);
nextBay.len =(bay.len+way.len);
nextBay.shopNo=way.no;
if(memo[nextBay.shopNo].find(nextBay.perm)!=memo[nextBay.shopNo].end()&&
memo[nextBay.shopNo][nextBay.perm]<=nextBay.len)continue;
qu.push(nextBay);
}
}
printf("%d %d\n",ans,bay.len);
}
int main(){
int n;
while(1){
std::cin>>n;
if(n==0)break;
calc(n);
}
}
1049 Building Houses
深さ優先による全探索と枝刈を組み合わせただけのシンプルコードで通るようです。
一応コード実行速度3位を取ったコードだが一位との差は大きい。
一位がどんな魔法を使ったのか気になるところ。
メモ化による枝刈をもっと高度化したというところかな?
#include<stdio.h>
#include<string.h>
#include<algorithm>
int ans,lens[11],data[11][11];
bool spents[11];
int n;
void saiki(int deep,int l){
if(deep==n){
if(ans==-1)ans=l;
ans=std::min(ans,l);
}else{
int back[11];
bool out=false;
memcpy(back,lens,sizeof(lens));
for(int i=0;i<n;i++){
if(spents[i]==false){
spents[i]=true;
int len=lens[i];
for(int j=0;j<n;j++){
if(spents[j]==false)lens[j]=std::max(len+data[i][j],lens[j]);
if(ans>-1&&ans<=lens[j]&&spents[j]==false)out=true;
}
if(out==false)saiki(deep+1,len);
out=false;
memcpy(lens,back,sizeof(back));
spents[i]=false;
}
}
}
}
void setData(){
ans=-1;
memset(data,0,sizeof(data));
for(int i=0;i<n;i++){
spents[i]=false;
lens[i]=0;
for(int j=0;j<n;j++){
scanf("%d",&data[i][j]);
data[i][j]=data[j][i]=std::max(data[i][j],data[j][i]);
}
}
saiki(0,0);
printf("%d\n",ans);
}
int main(){
while(1){
scanf("%d",&n);
if(n==0)break;
setData();
}
}
最終更新:2013年02月10日 12:52