Codeforces Round #372 (Div. 2)

http://codeforces.com/contest/716

A. Crazy Computer

수 사이의 차이가 C 이하이면 카운팅하고, 그렇지 않으면 카운트가 0으로 초기화된다. 수열 끝에서 카운트가 몇인지 출력한다.

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef long long lld;

int main(){
    int n, c, a[1000001], len=0;
    scanf("%d %d", &n, &c);
    for(int i=0; i<n; ++i){
       scanf("%d", &a[i]);
       if(i > 0){
          if(a[i]-a[i-1] <= c) len += 1;
          else len = 1;
       } else len = 1;
    }
    printf("%d", len);
    return 0;
}

B. Complete the Word

본문에서 "... to replace all the question marks with uppercase letters such that ..." 이라고 했는 데, 강조된 uppercase letters만 보느라 "replace all the question marks"를 놓쳤다. 물음표를 계속 그대로 방치해서 결국 계속 틀렸던 문제.

본문의 조건을 좀 더 세심하게 읽자.

틀린거 고치느라 급해서 $O(50000 * 26)$ 으로 제출

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef long long lld;

int main(){
   char s[50501]={};
   scanf("%s ", s);
   bool ans = false;
   for(int i=0; s[i]; ++i){
      bool used[26]={};
      char f[26]={};
      int j, c=0;
      for(j=0; j<26 && s[i+j]; ++j){
         if(s[i+j] == '?') continue;
         if(used[s[i+j]-'A']) break;
         used[s[i+j]-'A'] = true;
      }
      if(j == 26) ans = true;
      if(ans){
         for(j=0; j<26; ++j){
            if(!used[j]) f[c++] = 'A'+j;
         }
         int c2=0;
         for(j=0; j<26; ++j){
            if(s[i+j] == '?') s[i+j] = f[c2++];
         }
         break;
      }
   }
   if(!ans) return puts("-1"), 0;
   for(int i=0; s[i]; ++i) putchar(s[i] == '?' ? 'A' : s[i]);

   return 0;
}