問題一覧 > 通常問題

No.295 hel__world

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 15
作問者 : shimomireshimomire / テスター : uwiuwi
2 ProblemId : 400 / 出題時の順位表
問題文最終更新日: 2018-03-10 02:10:36

問題文

文字列$S$の連結成分の個数を、次の操作を行えるだけ行った後の文字列長さとして定めます。
操作:同じ文字が2文字以上連続する箇所があれば、そこから1文字取り除く
例えば「helloworld」の連結成分の個数は$9$、「aababbaaa」の連結成分の個数は$5$となります。

$S$ の $T$ 数を文字列 $S$ が含む部分列 $T$ の個数とします。
例えば、$S$をhelloworld、$T$をhelworld とすると、helloworldはhel__worldとhe_l_worldの2つを部分列として持つので、helloworld の helworld 数は $2$ です。

文字列 $S$ の各アルファベットの文字数 と 文字列 $T$ が与えられます。
次の2条件を満たす文字列$S$に対する、$T$数の最大値を求めてください。
・$S$に含まれる文字$alpha$の個数は高々$S_{alpha}$
・$S$の連結成分の個数と$T$の連結成分の個数は等しい
ただし、答えが非常に大きくなる場合があるので $2^{62}$ 以上になる場合は"hel"を出力してください。

入力

$S_a$ $S_b$ $S_c$ $S_d$ $S_e$ $S_f$ $S_g$ $S_h$ $S_i$ $S_j$ $S_k$ $S_l$ $S_m$ $S_n$ $S_o$ $S_p$ $S_q$ $S_r$ $S_s$ $S_t$ $S_u$ $S_v$ $S_w$ $S_x$ $S_y$ $S_z$
$T$

$0 \le S_{alpha} \le 10^{18}$ ( $alpha \in \{a,\cdots, z\}$)
$1 \le |T| \le 10^6$
$S_{alpha}$ は、文字列 $S$ に文字 $alpha$ が $S_{alpha}$ 文字含まれていることを表す。
文字列 $S$,$T$が含む文字は、$a,b,\cdots,z$(小文字のアルファベット)のいずれかである。

出力

$S$を並び替えて得られる最大の $T$ 数または "hel" を一行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
0 0 0 1 1 0 0 1 0 0 0 3 0 0 2 0 0 1 0 0 0 0 1 0 0 0
helworld
出力
4

この場合 $S$ は、helloworldを並び替えて得られる文字列になります。
$S$ をhellwoorldとするとhelworld数は 4 でこの時最大になります。

サンプル2
入力
0 0 0 1 1 0 0 1 0 0 0 3 0 0 2 0 0 1 0 0 0 0 1 0 0 0
hello
出力
6

helloとの連結数が同じ文字列として考えるとhelllooのhello数は 6 でこの時最大になります。

サンプル3
入力
100 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
abababababababababababababababab
出力
hel

答えが巨大になる場合は、 "hel" を出力してください。

サンプル4
入力
9 1 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0
iauba
出力
1260

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。