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

문제적남자 73화:수학 - 코딩으로 풀어보기

문제적남자 73화 - 수학 풀이

수능 D-100 특집으로 이런 문제가 나왔다.

첫 번째 숫자까지는 1로 나누어지고,

두 번째 숫자까지는 2로, .... 열 번째 숫자까지는 10으로 나누어진다.

0부터 9까지 10개의 숫자를 모두 사용해 규칙에 맞는 수를 만들어라.

다음과 같은 몇 가지 규칙을 발견하고 브루트 포스로 풀어보기로 했다.

1. 열 번째 숫자는 0 이다. (10의 배수는 0으로 끝나기 때문)
2. 다섯 번째 숫자는 5 이다. (5의 배수는 0, 5로 끝난다. 0은 열 번째 숫자이므로 5)
3. 짝수 번째 숫자는 2, 4, 6, 8 중 하나이다.
4. 홀수 번째 숫자는 1, 2, 3, 4, 6, 7, 8, 9 중 하나이다.

소스: https://jsfiddle.net/J00nas/yrmen84L/

javascript로 적어봤는데, 비동기식이라 그런지 제대로 걸러지지가 않는다. (그리고 브라우저의 자바스크립트 버전별로 다르게 보일 수 있다.) 그래도 답은 나온다.

모던 브라우저에서는 위처럼 보일것이다.

자바스크립트로는 코드가 정확하지 않은 것 같아서 C++로 다시 적었다.
소스: https://ideone.com/yoLJXx

신기하게도 규칙을 만족하는 숫자는 3816547290 뿐이었다.

2991 - 사나운 개

https://www.acmicpc.net/problem/2991

$p$분 후에 우체부가 도착한다면, $p \% (a+b)$ 가 $a$(공격시간)보다 이후라면 공격받지 않는다.

#include <cstdio>

bool attacked(int n, int a, int b){
    n %= (a+b);
    return n < a;
}

int main(){
    int a, b, c, d, n;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    for(int i=0; i<3; ++i){
        scanf("%d", &n);
        printf("%d\n", attacked(n-1, a, b) + attacked(n-1, c, d));
    }
    return 0;
}

2118 - 두 개의 탑

https://www.acmicpc.net/problem/2118

문제를 푸는 데 가장 크게 작용한 아이디어는

문제의 정답 $\le$ 전체 길이의 합 / 2

라는 사실이었다.

두 지점 사이의 거리는 "$x$ = [a, b) 사이의 부분 합" 라고 할 때 $x$ 와 전체 길이의 합 - $x$ 중 더 작은 것이 된다.
이러한 부분합들 중 가장 큰 것이 문제의 정답이다.

부분합을 구하려는 데 계속 $O(N^2)$ 밖에 안 떠올랐다. 시계방향과 반시계방향 두 경로 중 더 작은것을 선택하는 것 때문이었다.
"문제의 정답 $\le$ 전체 길이의 합 / 2" 이니까 전체 길이 합의 절반보다 작지만 가장 큰 수만 찾으면 되겠구나 생각하고 이진탐색을 궁리해보았다.

계산하고 하는 거리 [a, b) 는 a $\le$ b인 것들만 확인해도 충분했다. 예를 들어, [5, 3) 을 확인하고 싶다면 전체 거리의 합에서 [3, 4) 를 빼면 되기 때문이다. (한쪽 방향에 대해서만 본다면)

시계방향/반시계방향에 대해 위 계산을 범위를 좁혀가면서 했다.