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

Codeforces Round #353 (Div. 2)

http://codeforces.com/contest/675

A. Infinite Sequence

$a$에서 $c$의 차이만큼 계속 더해서 $b$를 만들 수 있는가를 묻는 문제이다.
직접 돌리는건 안된다. 예를 들어, $c=0$ 이기만해도 반복문으로는 안된다.

$ a+k*c == b $ 가 되는 $k$가 존재하는 가? 다시말해, $(b-a) \mod c == 0$ 인가? 이다.

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

int main(){
        int a, b, c;
        while(~scanf("%d %d %d", &a, &b, &c)){
        if(c == 0) puts( a == b ? "YES" : "NO" );
        else if(c > 0 && b < a) puts("NO");
        else if(c < 0 && b > a) puts("NO");
        else puts( (b-a)%c == 0 ? "YES":"NO" );
    }
    
    return 0;

}

B. Restoring Painting

2x2크기로 묶었을때 나오는 사각형 안의 수들의 합이 모두 같아지게 하는 빈칸의 경우의 수를 묻는 문제였다. 문제의 핵심은 정가운데 $?$는 전체 합에 영향을 미치지 않는다는 것이다.
그럼 나머지 모서리에 있는 4개의 $?$ 중에 하나를 설정해보면 나머지 물음표가 모두 해결되서, 이게 가능한 수인지 판별이 가능하다.
한 모서리 칸을 1~$N$까지 하나씩 설정하면서 가능한 경우를 세면 된다.

근데 코딩이 말려서 계속 틀렸다. 흠.. 분발해야겠다.