Yukicoder073 helloworld

問題概要

A君は、helloworldを愛してやまない． 文字列Sのhelloworld数を次を満たす組$(i_0,⋯,i_9)$の個数とする。

$S[i_0]S[i_1]⋯S[i_9]=“helloworld”$,$(i_0<i_1<⋯<i_9 )$
アルファベットの個数が与えられるので、 それぞれのアルファベットをちょうどその個数だけ使ってできる文字列におけるhelloworld数の最大値を求めよ。

$C_i\leqq10^2$

yukicoder073

解法

複数登場する”O”,“L”の配置のみ考えればよく、他の文字は一箇所に配置しないとそもそも選択できない。
Oは二箇所に配置するので、[x]…[y]のように配置すると考える。これは$x+y=\sum”O”,max${ $xy$ }なので$O(1)$で求められる。
Lも二箇所に配置する。[xy]..[z]のように配置なので、これは$x+y+z=\sum”L”$,$max${$xyz$}で一見大変そうだが、$xy$は連続なので、
$max${$comb(x+y,2)*z$}と実質2変数になり、簡単に求められる。
極値も取れそうだけど、面倒なので計算させれば良い。

計算量:$O(\sum “L”)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        VI cnt(26, 0);
        for (int&i : cnt) {
            cin >> i;
        }
        string s = "hewrd";
        LL ans = 1;
        FOR(i, 0, SZ(s)) {
            ans *= cnt[s[i] - 'a'];
        }
        int O = (cnt['o' - 'a']);
        int x = (O + 1) / 2;
        ans *= (-x*x + O*x);
        int ret = 0;
        int L = (cnt['l' - 'a']);
        FOR(i, 1, L) {
            int leftL = L - i;
            int comb = leftL*(leftL - 1) / 2;
            ret = max(ret, i*comb);
        }
    
        ans *= ret;
        cout << ans << "\n";
    
        return 0;
    }