Codeforces Round #405 (Div. 2) C

Codeforces Round #405 (Div. 2)

C. Bear and Different Names

http://codeforces.com/contest/791/problem/C

input

8 3
NO NO YES YES YES NO

output

Adam Bob Bob Cpqepqwer Limak Adam Bob Adam

위의 예제를 보고 얘기하면 쉽다.

첫 입력 8은 output에서 나와야 하는 단어는 8개라는 의미다.

그다음 입력 3은 3개씩 본다는 의미다.

출력의 1,2,3번째 단어를 보면 2,3번째 단어가 Bob으로 겹친다.

그럼 NO이다.

2,3,4번째 봐도 2,3번째 단어가 Bob으로 겹치니까 또 NO임...

그래서 인풋에서 첫번째 2개가 NO라는 의미

(당연히 하나도 안겹치면 YES인 셈이다.)

그래서 N, K값 주어지고 NO, YES가 N-K+1개 주어지면 그 조건을 만족하는 단어들을 출력하면 된다.

이때 주의할 것이 단어의 첫 문자는 대문자이고 다음 문자는 무조건 소문자여야 한다. (대문자 하나만 출력해도 상관없음)

N,K값이 2이상 50이하이고 이므로 시간복잡도 고려해줄 것도 없다.

이 문제는 약간의 센스가 필요한데,

N개를 모두 다른 단어로 지정하고

No가 i번째에 등장하면 i+k-1번째 단어를 i번째 단어와 똑같이 만들어주면 된다.

이게 가능한 이유는

i번째 위치에서 NO때문에 [i, i+k-1]구간에서 적어도 2개의 단어를 중복시켜야 한다고 하자.

그 다음 i+1번째에 YES가 나오든 NO가 나오든 상관없이 이전 NO를 만족시키려면 i번째 단어와 i+k-1번째 단어가 같으면 된다.

왜냐하면 [i+1, i+k]구간에서는 i번째 단어가 고려되지 않기 때문이기도 하며, 중복되는 단어가 존재하지 않기 때문이기도 하다.

만약 중복되는 단어가 존재한다면 어차피 문제 조건상 NO라는 인풋이 주어질 수밖에 없으므로 고려하지 않아도 된다.

설명은 긴데... 막상 풀면 쉬운문제.. but 나는 틀렸다. ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

#include <cstdio>
#include <cstring>
using namespace std;
char ch[52][3], s[4];
int ans[52];
int main() {
    memset(ans, 0, sizeof(ans));
    for(int i=0; i<26; i++) ch[i][0]='A'+i;
    for(int i=26; i<52; i++) {
        ch[i][0]='A'+i-26;
        ch[i][1]='a'+i-26;
    }
 
    int n,k; scanf("%d%d",&n,&k);
    for(int i=0; i<n; i++) ans[i]=i;
    for(int i=0; i<n-k+1; i++) {
        scanf("%s", s);
        if(s[0]=='N') ans[i+k-1]=ans[i];
    }
    for(int i=0; i<n; i++) printf("%s ", ch[ans[i]]);
    return 0;
}

아, 그리고 갑자기 생각났는데,

단어 만들때 string에 char를 +하면 뒤에 붙여서 써지는데

string 변수에 char 값 2개를 더하면 (변수로 더해도 마찬가지) 아스키코드 값의 합으로 계산된다.