問題一覧 > 通常問題

No.2454 Former < Latter

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 81
作問者 : srjywrdnprktsrjywrdnprkt / テスター : 👑 p-adicp-adic
3 ProblemId : 9858 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-21 08:05:57

問題文

英小文字のみからなる長さ $N$ の文字列 $S=S_1S_2\cdots S_N$ が与えられます。

$1\leq i\leq N-1$ を満たす整数 $i$ のうち、$S$ を $i$ 文字目で分割することで得られる文字列の前半を $U=S_1\cdots S_i$、後半を $V=S_{i+1}\cdots S_N$ とするとき、$U$ が辞書順で $V$ より真に小さくなるものの総数を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

$T$
$case_1$
$\vdots$
$case_T$
ここで、$case_i$ とは $i$ 個目のテストケースである。各テストケースは以下の形式で与えられる。 
$N$
$S$

入力は以下の制約を満たす。

  • $T, N$ は整数
  • $1\leq T$
  • $2\leq N$
  • $S$ は英小文字のみからなる長さ $N$ の文字列
  • $1$ 個の入力に含まれるテストケースについて、それらの $N$ の総和は $3\times 10^5$ を超えない。

出力

$T$ 行出力してください。$i$ 行目には $i$ 番目のテストケースに対する答えを出力してください。

サンプル

サンプル1
入力
3
6
banana
26
abcdefghijklmnopqrstuvwxyz
7
xxxxxxx
出力
2
25
3

$1$ つ目のテストケースについて、

  • $i=1$ のとき、$U=b, V=anana$ で $U > V$ です。
  • $i=2$ のとき、$U=ba, V=nana$ で $U < V$ です。
  • $i=3$ のとき、$U=ban, V=ana$ で $U > V$ です。
  • $i=4$ のとき、$U=bana, V=na$ で $U < V$ です。
  • $i=5$ のとき、$U=banan, V=a$ で $U > V$ です。
よって、条件を満たす $i$ は $i=2, 4$ の $2$ 個あります。

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