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";
}