【AtCoder】ABC 418 B - You're a teapot | 緑コーダーが解くAtCoder

atcoder.jp

配点: 200 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 123 / NoviSteps: 6Q

問題概要
制約
考察
実装例
コメント

問題概要

文字列 $t$ について、充填率を以下のように定義する。

$t$ の先頭と末尾の文字がともにtであり、かつ $|t| \geq 3$ である場合: $t$ に含まれるtの個数を $x$ とすると、 $t$ の充填率は $\displaystyle\frac{x-2}{|t|-2}$ である。
そうでない場合: $t$ の充填率は $0$ である。

英小文字からなる文字列 $S$ が与えられるので、 $S$ の連続部分文字列の充填率としてありうる最大値を求めよ。

制約

$1 \leq |S| \leq 100$

考察

$|S|$ の制約が小さいので、「 $S$ の連続部分文字列を列挙し、条件を満たした連続部分文字列に対して $x$ を愚直に求め、充填率を計算する」という $O(|S|^3)$ 解法が成立する。

$S$ の $l$ 文字目から $r$ 文字目までの連続部分文字列 $\mathrm{sub}$ は、S.substr(l, r - l + 1)で取得できる。

また、

$\mathrm{sub}$ の先頭の文字 : *sub.begin()
$\mathrm{sub}$ の末尾の文字 : *sub.rbegin()
$|\mathrm{sub}| = r - l + 1$

であることを踏まえれば、あとは素直に実装すればよい。詳細は実装例を参照のこと。

実装例

#include <bits/stdc++.h>
using namespace std;

#define fix(x) fixed << setprecision(x)
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    string S;
    cin >> S;

    double ans = 0;
    rep(l, 0, S.size()) rep(r, l + 1, S.size())
    {
        string sub = S.substr(l, r - l + 1);
        if (*sub.begin() == 't' && *sub.rbegin() == 't' && r - l + 1 >= 3)
        {
            int cnt = 0;
            rep(i, l, r + 1)
            {
                if (S[i] == 't')
                    cnt++;
            }

            chmax(ans, (double)(cnt - 2) / (r - l + 1 - 2));
        }
    }

    cout << fix(10) << ans << endl;
}