「2011～2020」の編集履歴（バックアップ）一覧に戻る
2011～2020 - (2012/07/08 (日) 05:27:48) のソース
*2011 Gather the Maps!
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011
各人のスケジュールに合わせて宝の地図を手渡しで集めていく問題です。
この問題の解法は、ある日集まれる人全てを一か所に集めて、○○さんに全部渡した場合を全部を考えていきます。
集まったAさんに渡した場合、Bさんに渡した場合、、、の仮定を全部同時進行で計算していき最初に全部集まった人を発見したらそこで計算が終了となります。
誰がどの地図をどんな順番で持っていても最後に誰かに集めるなら途中経過でどんなふうに持っていても関係ないということが計算量を落とす秘訣です。
perm[最大人数]で各人のd日目の各人の地図の集まり具合を考慮します。
こうやってシンプルな解法を見つけると、昔の自分のコードがとても恥ずかしくなりますね。
今からでも全部のコードを書きなおしたいくらいです。
#include<stdio.h>
#include<vector>
bool calc(int n){
long long int perm[51],ans=0,one=1,oneDay;
for(int i=0;i<n;i++)ans|=(one<<i);
std::vector<int> hSc[32];
int f,c;
for(int i=0;i<n;i++){
scanf("%d",&f);
while(f--){
scanf("%d",&c);
hSc[c].push_back(i);
}
perm[i]=(one<<i);
}
for(int d=0;d<31;d++){
oneDay=0;
for(int p=0;p<hSc[d].size();p++){
oneDay|=perm[hSc[d][p]];
}
for(int p=0;p<hSc[d].size();p++){
perm[hSc[d][p]]=oneDay;
}
if(oneDay==ans){
printf("%d\n",d);
return true;
}
}
printf("-1\n");
return false;
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
*2012 Space Coconut Grab
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2012
この問題はｚが決まれば残りのｙとｘの関係はｙのほうが大きければ大きい方がよい結果になるということを利用して解く。
ｚとｙの間にその関係は無いのでｚは虱潰し、ｙは最大値を求めて後は計算誤差が怖いのでその対処だけ。
#include<stdio.h>
#include<math.h>
#include <algorithm>
void calc(int n){
int zMax;
int ans=2000000000;
zMax=(int)pow((double)n,1/3.0)+2;
for(double z=0;z<zMax;z++){
if(n<z*z*z)continue;
int n2=n-z*z*z;
int y=(int)sqrt(n2);
if(n2<y*y&&y>0){
y--;
}
ans=std::min(ans,(int)(z+y+(n2-y*y)));
}
printf("%d\n",(int)ans);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
*2013 Osaki
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2013
到着した台数と帰ってきた台数の数を数えていくだけの簡単な問題なのだけど？
コード実行速度が出ない。
0：00:00はどうやって達成するのだろう？
#include<stdio.h>
#include<string.h>
int count[86402];
bool calc(){
int n,hh,mm,ss;
char s1,s2;
scanf("%d",&n);
if(n==0)return false;
memset(count,0,sizeof(count));
while(n--){
scanf("%2d%c%2d%c%2d",&hh,&s1,&mm,&s2,&ss);
count[hh*3600+mm*60+ss]++;
scanf("%2d%c%2d%c%2d",&hh,&s1,&mm,&s2,&ss);
count[hh*3600+mm*60+ss]--;
}
int ans=0,c=0;
for(int i=0;i<86401;i++){
c+=count[i];
ans=ans>c?ans:c;
}
printf("%d\n",ans);
return true;
}
int main(){
int n;
while(calc()){
}
}
*2017 Karakuri Doll
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2017
壁にあたるたびに右か左に移動するパタンをプログラムされた人形が迷路になっている屋敷を抜けてゴールまで辿りつき、プログラムを逆実行してゴールからスタートへ戻れるかを問う問題。
右が左で左が右で混乱した問題。
この問題は行きはよいよい帰りは恐い。
行きは前に通ったのと同じ状態になったら探索を止める幅優先探索で楽勝、中学生でも解けそうな問題です。
帰りは、行きを逆回しで行う探索と*帰りの探索をセットで行いセットで探索する必要がありかなり混乱しました。
pointはx,y,rが位置と今の人形の向きを表します。
rePoint構造体で帰りの探索とゴールから始める行きの逆回しをpoint２つで記憶します。
スタートやゴールからある地点にある向きで到達するプログラムが複数ある時、途中の人形プログラムがどうであろうと、その人形プログラムはその地点にある特定の向きで到達するプログラムであるという共通点があり、一度一つのプログラムを見つければ他の同じ地点に同じ向きで到達するプログラムは以後探索する必要がありません。
これを使って探索を枝かりできるわけです、具体的にはstd::set<rePoint> memosやmemoを使っています。
後は、逆回し+ゴールからスタートへのルート探索をnextsCalcで探索して幅優先探索に追加していけばいいだけです。
素朴な発想で書いたのでコードサイズも膨らんだし速度も出てませんが素朴なだけに分かりやすくメモリも使わないとコードという利点があります。
#include<stdio.h>
#include<set>
#include<queue>
struct point{
int x,y,r;
bool operator<(const point& p)const{
if(x!=p.x)return x<p.x;
if(y!=p.y)return y<p.y;
if(r!=p.r)return r<p.r;
return false;
}
bool operator!=(const point& p)const{
if(x!=p.x)return x!=p.x;
if(y!=p.y)return y!=p.y;
if(r!=p.r)return r!=p.r;
return false;
}
};
struct rePoint{
point p1,p2;
bool operator<(const rePoint& rp)const{
if(p1!=rp.p1)return p1<rp.p1;
if(p2!=rp.p2)return p2<rp.p2;
return false;
}
};
bool startOK,returnOK;
int sx,sy,gx,gy;
char map[18][70];
int startR;
//char muki[4][6]={"→","↓","←","↑"};
int dxs[]={1,0,-1,0};//右下左上1増えると右回り
int dys[]={0,1,0,-1};
void okCheck(const point& p){
if(p.x==gx&&p.y==gy){
startOK =true;
}
}
void okCheckRe(const rePoint& p){
if(p.p1.x==sx&&p.p1.y==sy&&p.p2.x==sx&&p.p2.y==sy&&startR==p.p2.r){
//printf("\n+++++++<<%d %d>>\n",p.p1.r,p.p2.r);
returnOK=true;
}
}
void nextStopPoint(const point& p,point& next){
next.r=p.r;
for(int i=1;i<100;i++){
int dx=p.x+dxs[p.r]*i;
int dy=p.y+dys[p.r]*i;
if(map[dy][dx]=='#'){
next.x=p.x+dxs[p.r]*(i-1);
next.y=p.y+dys[p.r]*(i-1);
break;
}
}
}
void nextsCalc(const rePoint& nowP,std::set<rePoint>& memo,std::queue<rePoint>& now){
rePoint next=nowP;
nextStopPoint(nowP.p1,next.p1);
int r2=nowP.p2.r;
//printf("\n<0(%d %d %s)(%d %d %s)>\n",next.p1.x,next.p1.y,muki[next.p1.r],next.p2.x,next.p2.y,muki[next.p2.r]);
for(int i=0;i<100;i++){
int nowX=nowP.p2.x+dxs[r2]*i;
int nowY=nowP.p2.y+dys[r2]*i;
//printf("(%d %d %c)",nowX,nowY,map[nowY][nowX]);
if(map[nowY][nowX]=='#'){
return;
}
//帰りが右向き
int dx=nowX+dxs[(r2+3)%4];
int dy=nowY+dys[(r2+3)%4];
if(map[dy][dx]=='#'){
next.p2.x=nowX;
next.p2.y=nowY;
next.p2.r=r2;
okCheckRe(next);
next.p2.r=(r2+1)%4;
next.p1.r=(nowP.p1.r+1)%4;
//printf(",<1(%d %d %s)(%d %d %s)>\n",next.p1.x,next.p1.y,muki[next.p1.r],next.p2.x,next.p2.y,muki[next.p2.r]);
if(memo.find(next)==memo.end()){
okCheckRe(next);
memo.insert(next);
now.push(next);
}
}
dx=nowX+dxs[(r2+1)%4];
dy=nowY+dys[(r2+1)%4];
if(map[dy][dx]=='#'){
next.p2.x=nowX;
next.p2.y=nowY;
next.p2.r=r2;
okCheckRe(next);
next.p2.r=(r2+3)%4;
next.p1.r=(nowP.p1.r+3)%4;
//printf("<2(%d %d %s)(%d %d %s)>\n",next.p1.x,next.p1.y,muki[next.p1.r],next.p2.x,next.p2.y,muki[next.p2.r]);
if(memo.find(next)==memo.end()){
okCheckRe(next);
memo.insert(next);
now.push(next);
}
}
}
}
void reCalc(rePoint nowP,int r2){
std::set<rePoint> memos;
std::queue<rePoint> nows;
for(int i=0;i<4;i++){
nowP.p2.r=i;
if(i==(r2+2)%4)continue;
nows.push(nowP);
}
int count=1;
while(!nows.empty()){
nowP=nows.front();
//if(count%20==0)scanf("%d",&count);
//count++;
nows.pop();
if(returnOK==true)break;
nextsCalc(nowP,memos,nows);
}
}
bool calc(){
startOK=false;
returnOK=false;
int h,w,r1,r2;
char c;
scanf("%d %d",&w,&h);
if(w==0&&h==0)return false;
for(int i=0;i<h;i++){
scanf("%s",map[i]);
}
for(int i=1;i<h-1;i++){
for(int j=1;j<w-1;j++){
c=map[i][j];
if(c=='K'){
sx=j;
sy=i;
for(int k=0;k<4;k++){
int dx=j+dxs[k];
int dy=i+dys[k];
if(map[dy][dx]!='#')r1=k;
}
}else if(c=='M'){
gx=j;
gy=i;
for(int k=0;k<4;k++){
int dx=j+dxs[k];
int dy=i+dys[k];
if(map[dy][dx]!='#')r2=k;
}
}
}
}
std::set<point> memos;
std::queue<point> nows;
point next,temp;
point p;
p.x=sx;
p.y=sy;
p.r=r1;
nextStopPoint(p,next);
memos.insert(next);
nows.push(next);
while(!nows.empty()){
p=nows.front();
okCheck(p);
//printf("(%d %d %s)",p.x,p.y,muki[p.r]);
if(startOK==true) break;
temp=nows.front();
nows.pop();
temp.r=(p.r+1)%4;
nextStopPoint(temp,next);
if(memos.find(next)==memos.end()){
memos.insert(next);
nows.push(next);
}
temp.r=(p.r+3)%4;
nextStopPoint(temp,next);
if(memos.find(next)==memos.end()){
memos.insert(next);
nows.push(next);
}
}
if(startOK==true){
rePoint rp;
rp.p1.x=gx;
rp.p1.y=gy;
rp.p2.x=gx;
rp.p2.y=gy;
rp.p1.r=r2;
startR=(r1+2)%4;
//printf("(r1=%d startR=%d)\n",r1,startR);
reCalc(rp,r2);
}
if(returnOK==true){
printf("He can accomplish his mission.\n");
}else if(startOK==true){
printf("He cannot return to the kitchen.\n");
}else{
printf("He cannot bring tea to his master.\n");
}
return true;
}
int main(){
while(calc()){
}
}
*2019 Princess's Marriage
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2019
お嫁入りするお姫様の護衛資金を割り振る問題。
読めば子供でも分かりますが貪欲法で十分な問題。
#include<stdio.h>
#include<vector>
#include <algorithm>
struct load{
int len,p;
bool operator<(const load& l)const{
return p>l.p;
}
};
int n,m;
void calc(){
std::vector<load> loads;
load l;
for(int i=0;i<n;i++){
scanf("%d %d",&l.len,&l.p);
loads.push_back(l);
}
std::sort(loads.begin(),loads.end());
bool last=false;
int ans=0;
for(int i=0;i<n;i++){
m-=loads[i].len;
if(m<0&&last==false){
last=true;
ans=-m*loads[i].p;
}else if(last==true){
ans+=loads[i].p*loads[i].len;
}
}
printf("%d\n",ans);
}
int main(){
while(scanf("%d %d",&n,&m)!=EOF){
if(n==0&&m==0) break;
calc();
}
}
