Beta Round #63-C: Game
解法
素材を組み合わせて新しい素材を作るアレ。1種類しか変化させないし、サイズも小さいので特に計算量を減らしたりする必要はない。問題文を読み間違えていたけど、ただのシミュレーションらしい。
感想
計算量を減らす工夫はいらないけど実装量を減らす工夫は必要ですよね(一生読み返されることのないだろう冗長なコードを眺めながら)。
#include <set> #include <iomanip> #include <vector> #include <cstdio> #include <iostream> #include <sstream> #include <map> #include <cassert> using namespace std; int K, N, M, Q; set<string> basics; map<string, map<string, int> > dict; map<int, map<string, int> > cnts; void proc(int x){ map<string, int>& cur = cnts[x]; for(map<string, map<string, int> >::iterator itr=dict.begin(); itr!=dict.end(); itr++){ string name = itr->first; map<string,int>& tmp = itr->second; bool ok = true; for(map<string,int>::iterator jtr=tmp.begin(); jtr!=tmp.end(); jtr++){ if(cur[jtr->first] < jtr->second){ ok = false; break; } } if(ok){ while(1){ bool ok2 = true; for(map<string,int>::iterator jtr=tmp.begin(); jtr!=tmp.end(); jtr++){ if(cur[jtr->first] < jtr->second){ ok2 = false; break; } } if(!ok2) break; for(map<string,int>::iterator jtr=tmp.begin(); jtr!=tmp.end(); jtr++){ cur[jtr->first] -= jtr->second; } cur[name]++; } } } } void solve(){ for(int i=0; i<Q; i++){ string line, str; int x; getline(cin,line); scanf(" "); stringstream ss(line); ss >> x >> str; cnts[x][str]++; proc(x); } for(int i=1; i<=K; i++){ int cnt=0; for(map<string,int>::iterator itr=cnts[i].begin(); itr!=cnts[i].end(); itr++){ if(itr->second) cnt++; } printf("%d\n",cnt); for(map<string,int>::iterator itr=cnts[i].begin(); itr!=cnts[i].end(); itr++){ if(itr->second){ printf("%s %d\n",itr->first.c_str(), itr->second); } } } } int main(){ scanf("%d%d%d%d ",&K, &N, &M, &Q); for(int i=0; i<N; i++){ string line; getline(cin, line); scanf(" "); basics.insert(line); } for(int i=0; i<M; i++){ string line, str, name; getline(cin, line); scanf(" "); for(int j=0; j<line.length(); j++) if(line[j]==':' || line[j]==',') line[j]=' '; stringstream ss(line); ss >> name; while(ss>>str){ int x; ss >> x; dict[name][str] = x; } } solve(); return 0; }