AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の84問目である「There are two types of characters（★3）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【084 – There are two types of characters（★3）】
考察
問題文
o と x からなる長さ N の文字列 S が与えられます。以下の条件をすべて満たす整数の組 (l,r) の個数を求めてください。
- \(1 < l < r < N\)
- S の l 文字目から r 文字目までの区間に、o と x 両方が含まれる
概要
長さ \(N\) の文字列 \(S\) が与えられ、この文字列の中で「o」と「x」が両方含まれる区間 (l,r) の組み合わせの数を求める問題を解説します。
問題の考察
この問題は、直感的には全ての l と r について調べることを考えがちですが、その方法では計算量が \(O(N^2)\) となり、時間制限に間に合わない可能性があります。そこで、しゃくとり法を用いて効率的に解く方法を考えます。
しゃくとり法の活用
しゃくとり法は、2つのポインタ（今回の場合は l と r）を使って、区間の長さや合計値などを効率的に計算する手法です。この問題では、\(l<R\) という条件のもとで、「o」と「x」が両方含まれる区間を見つけ出します。
実装のポイント
- 初期化: 文字列 S を受け取り、解答用の配列 ans を初期化します。
- しゃくとり法の適用: 左端のポインタ left と右端のポインタ right を用いて、条件を満たす区間を探索します。
- 区間のカウント: 条件を満たす区間が見つかった場合、その区間に対応する ans の要素を更新します。
典型解法：しゃくとり法
コード
N = int(input()) # 文字列の長さ N を入力
letter = input() # 文字列 S を入力
left = 0 # 左端のポインタを初期化
ans = [0 for i in range(N)] # 各位置における答えを格納する配列を初期化
# 右端のポインタ right を 1 から N-1 まで動かす
for right in range(1, N):
# 左端と右端の文字が同じ場合、次の right へ
if letter[left] == letter[right]:
continue
# 左端から right-1 までの各位置について、条件を満たす区間の数を計算
for j in range(left, right):
ans[j] = N - right
left = right # 左端のポインタを更新
# ans の合計を出力（最後の要素は除く）
print(sum(ans[:-1]))
まとめ
この問題は、しゃくとり法を活用して効率的に解くことができます。左端と右端のポインタを適切に動かしながら、条件を満たす区間を見つけ出し、その数をカウントすることで、計算量を削減することができます。
コメント