AtCoder Beginner Contest 381

A - 11/22 String

O(N)
問題文の条件通り、シミュレートしましょう。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;

    auto No = [](){
        cout << "No" << endl;
        exit(0);
    };

    if(N%2 == 0) No();

    int ans = 0;
    repx(i, 1, N+1){
        if((N + 1) / 2 - 1 >= i && S[i-1] != '1') No();
        if((N + 1) / 2 == i && S[i-1] != '/') No();
        if((N + 1) / 2 + 1 <= i && S[i-1] != '2') No();
    }

    cout << "Yes" << endl;
    return 0;
} 

B - 1122 String

O(N)
問題文の条件通り、シミュレートしましょう。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    string S;
    cin >> S;
    int N = S.size();
    if(N%2==1){
        cout << "No" << endl;
        return 0;
    }

    for(int i=1; i <= N / 2; i++){
        if(S[2 * i - 2] != S[2 * i - 1]){
            cout << "No" << endl;
            return 0;            
        }
    }

    set<char> st;
    for(int i=1; i <= N / 2; i++){
        if(st.find(S[2 * i - 1]) != st.end()){
            cout << "No" << endl;
            return 0;            
        }
        st.insert(S[2 * i - 1]);
    }
    cout << "Yes" << endl;

    return 0;
} 

C - 11/22 Substring

O(N)
'/'を起点に、左側の'1'の数、右側の'2'の数を探索します。

min(左側の'1'の数、右側の'2'の数) * 2 + 1 = Sの部分文字列の長さ

シミュレートする問題です。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;

    if(N==1){
        cout << 1 << endl;
        return 0;
    }

    int ans = 0;
    rep(i, N){
        if(S[i] == '/'){
            int d = 1;
            while(0<=i-d && i+d<N && S[i - d] == '1' && S[i + d] == '2'){
                d++;
            }
            ans = max(ans, d * 2 - 1);
        }
    }
    cout << ans << endl;

    return 0;
} 

D - 1122 Substring

O(N)
尺取り法の問題です。
規則性のある連続する部分列を探索する問題は尺取り法を考察します。

X_{2i−1}とX_{2i}は等しい。

から連続する2文字が同じ文字を探索します。
サンプル1で考察します。

8
2 3 1 1 2 2 1 1

「1 1 2 2」の為、4が最大値になります。
1という同じ文字は含めていけないので6でなく4です。
判定式は、

C++

while(right + 1 < N && A[right] == A[right+1] && st.find(A[right]) == st.end()){
    
}

1が重複しないようにsetを使用しています。
以下の入力を考えましょう。

5
1 1 1 2 2 

先ほどのプログラムは、i=0から2文字ずつ判定するパターンを考えました。
奇数のインデックスから1122文字列を判定しないといけない時に正確な処理ができません。
偶数、奇数のインデックスを見るように2重ループの構造にしましょう。

C++

    for(int i=0; i<2; i++){
        int right = i;
        set<int> st;
        for(int left = i; left < N; left+=2){
            while(right + 1 < N && A[right] == A[right+1] && st.find(A[right]) == st.end()){
                st.insert(A[right]);
                right += 2;   
            }
            ans = max(ans, right - left);
            if(right <= left) right = left + 2;
            if(st.find(A[left]) != st.end()) st.erase(A[left]);
        }
    }

実装しましょう。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];
    
    int ans = 0;
    for(int i=0; i<2; i++){
        int right = i;
        set<int> st;
        for(int left = i; left < N; left+=2){
            while(right + 1 < N && A[right] == A[right+1] && st.find(A[right]) == st.end()){
                st.insert(A[right]);
                right += 2;   
            }
            ans = max(ans, right - left);
            if(right <= left) right = left + 2;
            if(st.find(A[left]) != st.end()) st.erase(A[left]);
        }
    }
    cout << ans << endl;

    return 0;
}