パソコン甲子園2010予選問題がAOJに

うpられたのでSubmit。

結果としては、前回ブログに載せたソースだと、6と9がWA,10がTLE出した。6は本選で通った解法が通らなくてAC率大変なことに。

よって9を書き直したら、順列とか使う必要がなくて、単純に負辺をたった一度だけ通れるようにしたdijkstraでした。問題文難読だなあオイ。

9.ケーキ屋うんぬん

#include <iostream>
#include <vector>
#include <map>
#include <sstream>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<pair<int,string>,int>  NODE;

#define cost first.first
#define pos first.second
#define visit second

map<string,vector< pair<string,int> > > nodeInfo;
map<string,int> cakeShop;

int dijkstra(){
	int ret = (1<<25);
	
	priority_queue<NODE,vector<NODE>,greater<NODE> > Q;

	Q.push(make_pair(make_pair(0,"H"),0));
	map<string,int> memo[1<<10];
	while(Q.size()){
		NODE q = Q.top();Q.pop();
		if(memo[q.visit].find(q.pos) != memo[q.visit].end() ){
			if(memo[q.visit][q.pos] <= q.cost)continue;
		}
		
		memo[q.visit][q.pos] = q.cost;
		
		if(q.pos == "D"){
			ret = min(q.cost,ret);
		}
		
		rep(i,nodeInfo[q.pos].size()){
			NODE next;
			next.visit = q.visit;
			next.cost = q.cost + nodeInfo[q.pos][i].second;
			next.pos = nodeInfo[q.pos][i].first;
			
			if(next.pos[0] == 'C' && (q.visit & (1<<(next.pos[1]-'1'))) )continue;
			
			if(next.pos[0] == 'C'){
				next.visit |= (1<<(next.pos[1]-'1'));
				next.cost  -= cakeShop[next.pos];
			}
			Q.push(next);
		}
	}
	return ret;
}
int main(){
	int m,n,k,d;
	int base;
	while(cin >> m >> n >> k >> d , m ){
		nodeInfo.clear();
		cakeShop.clear();
		rep(i,m){
			int c;
			cin >> c;
			stringstream ss;
			ss << 'C' << i+1;
			cakeShop[ss.str()] = c;
		}
		rep(i,d){
			string a,b;int c;
			cin >> a >> b >> c;
			nodeInfo[a].push_back( make_pair(b,c*k) );
			nodeInfo[b].push_back( make_pair(a,c*k) );
		}
		cout << dijkstra() << endl;
	}	
}

10 こぶたぬきつねこ

出現数チェックを入れるだけで通る悪質なテストケースなのか知らないが入れたら通った。

(追記[2011/02/28]:オイラー閉路チェック+グラフが連結か判定　らしいのでこれでよいらしい)

/* 01 - 19*/

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n;
int data[26][26],fi[26],la[26];
string st;

bool flag;

void bt(char next,int depth){
	if(depth == n-1){
		if(next == st[0])flag = true;
	}
	if(flag)return;
	
	for(int i=0;i<26;i++){
		if(data[next-'a'][i]){
			data[next-'a'][i]--;
			bt('a'+i,depth+1);
			data[next-'a'][i]++;
		}
	}
}
int main(){
	while(cin >> n,n){
		for(int i=0;i<26;i++){
			fi[i] = la[i] = 0;
			for(int j=0;j<26;j++)
				data[i][j] = 0;
		}
		for(int i=0;i<n;i++){
			cin >> st;
			data[st[0]-'a'][st[st.length()-1]-'a']++;
			fi[st[0]-'a']++;
			la[st[st.length()-1]-'a']++;
			
		}
		
		data[st[0]-'a'][st[st.length()-1]-'a']--;
		flag = false;
		bool notSearch = false;
		
		for(int i=0;i<26;i++){
			if(fi[i] != la[i])notSearch = true; 
		}
		
		if(!notSearch)bt(st[st.length()-1],0);
		cout << (flag?"OK":"NG") << endl;
	}
}