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; }