問題一覧 > 通常問題

No.1951 Vanished AGCT (2)

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 51
作問者 : H20 / テスター : 蜜蜂 naskya
お気に入りにしたユーザー ProblemId : 7904 / 自分の提出
問題文最終更新日: 2022-05-21 00:40:42
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 344 (順位表) の他の問題:

Problem Statement

A string $s$ of $n$ characters consisting only of uppercase English letters is given as input.

You perform operations so that $s$ satisfies the condition. Output the minimum number of operations required.

Condition: $s$ does not contain any of the characters A,G,C,T

Performing the following steps 1. through 5. in order counts as one operation. You may not reorder the steps or skip any particular step.

Operation:

  1. Let $c_1$ be the total number of characters A,G,C,T contained in $s$
  2. Let $t$ be the string obtained by deleting the $c_1$-th character of $s$
  3. Let $c_2$ be the number of occurrences in $t$ of the $c_1$-th character of $s$
  4. Perform $c_2$ times the operation of replacing each character of $t$ with the next character in alphabetical order
    Here, the character $1$ position after Z in alphabetical order is considered to be A
  5. Replace $s$ with $t$

Input

$n$
$s$

Constraints

  • $ 1 \le n \le 5 \times10^{5}$
  • $|s|=n$
  • $s$ consists only of uppercase English letters
  • $n$ is an integer

Output

Output the minimum number of operations required until the condition is satisfied.

Print a newline at the end.

Sample

Sample 1
Input
11
ABRACADABRA
Output
2

The string changes as ABRACADABRA→EFVEGHEFVE→IYHJKHIYH.

Sample 2
Input
9
YUKICODER
Output
5

Sample 3
Input
19
ATCODERGRANDCONTEST
Output
18

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