ARC058-D アンバランス - 競プロのーと

問題

考察

アンバランスである条件「tの長さが2以上」「tの中の文字のうち過半数が同じ文字("noon"のように、半数だけではアンバランスではない)」

これを満たす文字がsの中に存在するか判定する。

"needed"では、"eede"がアンバランスな文字列

愚直に全探索を考えると、文字列sの部分文字列を全てアンバランスか試すことが思いつく。sの長さをnとすると、sには長さ2以上の部分文字列がn(n-1)/2個存在するので、それらで作られた文字列全てについてアルファベットの出現回数を数えることでO(n³)となりn≦100の部分点は解ける。(①)

しかし|s|≦10⁵なのでもっと効率的な解き方をしなければならない。アンバランスな文字列を考えると、必ず、"XX"又は"XYX"という配置が含まれていることがわかる。

"XX"又は"XYX"という文字列がある段階でアンバランスな文字列が含まれると判断できる。よって文字列を始めから追っていって、直近の2文字を覚えておき、次に得られた文字がその2文字のどちらかに一致する場合(直近2文字を'X','Y'とすると、"XYX"又は"XYY"となる時)アンバランスであると判断できる。これを実装すれば満点解答を得られる。(②)

(メモ化するのでDP?線形探索?思いつきさえすれば実装すること自体は①よりも簡単だと思います)

コード①(部分点)

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

string s;
int al[30];//各アルファベットの出現回数をカウントする

int main(){
    cin>>s;
    int si=s.size();
    
    for(int i=0; i<si; i++){//部分文字列の初め
        
        for(int j=i+1; j<si; j++){//部分文字列の終わり
            //i+1と置くことで部分文字列の長さは2以上になる
            
            for(int j=0; j<30; j++)al[j]=0;//アルファベットの初期化
            
            //文字列の探索(iから始まってjで終わる)
            for(int k=i; k<=j; k++){
                //sのj番目の文字に対応するアルファベットをカウントする
                al[s[k]-'a']++;
            }
            //最頻値を得たいので降順にソートする
            sort(al,al+30,greater<int>());
            if(al[0]>(j-i+1)/2){
                cout<<i+1<<" "<<j+1<<endl;//1-indexedで答える
                return 0;
            }
        }
    }
    
    cout<<"-1 -1"<<endl;
    
    return 0;
}

コード②(満点)

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

string s;

int main(){
    cin>>s;
    int si=s.size();
    
    char a=s[0];
    char b=s[1];
    if(a==b){
        cout<<"1 2"<<endl;
        return 0;
    }
    for(int i=2; i<s.size(); i++){
        char c=s[i];
        if(a==c){
            cout<<i-1<<" "<<i+1<<endl;
            return 0;
        }else if(b==c){
            cout<<i<<" "<<i+1<<endl;
            return 0;
        }
        a=b;
        b=c;
    }
    cout<<"-1 -1"<<endl;
    return 0;
}