Codeforces #405 C. Bear and Different Names
- 方針
まず、n個の異なる名前を用意。 i番目が"NO"なら、ans[i+k-1] = ans[i]とするとi番目以外のk個のグループには影響がない。
ここで、ans[i] = ans[i+k-1]とすると、ans[i+k-1]が後から更新された場合にこまる。
自分の回答
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; typedef long long ll; int main() { int n, k; cin >> n >> k; vector<string> ans(n); int cnt = 0; char suff = 'A', name = 'a'; for(int i=0;i<n;i++) { if(cnt > 25) { suff++; name = 'a'; } string a{suff}, b{name}; //ans[i] = suff + (char) name; ans[i] = a + b; //cout << suff + name << endl; cnt++; name++; } for(int i=0;i<n-k+1;i++) { string si; cin >> si; if(si == "NO") { ans[i+k-1] = ans[i]; } } for(int i=0;i<n;i++) { cout << ans[i] << " "; } cout << endl; }
模範解答
#include <bits/stdc++.h> using namespace std; string s[105]; int main() { int n, k; cin >> n >> k; // generate n different names for(int i = 1; i <= n; ++i) { s[i] = "Aa"; s[i][0] += i / 26; s[i][1] += i % 26; } for(int start = 1; start <= n - k + 1; ++start) { string should; cin >> should; if(should[0] == 'N') // not effective group s[start+k-1] = s[start]; // make two names equal } for(int i = 1; i <= n; ++i) cout << s[i] << " "; cout << "\n"; }