「AOJ1031～1040」の編集履歴（バックアップ）一覧はこちら
「AOJ1031～1040」(2012/07/19 (木) 12:16:34) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*aoj1033 Kuru-Kuru Robot
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1033
この問題はそれほど難しくはないが練習問題としてはかなりめんどくさい問題でした。
まず線分が同一直線上にあり共有部分を持つ場合、コードを単純にするために線分を統合していく必要があります。
次に、線分の交点を求めグラフに翻訳します。
後はゴールまで優先順位付きキューと幅優先探索を組み合わせれば計算量的に言って楽です。
注意点はグラフの探索中ロボは前に移動した方向と今いるポイントを覚えていく必要がある点くらいです。
他の回答者の方も同じくらいのコードサイズなので私の答えは平均的なものです。
#include<stdio.h>
#include<vector>
#include<set>
#include<math.h>
#include <algorithm>
#include<map>
#include<queue>
struct P{
double x,y;
bool operator<(const P& p)const{
if(x!=p.x)return x<p.x;
return y<p.y;
}
bool operator==(const P& p)const{
return x==p.x&&y==p.y;
}
bool operator>(const P& p)const{
if(x!=p.x)return x>p.x;
return y>p.y;
}
};
struct Line{
P p1,p2;
bool isUnion;//他の線に統合されたらtrueが設定される
};
struct cP{
double len;
int lineNo;
bool operator<(const cP& p)const{
return len<p.len;
}
};
std::vector<cP> cons[51];//線分のつながりを表す
Line lines[51];
struct robo{
int nowLine;//今いるラインNo
int nowPoint;//今いるポイントNo
double oldDX,oldDY;//一つ前に移動した移動量の向き
double cost;//回転コストの計
double len;
robo move(int nextPoint){
robo re;
double dx,dy;
dx=lines[nowLine].p2.x-lines[nowLine].p1.x;
dy=lines[nowLine].p2.y-lines[nowLine].p1.y;
//平行な線分は最初の時点ですべて取り除いているはずなので大丈夫
if(len>cons[nowLine][nextPoint].len){
dx=-dx;
dy=-dy;
}
double naiseki=dx*oldDX+dy*oldDY;
double lineLen=sqrt(dx*dx+dy*dy)*sqrt(oldDX*oldDX+oldDY*oldDY);
////printf("(len=%.3lf nai=%.3lf)",lineLen,naiseki);
if(lineLen==0){
re.cost=cost;
}else{
re.cost=cost+fabs(acos(naiseki/lineLen)/M_PI*180.0);
}
re.nowLine=cons[nowLine][nextPoint].lineNo;//次のライン
//-1は次がゴール
if(re.nowLine!=-1){
for(unsigned int i=0;i<cons[re.nowLine].size();i++){
if(nowLine==cons[re.nowLine][i].lineNo){
re.nowPoint=i;//次のポイント
break;
}
}
//次の線上での自分の位置
re.len=cons[re.nowLine][re.nowPoint].len;
}
//printf("<dx=%.3lf dy=%.3lf), ",dx,dy);
re.oldDX=dx;
re.oldDY=dy;
return re;
}
};
class costSorter {
public:
bool operator()(const robo& l, const robo& r) const {
//今いる線とポイントと向きとでチェック
return l.cost>r.cost;
}
};
class roboSorter {
public:
bool operator()(const robo& l, const robo& r) const {
//今いる線とポイントと向きとでチェック
if(l.nowPoint!=r.nowPoint)return l.nowPoint<r.nowPoint;
if(l.nowLine!=r.nowLine)return l.nowLine<r.nowLine;
if(l.oldDX!=r.oldDX)return l.oldDX<r.oldDX;
return l.oldDY<r.oldDY;
}
};
bool calcCross(Line& l1,Line& l2){
P p1,p2,p3,p4;
p1=l1.p1;
p2=l1.p2;
p3=l2.p1;
p4=l2.p2;
if (((p1.x - p2.x) * (p3.y - p1.y) + (p1.y - p2.y) * (p1.x - p3.x)) * ((p1.x - p2.x) * (p4.y - p1.y) + (p1.y - p2.y) * (p1.x - p4.x)) <= 0.0){
if(((p3.x - p4.x) * (p1.y - p3.y) + (p3.y - p4.y) * (p3.x - p1.x)) * ((p3.x - p4.x) * (p2.y - p3.y) + (p3.y - p4.y) * (p3.x - p2.x)) <= 0.0){
return true;
}
}
return false;
}
double lineInP(Line& l1,P& p3){
P p1,p2;
p1=l1.p1;
p2=l1.p2;
return (p2.y-p1.y)*(p3.x-p1.x)+p1.y*(p2.x-p1.x)-p3.y*(p2.x-p1.x);
}
void crossSet(Line& l1,Line& l2,int no1,int no2){
if(lineInP(l1,l2.p1)==0.0&&lineInP(l1,l2.p2)==0.0)return;//同じ直線上で共有部分を持たないことが判明している
if(calcCross(l1,l2)){
//printf("<%d %d>",no1,no2);
P p1,p2,p3,p4;
p1=l1.p1;
p3=l1.p2;
p2=l2.p1;
p4=l2.p2;//ばらばらなサイトを参考に組み上げたのでこのへん統一感がない
cP p;
p.lineNo=no2;
double s1=(p4.x-p2.x)*(p1.y-p2.y)-(p4.y-p2.y)*(p1.x-p2.x);
double s2=(p4.x-p2.x)*(p2.y-p3.y)-(p4.y-p2.y)*(p2.x-p3.x);
if(s1+s2==0.0){
//printf("?");
p.len=0;
}else{
double x=p1.x+(p3.x-p1.x)*s1/(s1+s2);
double y=p1.y+(p3.y-p1.y)*s1/(s1+s2);
//printf("(%lf %lf %lf)\n",x,y,s1/(s1+s2));
p.len=s1/(s1+s2);
}
cons[no1].push_back(p);
}
}
void crossUnion(Line& l1,Line& l2){
if(l1.isUnion||l2.isUnion)return ;//統合済みなので次へ
//lineの中身をp1<p2とソート
if(l1.p2<l1.p1)std::swap(l1.p1,l1.p2);
if(l2.p2<l2.p1)std::swap(l2.p1,l2.p2);
double d1=lineInP(l1,l2.p1);
double d2=lineInP(l1,l2.p2);
bool okUnion=false;
if(d1==0&&d2==0){
//両線分が平行だった
//両線分に共通部分があるかのチェック。
if(l1.p1==l2.p1 || l1.p1==l2.p2 || l1.p2==l2.p1 || l1.p2==l2.p2) okUnion=true;
if(( l1.p1<l2.p1&& l2.p1<l1.p2) || ( l1.p1<l2.p2&& l2.p2<l1.p2))okUnion=true;
}
if(okUnion==true){
//l1に統合する
l1.p1=std::min(l1.p1,l2.p1);
l1.p2=std::max(l1.p2,l2.p2);
l2.isUnion=true;//l2を使用済みに
}
}
void setData(int n){
//まずは平行で重なる線分を統合する作業
//長さ0の線分は無視する
//次にゴールを線分上に持つ線分の一覧を作る
P sp,ep;
Line l1,l2;
l1.isUnion=false;
for(int i=0;i<n;i++){
scanf("%lf %lf %lf %lf",&l1.p1.x,&l1.p1.y,&l1.p2.x,&l1.p2.y);
lines[i]=l1;
}
//まずは平行な線分を全部統合する
for(int t=0;t<n;t++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
crossUnion(lines[i],lines[j]);
}
}
}
//統合がうまくいったか確認
for(int i=0;i<n;i++){
//接合部分のリスト作り
cons[i].clear();
l1=lines[i];
////printf("(%lf %lf) (%lf %lf) %s\n",l1.p1.x,l1.p1.y,l1.p2.x,l1.p2.y,l1.isUnion?"uni":"no");
}
//線分の交点を求める
for(int i=0;i<n;i++){
if(lines[i].isUnion)continue;
for(int j=0;j<n;j++){
if(i==j || lines[j].isUnion)continue;
//統合済みの線分は無視
crossSet(lines[i],lines[j],i,j);
}
}
scanf("%lf %lf %lf %lf",&sp.x,&sp.y,&ep.x,&ep.y);
for(int i=0;i<n;i++){
if(lineInP(lines[i],ep)==0.0&&lines[i].isUnion==false){
cP p;
P p1,p2;
p1=lines[i].p1;
p2=lines[i].p2;
//長さ0の線分は無いと信じたい
if(p2.x==p1.x){
p.len=(ep.y-p1.y)/(p2.y-p1.y);
}else{
p.len=(ep.x-p1.x)/(p2.x-p1.x);
}
if(0.0<=p.len&&p.len<=1.0){
//printf("<<%d>>",i);
p.lineNo=-1;
cons[i].push_back(p);
}
}
std::sort(cons[i].begin(),cons[i].end());
}
std::map<robo,double,roboSorter> costMemo;//ロボがルート探索中過去に同じ状態でより低いコストで通ってないかのメモ
std::priority_queue<robo,std::vector<robo>,costSorter> roboQ;
robo r,nextR;
r.cost=0;
r.oldDX=r.oldDY=0.0;
r.nowPoint=0;
for(int i=0;i<n;i++){
r.nowLine=i;
if(lineInP(lines[i],sp)==0.0&&lines[i].isUnion==false){
//スタート地点の候補
P p1,p2;
p1=lines[i].p1;
p2=lines[i].p2;
if(p2.x==p1.x){
r.len=(sp.y-p1.y)/(p2.y-p1.y);
}else{
r.len=(sp.x-p1.x)/(p2.x-p1.x);
}
if(0.0<=r.len&&r.len<=1.0){
//線分の間にスタート地点があった
//printf("<<%d>>",i);
roboQ.push(r);
costMemo[r]=0.0;
}
}
}
r.nowLine=100;//適当な数を入れる
while(!roboQ.empty()){
r=roboQ.top();
roboQ.pop();
//printf("\n<?%d %lf %lf %lf>,",r.nowLine,r.cost,r.oldDX,r.oldDY);
if(r.nowLine==-1)break;
for(unsigned int i=0;i<cons[r.nowLine].size();i++){
nextR=r.move(i);
if(costMemo.find(nextR)==costMemo.end()){
costMemo[nextR]=nextR.cost;
roboQ.push(nextR);
}else if(costMemo[nextR]>nextR.cost){
costMemo[nextR]=nextR.cost;
roboQ.push(nextR);
}
}
}
if(r.nowLine==-1)printf("%.8lf\n",r.cost);
else printf("-1\n");
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
setData(n);
}
}
*1036
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1036
工場のラインの動作結果から反対のラインに並んだ商品を逆算する問題。
簡単な問題のはずなのに妙に悩んでしまった。
現実のラインだったら色々な理由で順番が変わるけど、これは練習問題なのでそういったことを考慮しなくていいのが楽だな。
#include<stdio.h>
#include<vector>
bool setData(){
char gu[100],gl[100],gd[100];
std::vector<char> ans;
int p1,p2;
p1=p2=0;
scanf("%s",gu);
if(gu[0]=='-')return false;
scanf("%s %s",gl,gd);
char t;
int oldMove,down=0,right=1;
oldMove=right;
for(int i=0;gd[i]!='\0'||gu[p1]!='\0'||gl[p2]!='\0';){
t=gd[i];
if(oldMove==down){
if(gu[p1]==t&&t!='\0'){
p1++;
i++;
}else{
oldMove=right;
if(gu[p1]=='\0') continue;
printf("%c",gu[p1]);
p1++;
}
}else{
if(gl[p2]==t&&t!='\0'){
p2++;
i++;
oldMove=down;
}else{
if(gl[p2]=='\0'){
oldMove=down;
continue;
}
printf("%c",gl[p2]);
p2++;
}
}
}
printf("\n");
return true;
}
int main(){
while(setData()){
}
}
----
*1037 Midnight Teatime
木構造を利用した問題。
枝先にお菓子のセット、枝ごとにお菓子のセットのAnd Or Xorを計算して根元まで計算する。
組み合わせ数が少ないことを利用して全探索で解いてみた。
ほとんどの人がもう少し速度で解いているので正しい解き方は全探索ではないのかも？
#include<stdio.h>
int cakeSets[10];//色々計算して最後に下4ビットだけを使う
int mask=15;//下位4ビットマスク
int ans;
int calcNode(int& p,const char* nodeText,bool modeRe){
int nowSet=0;
p++;
while(1){
char t=nodeText[p];
if('1'<=t && t<='9'){
nowSet=cakeSets[t-'0'];
}else if(t=='A'){
nowSet&=calcNode(p,nodeText,true);
}else if(t=='O'){
nowSet|=calcNode(p,nodeText,true);
}else if(t=='X'){
nowSet^=calcNode(p,nodeText,true);
}else if(t=='('){
nowSet=calcNode(p,nodeText,false);
}else{
return nowSet;
}
if(modeRe==true) return nowSet;
p++;
}
}
void setNode(int p,char* nodeText){
char t=nodeText[p];
if(t=='\0'){
int np=-1;
//printf("%s=",nodeText);
int k=calcNode(np,nodeText,true);
//printf("%d %d %d %d\n",(k&1)!=0?1:0,(k&2)!=0?1:0,(k&4)!=0?1:0,(k&8)!=0?1:0);
if(mask==(mask&k)){
ans++;
}
}else if(t==' '){
nodeText[p]='A';
setNode(p+1,nodeText);
nodeText[p]='O';
setNode(p+1,nodeText);
nodeText[p]='X';
setNode(p+1,nodeText);
nodeText[p]=' ';
}else {
setNode(p+1,nodeText);
}
}
bool setData(){
char nodeText[200],re;
int p;
ans=0;
scanf("%[^\n]%c",nodeText,&re);
if(nodeText[0]=='E')return false;
int n,c;
scanf("%d",&n);
for(int i=1;i<=n;i++){
cakeSets[i]=0;
for(int j=0;j<4;j++){
scanf("%d",&c);
cakeSets[i]|=(c<<j);
}
}
setNode(0,nodeText);
printf("%d\n",ans);
if(scanf("%c",&re)==EOF)return false;
return true;
}
int main(){
while(setData()){
}
}
*1038 Dr. Nakamura's Lab.
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1038
ドクター中村がパズルになった防犯システムをすりぬけてゴールまで辿り着く最短歩数を答える問題。
一ます移動するとき移動先が壁、漏電床なら移動禁止。
コンテナの次が壁、コンテナの次がコンテナも移動禁止。
コンテナ移動時は一ます移動するごとに壁にあたらないか、漏電床にあたってきえないか、別のコンテナにぶつかって止まらないかをチェックする必要がありこの部分が少し複雑。
この問題最大のひっかけは倉庫番を知ってるか知らないかである。
実は問題文を丁寧によく読むと、ドクター中松はコンテナのあるマスに入れないと書いてある。
つまりコンテナのあるマスに侵入するには一歩も動かずにコンテナを押して、その後でコンテナのあるマスに侵入しなくてはいけないわけだ。
実質２手なのである。
倉庫番を知っている人だとコンテナを押すと、中松もコンテナのあったマスに入ってしまうという先入観を持つことになる。
これでひっか勝てる人が非常に多いと思う。
#include<stdio.h>
#include<queue>
#include <algorithm>
#include<set>
char map[11][11];
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
struct box{
int x,y;
bool operator<(const box& b)const{
if(x!=b.x)return x<b.x;
return y<b.y;
}
bool operator!=(const box& b)const{
return x!=b.x||y!=b.y;
}
};
struct state{
box boxs[3];
box eFloor[3];
int x,y,len;//中村の位置
bool operator<(const state& s)const{
if(x!=s.x)return x<s.x;
if(y!=s.y)return y<s.y;
for(int i=0;i<3;i++){
if(boxs[i]!=s.boxs[i])return boxs[i]<s.boxs[i];
if(eFloor[i]!=s.eFloor[i])return eFloor[i]<s.eFloor[i];
}
return false;
}
state move(int arrow){
state s;
s.len=len+1;
s.x=x;
s.y=y;
for(int i=0;i<3;i++){
s.boxs[i]=boxs[i];
s.eFloor[i]=eFloor[i];
}
//まず中村の移動が可能か
int nx1=x+dxs[arrow];
int ny1=y+dys[arrow];
int nx2=x+2*dxs[arrow];
int ny2=y+2*dys[arrow];
//移動先が壁
if(map[ny1][nx1]=='#'){
return s;
}
//移動先が漏電床で移動できない
for(int i=0;i<3;i++){
if(nx1==eFloor[i].x&&ny1==eFloor[i].y)return s;
}
//移動先がボックス、壁で移動できない
if(map[ny2][nx2]=='#'){
for(int i=0;i<3;i++){
if(nx1==boxs[i].x&&ny1==boxs[i].y)return s;
}
}
//移動先がボックスボックスで移動できない
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(nx1==boxs[i].x&&ny1==boxs[i].y&&
nx2==boxs[j].x&&ny2==boxs[j].y)return s;
}
}
//移動が出来た
int moveNo=-1;
//押したボックスの番号を取得
for(int i=0;i<3;i++){
if(nx1==boxs[i].x&&ny1==boxs[i].y){
moveNo=i;
break;
}
}
if(moveNo==-1){
//移動先がボックスがなかったので
s.x=nx1;
s.y=ny1;
return s;
}
//移動しようとした先がボックスがあったのでボックスだけ押す
//中村自身は移動しない
s.len=len;
box b=boxs[moveNo];
bool boxStop=false;
for(int i=1;i<11;i++){
int nx=b.x+i*dxs[arrow];
int ny=b.y+i*dys[arrow];
if(map[ny][nx]=='#'){
//壁にあたった
b.x=b.x+(i-1)*dxs[arrow];
b.y=b.y+(i-1)*dys[arrow];
break;
}
for(int j=0;j<3;j++){
if(nx==boxs[j].x&&ny==boxs[j].y){
//ボックスにあたった
b.x=b.x+(i-1)*dxs[arrow];
b.y=b.y+(i-1)*dys[arrow];
boxStop=true;
break;
}
}
if(boxStop==true)break;
for(int j=0;j<3;j++){
if(nx==eFloor[j].x&&ny==eFloor[j].y){
//漏電床にあたった
//ボックスと床の消去
s.eFloor[j].x=s.eFloor[j].y=-1;
b.x=-1;
b.y=-1;
boxStop=true;
break;
}
}
if(boxStop==true)break;
}
//ボックスの移動終了
//状況を簡単にするためにソート。
s.boxs[moveNo]=b;
std::sort(s.boxs,s.boxs+3);
std::sort(s.eFloor,s.eFloor+3);
return s;
}
};
void calc(int h,int w){
state s,nextS;
std::queue<state> states;
std::set<state> memo;
int cC=0,wC=0,gx,gy;
//初期化
for(int i=0;i<3;i++){
s.boxs[i].y=s.boxs[i].y=-1;
s.eFloor[i].y=s.eFloor[i].y=-1;
}
s.len=0;
for(int r=0;r<h;r++){
scanf("%s",&map[r]);
for(int x=0;x<w;x++){
char c=map[r][x];
if(c=='w'){
s.eFloor[wC].x=x;
s.eFloor[wC].y=r;
wC++;
}else if(c=='c'){
s.boxs[cC].y=r;
s.boxs[cC].x=x;
cC++;
}else if(c=='@'){
s.y=r;
s.x=x;
}else if(c=='E'){
gx=x;
gy=r;
}
}
}
std::sort(s.boxs,s.boxs+3);
std::sort(s.eFloor,s.eFloor+3);
states.push(s);
memo.insert(s);
bool clearOK=false;
while(states.empty()==false){
s=states.front();
states.pop();
if(s.x==gx&&s.y==gy){
clearOK=true;
break;
}
for(int i=0;i<4;i++){
nextS=s.move(i);
if(memo.find(nextS)==memo.end()){
memo.insert(nextS);
states.push(nextS);
}
}
}
if(clearOK==true){
printf("%d\n",s.len);
}else{
printf("-1\n");
}
}
int main(){
int h,w;
while(1){
scanf("%d %d",&h,&w);
if(h==0&&w==0)break;
calc(h,w);
}
}
*aoj1033 Kuru-Kuru Robot
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1033
この問題はそれほど難しくはないが練習問題としてはかなりめんどくさい問題でした。
まず線分が同一直線上にあり共有部分を持つ場合、コードを単純にするために線分を統合していく必要があります。
次に、線分の交点を求めグラフに翻訳します。
後はゴールまで優先順位付きキューと幅優先探索を組み合わせれば計算量的に言って楽です。
注意点はグラフの探索中ロボは前に移動した方向と今いるポイントを覚えていく必要がある点くらいです。
他の回答者の方も同じくらいのコードサイズなので私の答えは平均的なものです。
#include<stdio.h>
#include<vector>
#include<set>
#include<math.h>
#include <algorithm>
#include<map>
#include<queue>
struct P{
double x,y;
bool operator<(const P& p)const{
if(x!=p.x)return x<p.x;
return y<p.y;
}
bool operator==(const P& p)const{
return x==p.x&&y==p.y;
}
bool operator>(const P& p)const{
if(x!=p.x)return x>p.x;
return y>p.y;
}
};
struct Line{
P p1,p2;
bool isUnion;//他の線に統合されたらtrueが設定される
};
struct cP{
double len;
int lineNo;
bool operator<(const cP& p)const{
return len<p.len;
}
};
std::vector<cP> cons[51];//線分のつながりを表す
Line lines[51];
struct robo{
int nowLine;//今いるラインNo
int nowPoint;//今いるポイントNo
double oldDX,oldDY;//一つ前に移動した移動量の向き
double cost;//回転コストの計
double len;
robo move(int nextPoint){
robo re;
double dx,dy;
dx=lines[nowLine].p2.x-lines[nowLine].p1.x;
dy=lines[nowLine].p2.y-lines[nowLine].p1.y;
//平行な線分は最初の時点ですべて取り除いているはずなので大丈夫
if(len>cons[nowLine][nextPoint].len){
dx=-dx;
dy=-dy;
}
double naiseki=dx*oldDX+dy*oldDY;
double lineLen=sqrt(dx*dx+dy*dy)*sqrt(oldDX*oldDX+oldDY*oldDY);
////printf("(len=%.3lf nai=%.3lf)",lineLen,naiseki);
if(lineLen==0){
re.cost=cost;
}else{
re.cost=cost+fabs(acos(naiseki/lineLen)/M_PI*180.0);
}
re.nowLine=cons[nowLine][nextPoint].lineNo;//次のライン
//-1は次がゴール
if(re.nowLine!=-1){
for(unsigned int i=0;i<cons[re.nowLine].size();i++){
if(nowLine==cons[re.nowLine][i].lineNo){
re.nowPoint=i;//次のポイント
break;
}
}
//次の線上での自分の位置
re.len=cons[re.nowLine][re.nowPoint].len;
}
//printf("<dx=%.3lf dy=%.3lf), ",dx,dy);
re.oldDX=dx;
re.oldDY=dy;
return re;
}
};
class costSorter {
public:
bool operator()(const robo& l, const robo& r) const {
//今いる線とポイントと向きとでチェック
return l.cost>r.cost;
}
};
class roboSorter {
public:
bool operator()(const robo& l, const robo& r) const {
//今いる線とポイントと向きとでチェック
if(l.nowPoint!=r.nowPoint)return l.nowPoint<r.nowPoint;
if(l.nowLine!=r.nowLine)return l.nowLine<r.nowLine;
if(l.oldDX!=r.oldDX)return l.oldDX<r.oldDX;
return l.oldDY<r.oldDY;
}
};
bool calcCross(Line& l1,Line& l2){
P p1,p2,p3,p4;
p1=l1.p1;
p2=l1.p2;
p3=l2.p1;
p4=l2.p2;
if (((p1.x - p2.x) * (p3.y - p1.y) + (p1.y - p2.y) * (p1.x - p3.x)) * ((p1.x - p2.x) * (p4.y - p1.y) + (p1.y - p2.y) * (p1.x - p4.x)) <= 0.0){
if(((p3.x - p4.x) * (p1.y - p3.y) + (p3.y - p4.y) * (p3.x - p1.x)) * ((p3.x - p4.x) * (p2.y - p3.y) + (p3.y - p4.y) * (p3.x - p2.x)) <= 0.0){
return true;
}
}
return false;
}
double lineInP(Line& l1,P& p3){
P p1,p2;
p1=l1.p1;
p2=l1.p2;
return (p2.y-p1.y)*(p3.x-p1.x)+p1.y*(p2.x-p1.x)-p3.y*(p2.x-p1.x);
}
void crossSet(Line& l1,Line& l2,int no1,int no2){
if(lineInP(l1,l2.p1)==0.0&&lineInP(l1,l2.p2)==0.0)return;//同じ直線上で共有部分を持たないことが判明している
if(calcCross(l1,l2)){
//printf("<%d %d>",no1,no2);
P p1,p2,p3,p4;
p1=l1.p1;
p3=l1.p2;
p2=l2.p1;
p4=l2.p2;//ばらばらなサイトを参考に組み上げたのでこのへん統一感がない
cP p;
p.lineNo=no2;
double s1=(p4.x-p2.x)*(p1.y-p2.y)-(p4.y-p2.y)*(p1.x-p2.x);
double s2=(p4.x-p2.x)*(p2.y-p3.y)-(p4.y-p2.y)*(p2.x-p3.x);
if(s1+s2==0.0){
//printf("?");
p.len=0;
}else{
double x=p1.x+(p3.x-p1.x)*s1/(s1+s2);
double y=p1.y+(p3.y-p1.y)*s1/(s1+s2);
//printf("(%lf %lf %lf)\n",x,y,s1/(s1+s2));
p.len=s1/(s1+s2);
}
cons[no1].push_back(p);
}
}
void crossUnion(Line& l1,Line& l2){
if(l1.isUnion||l2.isUnion)return ;//統合済みなので次へ
//lineの中身をp1<p2とソート
if(l1.p2<l1.p1)std::swap(l1.p1,l1.p2);
if(l2.p2<l2.p1)std::swap(l2.p1,l2.p2);
double d1=lineInP(l1,l2.p1);
double d2=lineInP(l1,l2.p2);
bool okUnion=false;
if(d1==0&&d2==0){
//両線分が平行だった
//両線分に共通部分があるかのチェック。
if(l1.p1==l2.p1 || l1.p1==l2.p2 || l1.p2==l2.p1 || l1.p2==l2.p2) okUnion=true;
if(( l1.p1<l2.p1&& l2.p1<l1.p2) || ( l1.p1<l2.p2&& l2.p2<l1.p2))okUnion=true;
}
if(okUnion==true){
//l1に統合する
l1.p1=std::min(l1.p1,l2.p1);
l1.p2=std::max(l1.p2,l2.p2);
l2.isUnion=true;//l2を使用済みに
}
}
void setData(int n){
//まずは平行で重なる線分を統合する作業
//長さ0の線分は無視する
//次にゴールを線分上に持つ線分の一覧を作る
P sp,ep;
Line l1,l2;
l1.isUnion=false;
for(int i=0;i<n;i++){
scanf("%lf %lf %lf %lf",&l1.p1.x,&l1.p1.y,&l1.p2.x,&l1.p2.y);
lines[i]=l1;
}
//まずは平行な線分を全部統合する
for(int t=0;t<n;t++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
crossUnion(lines[i],lines[j]);
}
}
}
//統合がうまくいったか確認
for(int i=0;i<n;i++){
//接合部分のリスト作り
cons[i].clear();
l1=lines[i];
////printf("(%lf %lf) (%lf %lf) %s\n",l1.p1.x,l1.p1.y,l1.p2.x,l1.p2.y,l1.isUnion?"uni":"no");
}
//線分の交点を求める
for(int i=0;i<n;i++){
if(lines[i].isUnion)continue;
for(int j=0;j<n;j++){
if(i==j || lines[j].isUnion)continue;
//統合済みの線分は無視
crossSet(lines[i],lines[j],i,j);
}
}
scanf("%lf %lf %lf %lf",&sp.x,&sp.y,&ep.x,&ep.y);
for(int i=0;i<n;i++){
if(lineInP(lines[i],ep)==0.0&&lines[i].isUnion==false){
cP p;
P p1,p2;
p1=lines[i].p1;
p2=lines[i].p2;
//長さ0の線分は無いと信じたい
if(p2.x==p1.x){
p.len=(ep.y-p1.y)/(p2.y-p1.y);
}else{
p.len=(ep.x-p1.x)/(p2.x-p1.x);
}
if(0.0<=p.len&&p.len<=1.0){
//printf("<<%d>>",i);
p.lineNo=-1;
cons[i].push_back(p);
}
}
std::sort(cons[i].begin(),cons[i].end());
}
std::map<robo,double,roboSorter> costMemo;//ロボがルート探索中過去に同じ状態でより低いコストで通ってないかのメモ
std::priority_queue<robo,std::vector<robo>,costSorter> roboQ;
robo r,nextR;
r.cost=0;
r.oldDX=r.oldDY=0.0;
r.nowPoint=0;
for(int i=0;i<n;i++){
r.nowLine=i;
if(lineInP(lines[i],sp)==0.0&&lines[i].isUnion==false){
//スタート地点の候補
P p1,p2;
p1=lines[i].p1;
p2=lines[i].p2;
if(p2.x==p1.x){
r.len=(sp.y-p1.y)/(p2.y-p1.y);
}else{
r.len=(sp.x-p1.x)/(p2.x-p1.x);
}
if(0.0<=r.len&&r.len<=1.0){
//線分の間にスタート地点があった
//printf("<<%d>>",i);
roboQ.push(r);
costMemo[r]=0.0;
}
}
}
r.nowLine=100;//適当な数を入れる
while(!roboQ.empty()){
r=roboQ.top();
roboQ.pop();
//printf("\n<?%d %lf %lf %lf>,",r.nowLine,r.cost,r.oldDX,r.oldDY);
if(r.nowLine==-1)break;
for(unsigned int i=0;i<cons[r.nowLine].size();i++){
nextR=r.move(i);
if(costMemo.find(nextR)==costMemo.end()){
costMemo[nextR]=nextR.cost;
roboQ.push(nextR);
}else if(costMemo[nextR]>nextR.cost){
costMemo[nextR]=nextR.cost;
roboQ.push(nextR);
}
}
}
if(r.nowLine==-1)printf("%.8lf\n",r.cost);
else printf("-1\n");
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
setData(n);
}
}
*1036
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1036
工場のラインの動作結果から反対のラインに並んだ商品を逆算する問題。
簡単な問題のはずなのに妙に悩んでしまった。
現実のラインだったら色々な理由で順番が変わるけど、これは練習問題なのでそういったことを考慮しなくていいのが楽だな。
#include<stdio.h>
#include<vector>
bool setData(){
char gu[100],gl[100],gd[100];
std::vector<char> ans;
int p1,p2;
p1=p2=0;
scanf("%s",gu);
if(gu[0]=='-')return false;
scanf("%s %s",gl,gd);
char t;
int oldMove,down=0,right=1;
oldMove=right;
for(int i=0;gd[i]!='\0'||gu[p1]!='\0'||gl[p2]!='\0';){
t=gd[i];
if(oldMove==down){
if(gu[p1]==t&&t!='\0'){
p1++;
i++;
}else{
oldMove=right;
if(gu[p1]=='\0') continue;
printf("%c",gu[p1]);
p1++;
}
}else{
if(gl[p2]==t&&t!='\0'){
p2++;
i++;
oldMove=down;
}else{
if(gl[p2]=='\0'){
oldMove=down;
continue;
}
printf("%c",gl[p2]);
p2++;
}
}
}
printf("\n");
return true;
}
int main(){
while(setData()){
}
}
----
*1037 Midnight Teatime
木構造を利用した問題。
枝先にお菓子のセット、枝ごとにお菓子のセットのAnd Or Xorを計算して根元まで計算する。
組み合わせ数が少ないことを利用して全探索で解いてみた。
ほとんどの人がもう少し速度で解いているので正しい解き方は全探索ではないのかも？
#include<stdio.h>
int cakeSets[10];//色々計算して最後に下4ビットだけを使う
int mask=15;//下位4ビットマスク
int ans;
int calcNode(int& p,const char* nodeText,bool modeRe){
int nowSet=0;
p++;
while(1){
char t=nodeText[p];
if('1'<=t && t<='9'){
nowSet=cakeSets[t-'0'];
}else if(t=='A'){
nowSet&=calcNode(p,nodeText,true);
}else if(t=='O'){
nowSet|=calcNode(p,nodeText,true);
}else if(t=='X'){
nowSet^=calcNode(p,nodeText,true);
}else if(t=='('){
nowSet=calcNode(p,nodeText,false);
}else{
return nowSet;
}
if(modeRe==true) return nowSet;
p++;
}
}
void setNode(int p,char* nodeText){
char t=nodeText[p];
if(t=='\0'){
int np=-1;
//printf("%s=",nodeText);
int k=calcNode(np,nodeText,true);
//printf("%d %d %d %d\n",(k&1)!=0?1:0,(k&2)!=0?1:0,(k&4)!=0?1:0,(k&8)!=0?1:0);
if(mask==(mask&k)){
ans++;
}
}else if(t==' '){
nodeText[p]='A';
setNode(p+1,nodeText);
nodeText[p]='O';
setNode(p+1,nodeText);
nodeText[p]='X';
setNode(p+1,nodeText);
nodeText[p]=' ';
}else {
setNode(p+1,nodeText);
}
}
bool setData(){
char nodeText[200],re;
int p;
ans=0;
scanf("%[^\n]%c",nodeText,&re);
if(nodeText[0]=='E')return false;
int n,c;
scanf("%d",&n);
for(int i=1;i<=n;i++){
cakeSets[i]=0;
for(int j=0;j<4;j++){
scanf("%d",&c);
cakeSets[i]|=(c<<j);
}
}
setNode(0,nodeText);
printf("%d\n",ans);
if(scanf("%c",&re)==EOF)return false;
return true;
}
int main(){
while(setData()){
}
}
*1038 Dr. Nakamura's Lab.
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1038
ドクター中村がパズルになった防犯システムをすりぬけてゴールまで辿り着く最短歩数を答える問題。
一ます移動するとき移動先が壁、漏電床なら移動禁止。
コンテナの次が壁、コンテナの次がコンテナも移動禁止。
コンテナ移動時は一ます移動するごとに壁にあたらないか、漏電床にあたってきえないか、別のコンテナにぶつかって止まらないかをチェックする必要がありこの部分が少し複雑。
この問題最大のひっかけは倉庫番を知ってるか知らないかである。
実は問題文を丁寧によく読むと、ドクター中松はコンテナのあるマスに入れないと書いてある。
つまりコンテナのあるマスに侵入するには一歩も動かずにコンテナを押して、その後でコンテナのあるマスに侵入しなくてはいけないわけだ。
実質２手なのである。
倉庫番を知っている人だとコンテナを押すと、中松もコンテナのあったマスに入ってしまうという先入観を持つことになる。
これでひっか勝てる人が非常に多いと思う。
#include<stdio.h>
#include<queue>
#include <algorithm>
#include<set>
char map[11][11];
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
struct box{
int x,y;
bool operator<(const box& b)const{
if(x!=b.x)return x<b.x;
return y<b.y;
}
bool operator!=(const box& b)const{
return x!=b.x||y!=b.y;
}
};
struct state{
box boxs[3];
box eFloor[3];
int x,y,len;//中村の位置
bool operator<(const state& s)const{
if(x!=s.x)return x<s.x;
if(y!=s.y)return y<s.y;
for(int i=0;i<3;i++){
if(boxs[i]!=s.boxs[i])return boxs[i]<s.boxs[i];
if(eFloor[i]!=s.eFloor[i])return eFloor[i]<s.eFloor[i];
}
return false;
}
state move(int arrow){
state s;
s.len=len+1;
s.x=x;
s.y=y;
for(int i=0;i<3;i++){
s.boxs[i]=boxs[i];
s.eFloor[i]=eFloor[i];
}
//まず中村の移動が可能か
int nx1=x+dxs[arrow];
int ny1=y+dys[arrow];
int nx2=x+2*dxs[arrow];
int ny2=y+2*dys[arrow];
//移動先が壁
if(map[ny1][nx1]=='#'){
return s;
}
//移動先が漏電床で移動できない
for(int i=0;i<3;i++){
if(nx1==eFloor[i].x&&ny1==eFloor[i].y)return s;
}
//移動先がボックス、壁で移動できない
if(map[ny2][nx2]=='#'){
for(int i=0;i<3;i++){
if(nx1==boxs[i].x&&ny1==boxs[i].y)return s;
}
}
//移動先がボックスボックスで移動できない
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(nx1==boxs[i].x&&ny1==boxs[i].y&&
nx2==boxs[j].x&&ny2==boxs[j].y)return s;
}
}
//移動が出来た
int moveNo=-1;
//押したボックスの番号を取得
for(int i=0;i<3;i++){
if(nx1==boxs[i].x&&ny1==boxs[i].y){
moveNo=i;
break;
}
}
if(moveNo==-1){
//移動先がボックスがなかったので
s.x=nx1;
s.y=ny1;
return s;
}
//移動しようとした先がボックスがあったのでボックスだけ押す
//中村自身は移動しない
s.len=len;
box b=boxs[moveNo];
bool boxStop=false;
for(int i=1;i<11;i++){
int nx=b.x+i*dxs[arrow];
int ny=b.y+i*dys[arrow];
if(map[ny][nx]=='#'){
//壁にあたった
b.x=b.x+(i-1)*dxs[arrow];
b.y=b.y+(i-1)*dys[arrow];
break;
}
for(int j=0;j<3;j++){
if(nx==boxs[j].x&&ny==boxs[j].y){
//ボックスにあたった
b.x=b.x+(i-1)*dxs[arrow];
b.y=b.y+(i-1)*dys[arrow];
boxStop=true;
break;
}
}
if(boxStop==true)break;
for(int j=0;j<3;j++){
if(nx==eFloor[j].x&&ny==eFloor[j].y){
//漏電床にあたった
//ボックスと床の消去
s.eFloor[j].x=s.eFloor[j].y=-1;
b.x=-1;
b.y=-1;
boxStop=true;
break;
}
}
if(boxStop==true)break;
}
//ボックスの移動終了
//状況を簡単にするためにソート。
s.boxs[moveNo]=b;
std::sort(s.boxs,s.boxs+3);
std::sort(s.eFloor,s.eFloor+3);
return s;
}
};
void calc(int h,int w){
state s,nextS;
std::queue<state> states;
std::set<state> memo;
int cC=0,wC=0,gx,gy;
//初期化
for(int i=0;i<3;i++){
s.boxs[i].y=s.boxs[i].y=-1;
s.eFloor[i].y=s.eFloor[i].y=-1;
}
s.len=0;
for(int r=0;r<h;r++){
scanf("%s",&map[r]);
for(int x=0;x<w;x++){
char c=map[r][x];
if(c=='w'){
s.eFloor[wC].x=x;
s.eFloor[wC].y=r;
wC++;
}else if(c=='c'){
s.boxs[cC].y=r;
s.boxs[cC].x=x;
cC++;
}else if(c=='@'){
s.y=r;
s.x=x;
}else if(c=='E'){
gx=x;
gy=r;
}
}
}
std::sort(s.boxs,s.boxs+3);
std::sort(s.eFloor,s.eFloor+3);
states.push(s);
memo.insert(s);
bool clearOK=false;
while(states.empty()==false){
s=states.front();
states.pop();
if(s.x==gx&&s.y==gy){
clearOK=true;
break;
}
for(int i=0;i<4;i++){
nextS=s.move(i);
if(memo.find(nextS)==memo.end()){
memo.insert(nextS);
states.push(nextS);
}
}
}
if(clearOK==true){
printf("%d\n",s.len);
}else{
printf("-1\n");
}
}
int main(){
int h,w;
while(1){
scanf("%d %d",&h,&w);
if(h==0&&w==0)break;
calc(h,w);
}
}
*1039 Frisbee Dogs
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1039
フリスビー大会を模したミニゲームの結果をシミュレートする問題です。
解法
この問題はベクトルで解きます。
フリスビーの発射位置を原点とし各犬の位置を計算します。
発射速度と犬の速度でベクトル計算を行い取得可能時刻を計算し、0以上なら記録します。
２次方程式の解の公式(-b+sqrt(b^2-4ac))/2aを使い取得時刻を計算しますがa=0でも答えがある場合が要注意です。
a==0は犬とフリスビーの速度が同じ時で、この時、犬の位置ベクトルとフリスビーのなす角が９０度以内なら２と右辺三角をなしてフリスビーを取得できる可能性が残っているのでそれを忘れずに計算式に組み込みます。
何も考えず数学の教科書通り実装しましましたが、何の工夫もしてないのに何故かコード実行速度１位を取れてしまいました。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
void setData(int n,int m){
double dogXs[12],dogYs[12],dogRs[12];//犬の位置、速度
double dogXs2[12],dogYs2[12];//フリスビーの発射位置を原点とした座標
double times[12];//犬の移動距離と移動タイム、これが0以下なら移動禁止
double fx,fy,sx,sy;//フリスビーの発射向きと発射位置
double a,b,c,timeS;//フリスビー取得タイムの計算用
int ans[12],getNo;//フリスビーをゲットした犬の番号
memset(ans,0,sizeof(ans));
for(int i=0;i<n;i++){
scanf("%lf %lf %lf",&dogXs[i],&dogYs[i],&dogRs[i]);
}
while(m--){
scanf("%lf %lf %lf %lf",&sx,&sy,&fx,&fy);
timeS=-1;
for(int i=0;i<n;i++){
dogXs2[i]=dogXs[i]-sx;
dogYs2[i]=dogYs[i]-sy;
a=fx*fx+fy*fy-dogRs[i]*dogRs[i];
b=-2*dogXs2[i]*fx-2*dogYs2[i]*fy;
c=dogXs2[i]*dogXs2[i]+dogYs2[i]*dogYs2[i];
double temp=b*b-4*a*c;
if(a==0){
//フリスビーと犬が同じ速度
temp=fx*dogXs2[i]+fy*dogYs2[i];
if(temp>0){
//内積が0以上、つまり犬の位置とフリスビーの向きのなす角が９０度以下ならゲットできる
double v1 =sqrt(fx*fx+fy*fy);
double len1=sqrt(dogXs2[i]*dogXs2[i]+dogYs2[i]*dogYs2[i]);
double cos1=temp/(len1*v1);
times[i]=len1/(2.0*v1*cos1);//犬とフリスビーの動きは二等辺三角になる
}else{
times[i]=-1;
}
}else if(temp<0){
times[i]=-1;
}else{
//ゲットタイムを計算
double time1=(-b-sqrt(temp))/(2*a);
double time2=(-b+sqrt(temp))/(2*a);
if(time1>=0){
times[i]=time1;
}else if(time2>=0){
times[i]=time2;
}else{
times[i]=-1;
}
}
if(timeS==-1||timeS>times[i]&×[i]>0){
getNo=i;
timeS=times[i];
}
}
ans[getNo]++;
for(int i=0;i<n;i++){
if(times[i]>0){
//タイム1e-6以前に取得できる犬はいないという記述に従う
dogXs[i]=dogXs2[i]+(times[i]*fx-dogXs2[i])*timeS/times[i]+sx;
dogYs[i]=dogYs2[i]+(times[i]*fy-dogYs2[i])*timeS/times[i]+sy;
}
}
}
for(int i=0;i<n;i++)printf("%s%d",i==0?"":" ",ans[i]);
printf("\n");
}
int main(){
int n,m;
while(1){
scanf("%d %d",&n,&m);
if(n==0&&m==0)break;
setData(n,m);
}
}
