B - 回文分割(diff: 984)

本当に苦手っすこういうの！！！！

問題: B - 回文分割

まずは問題文から、文字列$S$は並び替えられてしまうので文字列$S$の並びは気にする必要がない。

なので文字列$S$では無く、文字列$S$に出現する文字とその出現回数について着目する。

次に回文の文字数について考えてみる。

文字数が偶数の回文について考えてみる。

この時、回文を真ん中で左右に分割すると、左と右の文字列において、出現する文字とその出現回数は一致する。

すなわり、左の文字列で x 回出現していたら右の文字列でも x 回出現する。

なので、回文中に出現する文字の出現回数は偶数となる

文字数が奇数の回文について考えてみる。

文字数が 1 の場合は明らかに回文になる。

文字数が 1 よりも大きく、奇数の場合について考えてみると、真ん中の文字を取り除けば、偶数の回文になる。

そのため、真ん中の文字にはなんでも入れられる。

まとめ

これらの考察を踏まえると、文字列$S$に出現する文字で出現回数が奇数の種類数だけ回文は作らざるを得ない。

回文を作る数が分かれば、後は$X$ができるだけ大きくなるように回文を作れば良い。

解く

文字列$S$の文字数を$len(S)$とする。文字列$S$に出現した文字の中で出現回数が奇数の文字種類数を$t$とする。

$n$を自然数として 1 から探索し、以下の不等式を満たす最大の値$n$を出力すれば良い。

$t(2n-1) \leq len(S)$

出現回数が奇数の文字を並べて、肉付けをうまいようにしていくイメージ。この時、回文はすべて文字数が奇数となる。

また、出現回数が奇数の文字が一個もなければ並び替えて一つの回文になるため$len(S)$を出力すれば良いです。

解答

提出 #19092644 - AtCoder Regular Contest 053

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


#include <bits/stdc++.h>
#define INF 1e9
#define INFLL 1ull<<60u
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

using vi = vector<int>;
using vvi = vector<vi>;
using vpii = vector<pair<int,int>>;

void solve() {
    string S; cin >> S;
    map<char,int> mp;
    for(const auto &c: S) mp[c]++;

    int odds = 0; // 出現回数が奇数の種類数
    for(const auto &p: mp) if(p.second%2) odds++;

    // もし出現回数が0ならlen(S)が答え(並び替えで回文が出来るので)
    if(odds == 0) {
        cout << S.size() << endl;
        return;
    }

    const int MAX = 1e6;
    FOR(i,1,MAX) {
        if (odds * ((2 * i) - 1) > S.size()) {
            assert(i > 1);
            cout << (2 * (i-1)) - 1 << endl;
            return;
        }
    }
    assert(false);
}

int main() {
    solve();
    return 0;
}