問題一覧 > 通常問題

No.1951 消えたAGCT(2)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 48
作問者 : 👑 H20H20 / テスター : naskyanaskya 蜜蜂蜜蜂
0 ProblemId : 7904 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-21 00:40:42

問題文

英大文字のみからなる $n$ 文字の文字列 $s$ が入力として与えられます。

$s$ が条件を満たすように操作を行います。必要な操作の最小の回数を出力してください。

条件:$s$ にA,G,C,Tの文字が含まれない

以下の 1. から 5. までの手順を順番に通して行うことを一回の操作とします。手順を入れ替えたり、特定の手順を省略したりすることはできません。

操作:

  1. $s$ に含まれる A,G,C,Tの文字数の合計を $c_1$ とする
  2. $s$ の $c_1$ 文字目を削除した文字列を $t$ とする
  3. $t$ に含まれる $s$ の $c_1$文字目の文字数を $c_2$ とする
  4. $t$ の各文字を、アルファベット順で次の文字にそれぞれ置き換える操作を $c_2$ 回行う
    ただし、アルファベット順で Z の $1$ 個後の文字は A とみなす
  5. $s$ を $t$ に置き換える

入力

$n$
$s$

制約

  • $ 1 \le n \le 5 \times10^{5}$
  • $|s|=n$
  • $s$ は英大文字のみからなる
  • $n$ は整数

出力

条件を満たすまでに必要な操作の最低回数を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
11
ABRACADABRA
出力
2

ABRACADABRAEFVEGHEFVEIYHJKHIYHと置き換わります。

サンプル2
入力
9
YUKICODER
出力
5

サンプル3
入力
19
ATCODERGRANDCONTEST
出力
18

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