読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ARC 059 D - アンバランス / Unbalanced

問題

問題概要

省略

解法

アンバランスとなる文字のどんなものでも良いから、一つ出力すればいい。だから、余計な文字を含まない(最短でアンバランスな文字)ものを考えればいい。そのように考えると
aa
aa(:任意の文字)
の2パターンがある。この2パターン以上の文字数となるアンバランスな文字列を考えるとサンプル1ではneededの中でアンバランスなものとして、eedeを上げているが、これはeeというより短いアンバランスなものを含んでいる。meleeもアンバランスな文字列であるが、より短いアンバランスな文字列として、eleやeeを含んでいる。

ミス

部分点解放しか思いつかなかった。なんか難しく考えすぎた。 部分点解放は単純に左端と右端となりうる場所を全探索して、解を見つけるだけである。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)

int main(void){
    string s; cin >> s;
    rep(l, s.size()){
        reps(r, l + 1, s.size()){
            vector<int> v(30);
            rep(i, 30) v[i] = 0;
            reps(i, l, r + 1){
                v[s[i] - 'a']++;
            }
            sort(v.begin(), v.end());
            if(v[v.size() - 1] > (r - l + 1) / 2){
                printf("%d %d\n", l + 1 ,r + 1);
                return 0;
            }
        }
    }
    printf("-1 -1\n");
    return 0;
}

コード

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

int main(void){
    string s; cin >> s;
    int n = s.size();

    //連続した2文字を見る
    for (int i = 0; i < n - 1; ++i){
        if(s[i] == s[i + 1]){
            printf("%d %d\n", i + 1, i + 1 + 1); return 0;
        }
    }

    //a*aのような文字列
    for (int i = 1; i < n - 1; ++i){
        if(s[i - 1] == s[i + 1]){
            printf("%d %d\n", i - 1 + 1, i + 1 + 1); return 0;
        }
    }

    printf("-1 -1\n");
    return 0;
}