問題一覧 > 通常問題

No.2073 Concon Substrings (Swap Version)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 113
作問者 : 👑 AngrySadEightAngrySadEight / テスター : sapphire__15sapphire__15
0 ProblemId : 8299 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-16 16:55:22

問題文

英小文字からなる長さ $3N$ の文字列 $S$ が与えられます．この文字列 $S$ に対して，次に示す操作を，$0$ 回以上の好きな回数行うことができます．

  • 操作： $1 \leq i \leq 3N - 3$ なる整数 $i$ をひとつ選ぶ．$S_i$ と $S_{i+3}$ を入れ替える．

ただし，$S_i$ で文字列 $S$ の左から $i$ 番目の文字を表します．

操作後の $S$ の中に含まれる連続する部分列 con の個数の最大値を求めてください．

入力

$N$
$S$

  • $N$ は整数である．
  • $1 \leq N \leq 2 \times 10^5$
  • $S$ は英小文字からなる長さ $3N$ の文字列である．

出力

答えを出力せよ．

サンプル

サンプル1
入力
3
toscenter
出力
1

次のように操作を行えばよいです．

  • $i=1$ を選び，$S_1$ と $S_4$ を入れ替える．toscenter → costenter となる．
  • $i=3$ を選び，$S_3$ と $S_6$ を入れ替える．costenter → contester となる．
このようにして操作を行うことで，文字列 $S$ に含まれる連続する部分列 con の個数は $1$ になり，これが最大です．

サンプル2
入力
3
conconfox
出力
2

操作を行うまでもなく，文字列 conconfox に含まれる連続する部分列 con の個数は $2$ となり，これが最大です．

サンプル3
入力
5
kudagitsunecoon
出力
0

どのように操作を行っても，連続する部分列 con を作ることはできません．

サンプル4
入力
9
yukicoderprogrammingcontest
出力
2

サンプル5
入力
33
paracetamoxyfrusebendroneomycinsupercalifragilisticexpialidocioussupercalifragilisticexpialidocious
出力
3

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