0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

【AtCoder】CODE FESTIVAL 2017 Final B - Palindrome-phobia

Last updated at Posted at 2019-03-12

CODE FESTIVAL 2017 Final B - Palindrome-phobia

問題概要

B - Palindrome-phobia

解法

長さ2以上の回文を部分文字列として含ませないためには$S$を$abcabc\cdots$と並べ替えれば良い。
判定であるが、$S$における各文字の出現回数が等しければYES。そうでない場合は各文字の出現回数の最大値と最小値の差が2未満であればYES。これら以外はNO。時間計算量は$S$の長さを$N$として$O(N)$。

ソースコード

#include <bits/stdc++.h>

using namespace std;

#define llong long long int
#define ldouble long double
#define fore(i, n) for(auto &i : n)
#define rep(i, n) for (int i = 0; i < n; ++i)
#define repr(i, n) for (int i = n; i >= 0; --i) 
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

const static int mod = 1000000000 + 7;
const static int inf = INT_MAX / 2;
const static llong INF = LLONG_MAX / 2;
const static double eps = 1e-6;
const static int dx[] = {1, 0, -1, 0};
const static int dy[] = {0, 1, 0, -1};

template<class T> bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}

template<class T> bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

void solve();

signed main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    solve();
    
    return 0;
}

void solve() {
    string S;
    cin >> S;
    map<char, int> M;
    M['a'] = 0;
    M['b'] = 0;
    M['c'] = 0;
    const int n = S.size();
    rep(i, n) ++M[S[i]];

    if (M['a'] == M['b'] && M['b'] == M['c'] && M['a'] == M['c']) {
        cout << "YES" << endl;
    } else {
        int max_cnt = -1, min_cnt = inf;
        rep(i, 3) {
            chmax(max_cnt, M['a' + i]);
            chmin(min_cnt, M['a' + i]);
        }

        if (max_cnt - min_cnt >= 2) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?