[Codeforces] Sum of Substrings

대회에서는 C번부터는 문제를 읽지 못해서 그 다음날에도 쭉 풀고 있다.

우선 내가 계획한 풀이 방법은 단순한 DFS이다.

이미 탐색해본 string은 패스하고, string마다 $f$함수를 계산하여 최솟값을 찾아낸다.

 

그런데 최대 길이가 $10^5$이기 때문에 최대 시간인 1초를 넘어간다. 즉 더 효율적인 풀이 방법이 있다는 것이다.

 

face value 

Hint 1.

What is the contribution of each 1?

 

Hint 2.

At what position would 1 contribute less?

 

해당 string을 분해해보면 크게 sum에 기여하는 방식은 세 가지이다.

1. 맨 앞 자리에서의 수

이 경우에는 sum에 한 번만 기여한다.

즉 하나의 1에 10이 더해지는 셈이다.

 

2. 가운데에 위치한 수

이 경우에는 sum에 두 번 기여한다.앞에 인접한 수와 매치되고, 뒤에 위치한 수와 매치되기 때문이다.

즉 하나의 1에 11이 더해지는 셈이다.

가운데에 위치하는 경우에는 순서가 상관이 없다.

실제로 2번째 testcase를 살펴보면 최선으로 이동해도 전체 sum은 동일하다.

어차피 11로 더해지는 것은 매한가지이기 때문이다.

 

3. 맨 뒷 자리에서의 수

이 경우에는 sum에 한 번만 기여한다.

즉 하나의 1에 1이 더해지는 셈이다.

 

이 경우 11로 더해지는 것보다는 1이나 10으로 더해지는 것이 sum을 최소화할 수 있다.

그래서 최대한 가운데의 수들을 뒤로 빼고, 앞으로 빼야 한다.

그리고 뒤로 빼는 게 더 우선순위가 높다.

 

이렇게 진행하면 시간복잡도가 $O(N)$로 훨씬 효율적으로 바뀐다.

 

점화식

$f(s) = 10 \times s_1 + 11 \times s_2 + 11 \times s_3  + ... + 1 \times s_{n-1} + 1 \times s_n $

 

만약 $s$가 0010100이면, $10 \times 0 + 11 \times 0 + 11 \times 1 + 11 \times 0 + 11 \times 1 + 11 \times 0 + 1 \times 0$

 

참고

https://codeforces.com/blog/entry/103212

Editorial for CodeCraft-22 and Codeforces Round #795 (Div. 2) - Codeforces

이렇게 패턴을 파악하여 단순화하는 것이 중요하다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        int ones = 0, p1_first = n, p1_last = -1;
        
        for(int p = 0;p < n;p++){
            if(s[p] != '1'){
                continue;
            }
            
            ones += 1;
            if(p1_first == n) {
                p1_first = p;
            }
            p1_last = p;
        }
        
        int add = 0;
        // moving the last one to last position
        if(ones > 0 && (n - 1 - p1_last <= k)) {
            k -= (n - 1 - p1_last);
            add += 1;
            ones -= 1;
        }
        
        // moving the first one to first position
        if(ones > 0 && p1_first <= k) {
            k -= p1_first;
            add += 10;
            ones -= 1;
        }
        
        cout << 11 * ones + add << '\n';
    }
    return 0;
}