[c++] (AtCoder Beginner Contest 295) D - Three Days Ago

https://atcoder.jp/contests/abc295/tasks/abc295_d

D - Three Days Ago

인상적인 풀이가 있다.

먼저 평범한 풀이는

1. 문자열 s로 입력을 받는다.

2. s의 i번째 요소(0~9) 각각의 누적합을 작성한다.

    (짝수 홀수만 판단하면 되므로 0,1로 기록한다.)

3. i가 0~s.size() 일 때, i에 대해 기록된 누적합(0~9)을 2진법을 생각하고 10진법으로 변환하여 masking벡터에 저장한다.

    (이 과정에서 비트 마스킹을 사용했다)

4. masking에 중복된 element를 찾고, 그 element의 중복된 횟수를 n이라 할 때, nC2을 ans에 더해준다.

5. ans 출력

#include<bits/stdc++.h>
using namespace std;
#define N 555555
bool prefix_sum[N][10];
vector<int> masking;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s; cin>>s;
    int n = s.size();
    for(int i=1; i<=n; i++){
        // s[i] 누적
        for(int j=0; j<10; j++){
            if(j == s[i-1]-'0') prefix_sum[i][j] = !prefix_sum[i-1][j];
            else prefix_sum[i][j] = prefix_sum[i-1][j];
        }
    }
    for(int i=0; i<=n; i++){
        int a=0;
        for(int j=0; j<10; j++)
            if(prefix_sum[i][j])
                a|=1 << (j +1);
        masking.push_back(a);
    }
    sort(masking.begin(), masking.end());
    long long ans=0, cnt=1;
    for(int i=1; i<n+1; i++){
        if(masking[i] == masking[i-1])
            cnt++;
        else{
            if(cnt != 1)
                ans += cnt*(cnt-1)/2;
            cnt = 1;
        }
    }
    if(cnt != 1)
        ans += cnt*(cnt-1)/2;
    cout << ans;
    return 0;
}

 

이것 말고 신기한 풀이가 있다.

반복을 줄이고, nC2를 시그마 연산을 이용해 풀이한 방법이다.

#include<bits/stdc++.h>
using namespace std;
#define N 555555
int save[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s; cin>>s;
    long long ans = 0;
    int bit_mask=0;
    // s[-1]에는 누적합이 0~9 모두 0이므로
    // 초기값으로 1을 넣어준다.
    save[0] = 1;
    for(int i=0; i<s.size(); i++){
        /*
        1이였으면 0으로
        0이였으면 1로
         => XOR연산이 알맞음
        */
        bit_mask ^= 1<<(s[i]-'0');
        /*
        누적된 상태를 시그마 해줘야함
        (누적된것의 중복을 카운트 하기 위해)
        nC2 = n(n-1)/2 = sum(1,n-1)
        */
        ans += save[bit_mask]++;
    }
    cout << ans;
    return 0;
}