問題一覧 > 通常問題

No.295 hel__world

レベル : / AI推定難易度 : 2450 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : shimomire / テスター : uwi
お気に入りにしたユーザー ProblemId : 400 / 自分の提出
問題文最終更新日: 2026-10-21 22:25:38
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 124 (順位表) の他の問題:

Problem Statement

The number of connected components of a string $S$ is defined as the length of the string after performing the following operation as many times as possible.
Operation: if there is a place where the same character appears 2 or more times in a row, remove 1 character from it.
For example, the number of connected components of "helloworld" is $9$, and that of "aababbaaa" is $5$.

The $T$-count of $S$ is defined as the number of subsequences $T$ contained in the string $S$.
For example, let $S$ be helloworld and $T$ be helworld. Since helloworld has the 2 subsequences hel__world and he_l_world, the helworld-count of helloworld is $2$.

You are given the number of characters of each letter in the string $S$, and the string $T$.
Find the maximum $T$-count over strings $S$ satisfying the following 2 conditions.
・The number of characters $alpha$ contained in $S$ is at most $S_{alpha}$
・The number of connected components of $S$ equals the number of connected components of $T$
Note that the answer can be very large, so if it is $2^{62}$ or greater, output "hel" instead.
Also, if no $S$ satisfying the 2 conditions exists, output $0$.

Input

$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}$ means that the string $S$ contains $S_{alpha}$ characters $alpha$.
The strings $S$,$T$ consist only of the characters $a,b,\cdots,z$ (lowercase letters).

Output

Output on one line the maximum $T$-count obtainable by rearranging $S$, or "hel".
Print a newline at the end.

Sample

Sample 1
Input
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
Output
4

In this case, $S$ is a string obtained by rearranging helloworld.
If $S$ is hellwoorld, the helworld-count is 4, which is the maximum.

Sample 2
Input
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
Output
6

Considering strings with the same number of connected components as hello, the hello-count of helllooo is not used here; helloo-type arrangement helllo o is not needed: the hello-count of hellloo is 6, which is the maximum.

Sample 3
Input
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
Output
hel

If the answer is huge, output "hel".

Sample 4
Input
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
Output
1260

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