[Codeforces] 1694A. Creep

나는 이거 그나마 패턴 만들어서 꾸역꾸역 string을 만들었는데, 이보다 더 간단한 패턴이 있다고 한다.

 

Define the minimum possible creepiness of the string as ans. We want to show that ans is equal to $max(1, |a - b|)$.

 

최소한의 creepiness를 가지는 ans라는 string을 정의해보자.

우리는 ans가 $max(1, |a - b|)$와 동일하다는 것을 보여주어야 한다.

 

• $S[1..1]$의 creepiness는 1과 동일하고, $S[1..n]$는 $|a - b|$와 동일하다. 따라서 $max(1, |a - b|) <= ans$이다.
• $max(1, |a - b|)$의 creepiness와 동일하게 만드는 방식
  • while $0 < a, b$ holds, add 01 to the end of the string. After that, add the remaining character to the end of the string. Now we know ans <= $max(1, |a-b|)$.
• Complexity: $O(a + b)$

#include <iostream>
#include <map>
#include <cmath>
using namespace std;
int main() {
    int t;
    cin >> t;
    while(t--) {
        int a, b;
        cin >> a >> b;
        for(int i = 0;i < min(a, b);i++) {
            cout << "01";
        }
        
        for(int i = 0;i < abs(a - b);i++) {
            cout << (a < b ? 1 : 0);
        }
        
        cout << '\n';
    }
    return 0;
}

이 개수의 차이를 카운트할 때 어차피 문자열의 처음부터 세기 때문에 누적된다.

따라서 굳이 가운데 사이사이에 숫자를 넣어줄 필요가 없다.

앞에 최대한 score를 0으로 만들면 이후에는 score가 증가되어 $max(|a - b|)$가 된다.