BottomCoder SRM357

なんか今日の8時からやるそうだったので参加してきました。(ツイッターで募集されてた。)

250 MnemonicMemory

なんか数字と単語の長さで語呂合わせしたいからよろしく。みたいな問題。解は必ず存在する。

けど、複数解がある場合は辞書順で最小のものを返せみたいな問題。

具体例を挙げると、

単語リストと作りたい数字の並びが与えられるから、

31415 = "Yes I have a number"をつくれみたいな感じ。

先にソートしておく。

class MnemonicMemory {
public:
	string getPhrase(string number, vector <string> dic) {
		string ret;
		sort(all(dic));
		vector<bool> done(dic.size(),0);
		int pos = 0;
		while(pos < number.size()){
			rep(i,dic.size()){
				if(!done[i] && dic[i].size() == number[pos] - '0'){
					ret += dic[i] +" ";
					done[i] = 1;
					break;
				}
			}
			pos++;
		}
		return ret.substr(0,ret.size()-1);
	}
};

500 Hotel

とりあえずコスト最小化しろみたいな。よく問題を読んでいない。汚い。

とりあえずサンプル見てDPしたら通った。

class Hotel {
public:
	int marketCost(int minCustomers, vector <int> a, vector <int> b) {
		int ret = (1<<21);
		vector<int> dp(3001,(1<<21));
		dp[0] = 0;
		rep(j,a.size())rep(i,3000-a[j]) dp[i+a[j]] = min(dp[i+a[j]],dp[i]+b[j]);
		rep(i,3001){
			if(i >= minCustomers){
				ret = min(ret,dp[i]);
			}
		}
		return ret;
	}
};

1000 WebsiteRank

本番で解けなかった(題意がつかめなかったので後で丁寧に解きました)

id:chokudaiさんの放送を見てやっと意味が分かった。

• "A B C"って入力が与えられたらAはBとCから繋がっている。
• 閉路があったら得点無きものとする。

ここらへんが重要

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

vector<int> revTree[1000];
bool wf[1000][1000] = {0};
long long memo[1000] = {0};
map<string,int> num;

// メモ化深さ優先探索
long long dfs(int pos){
	if(memo[pos])return memo[pos];
	
	long long ans = 1;
	rep(i,revTree[pos].size()){
		//ループが無ければ
		if(!wf[pos][ revTree[pos][i] ])
			ans += dfs( revTree[pos][i] );
	}
	return memo[pos] = ans;
}

int getNum(string s){
	if(num.find(s) != num.end())return num[s];
	return num[s] = num.size()-1; // アクセス順序に注意。
}

class WebsiteRank {
public:
	long long countVotes(vector <string> v, string website) {
		
		// string ⇒ intの番号 にしつつ、連結判定のための通常有向グラフと、探索用の逆グラフを生成。
		rep(i,v.size()){
			stringstream ss(v[i]);
			string t,s; ss >> t;
			while(ss >> s){
				revTree[getNum(t)].push_back(getNum(s));
				wf[getNum(s)][getNum(t)] = true;
			}
		}
		
		// 閉路チェック用のワーシャルフロイド
		int N = num.size();
		rep(k,N)rep(i,N)rep(j,N)
			wf[i][j] |= wf[i][k] & wf[k][j];
		
		// メモ化で探索
		return dfs( getNum(website) );
	}
};