aoj2491～2500 - c21coterie @ ウィキ

堀江伸一
〒675-0033-79-16

aoj2491 sanpo

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2491
ねこのそらの散歩を題材にした問題。

解法
正答者数も少なく難しい問題です。
普通に探索しては小さなグラフでも間に合いません。
道を通った回数、今いる地点、残り時間の３種類を基準に点をプロットし、グラフとして素朴な動的計画法で解こうととすると点の数が膨大になります。

この問題はすこし変わった方法で解けそうです。
1番にタイムとそのタイムで得られる最大の価値の対応表を持った猫を待機させます。
その猫からどれかの道にむけて対応表を持たせて架空の探索猫を１匹先行させます。
探索猫は枝先でないならついた広場で待機し親猫となり、さらに子となる探索猫を一匹出します。
探索猫が枝先の広場にいるなら、その広場に至る道を何度か往復してこのタイムならこれだけの価値が得られるという情報の一覧を親猫に持ち帰ります。
その結果より良い結果があれば親猫はタイムと価値の対応表を更新します。
更新したタイムと価値の対応表を持たせて自分の持ち場の次の枝に探索猫を出します。
親猫は自分の持ち場の全ての道で探索猫の結果を習得したら親猫は自分の親猫に対応表を返していけば答えが出ます。
後はスピードを上げるために往復の検証順序を価値の高い順にソートしておきます。

#include<stdio.h>
#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<string.h>
#include<algorithm>
struct Way{
	int to;
	long long int t,m,v;
};
struct S{ 
	 long long int v,t;
	bool operator<(const S& s)const{
		return t>s.t;
	}
};

const int size=301;
const int tMax=10001;

std::vector<Way> G[size];
long long int values[size][tMax];
void saiki(int parent,int now,Way w1,int T){
	int t1;
	long long int v1;
	if(parent!=0){
		std::vector<S> tempV;
		S s1;
		for(int i=0;i<=T;i+=2){
			s1.t=i;
			s1.v=values[parent][i];
			if(s1.v!=-1)tempV.push_back(s1);
		}
		std::sort(tempV.begin(),tempV.end());
		for(int i=0;i<tempV.size();i++){
			long long int baseV=tempV[i].v;
			for(long long int j=2;j<=w1.m+1+(w1.m==0);j+=2){
				t1=j*w1.t+tempV[i].t;
				if(t1>T)break;
 				v1=(j>=w1.m?w1.m:j)*w1.v+baseV;
				if(values[now][t1]<v1)values[now][t1]=v1;
				else break;
			}
		}
	}
	for(int i=0;i<G[now].size();i++){
		w1=G[now][i];
		if(parent!=w1.to){
			saiki(now,w1.to,w1,T);
			for(int j=0;j<=T;j++){
				if(values[now][j]<values[w1.to][j])values[now][j]=values[w1.to][j];
			}
		}
	}
}
 
int main(){
	int N,T,a,b;
	Way w1;
	long long int t1,m1;
	memset(values,-1,sizeof(values));
	
	scanf("%d %d",&N,&T);
	T=T-T%2;
	for(int i=0;i<N-1;i++){
		scanf("%d %d",&a,&b);
		std::cin>>w1.t>>w1.m>>w1.v;
		w1.to=b;
		G[a].push_back(w1);
		w1.to=a;
		G[b].push_back(w1);
	}
	values[1][0]=0;
	saiki(0,1,w1,T);
	long long int ans=0;
	for(int i=0;i<=T;i+=2){
		if(values[1][i]>ans)ans=values[1][i];
 	}
std::cout<<ans<<"\n";
}   

aoj2492　goto busters

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2492
goto文とラベルだけからなるプログラムコードが与えられる。
ソースが無限ループにならないようgoto文を削除したいが、削除数を最小にしたい。
goto文を何個消す必要があるか？

解法
まずはgoto文で飛ぶとラベルで次の行に移動するをグラフにします。
矢印はその行に飛ぶ→を逆向きにして繋げます。
後はゴールから逆探索してスタート行の上まで到達できるなら答えは0。
到達できないなら、到達できた範囲全部で上にgoto文があればこれを一つだけ無視した範囲から逆探索を続け駄目ならもうひとつ無視してと続けます。
こんな簡単な問題で不正回食らったら恥ずかしい問題ですね。

#include<stdio.h>
#include<map>
#include<string>
#include<set>
#include<iostream>
#include<vector>
#include<queue>

int main(){
	int n;
 	int spents[102]={0};
std::vector<int> G[102];
	std::map<std::string,int> code;
	std::map<int,std::string> go;
	std::string com,label;
	std::queue<int> qu;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		std::cin>>com;
		if(com=="goto"){
			std::cin>>label;
			go[i]=label.substr(0,label.size()-1);
		}else{
			code[com.substr(0,com.size()-1)]=i;
		}
	}
for(int i=0;i<=n;i++){
		if(go.find(i)!=go.end()){
			G[code[go[i]]].push_back(i);
		}else{
		G[i+1].push_back(i);
		}
	}
	qu.push(n+1);
	spents[n+1]=1;
	int ans=0,now;
	while(1){
		while(qu.empty()==false){
 			now=qu.front();
			qu.pop();
			if(now==0)break;
			for(int i=0;i<G[now].size();i++){
				int back=G[now][i];
				if(spents[back]==1)continue;
				spents[back]=1;
				qu.push(back);
			}
		}
		if(now==0)break;
		
		for(int i=1;i<=n+1;i++){
			if(spents[i]==1&&spents[i-1]==0){
				qu.push(i-1);
				spents[i-1]=1;
			}
		}
		ans++;
	}
	std::cout<<ans<<"\n";
}