Codeforces Round #126 (Div. 2) D : Programming Language

問題概要

テンプレートを用いて複数のオーバーロードされた関数があるので、関数を実際に呼び出すとき何通りインスタンス化される可能性があるか求める問題。

解法

mapでがりがり実装する。

acceptされたコード

#include <cstdio>
#include <map>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

map< string, vector<vector<string> > > funcs;
map<string, string> variables;
string callf[1000];
vector<string> callt[1000];

int N, M, K;
void init() {
	string line;
	cin >> N;
	cin.ignore();
	for (int i = 0; i < N; ++i) {
		getline(cin, line);
		for (int j = 0; j < (int)line.length(); ++j) {
			if (line[j] == '(' || line[j] == ')' || line[j] == ',') {
				line[j] = ' ';
			}
		}
		stringstream ss(line);
		string f, e;
		ss >> e >> f;
		vector<string> tmp;
		string t;
		for (;ss >> t;) {
			tmp.push_back(t);
		}
		funcs[f].push_back(tmp);
	}
	cin >> M;
	cin.ignore();
	for (int i = 0; i < M; ++i) {
		getline(cin, line);
		stringstream ss(line);
		string t, n;
		ss >> t >> n;
		variables[n] = t;
	}
	cin >> K;
	cin.ignore();
	for (int i = 0; i < K; ++i) {
		getline(cin, line);
		for (int j = 0; j < (int)line.length(); ++j) {
			if (line[j] == '(' || line[j] == ')' || line[j] == ',') {
				line[j] = ' ';
			}
		}
		stringstream ss(line);
		string f;
		ss >>  f;
		vector<string> tmp;
		string t;
		for (;ss >> t;) {
			tmp.push_back(variables[t]);
		}
		callf[i] = f;
		callt[i] = tmp;
	}
}

int subsolve(string f, vector<string> ts) {
	if (funcs.find(f) == funcs.end()) {
		return 0;
	}

	const vector< vector<string> >& as = funcs[f];
	int ans = 0;
	for (int i = 0; i < (int)as.size(); ++i) if (ts.size() == as[i].size()) {
		bool ok = true;
		for (int j = 0; j < (int)ts.size(); ++j) {
			ok &= (ts[j] == as[i][j]) || (as[i][j] == "T");
		}
		if (ok) {
			++ans;
		}
	}

	return ans;
}

void solve() {
	for (int i = 0; i < K; ++i) {
		printf("%d\n", subsolve(callf[i], callt[i]));
	}
}

int main() {
	init();
	solve();

	return 0;
}