# ABC299 F Square Subsequence 解説

本記事では、東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 299）のF問題(500点)"[Square Subsequence](https://atcoder.jp/contests/abc299/tasks/abc299_f)"の自分の思考の過程について説明します。
本記事の方向性については[初回記事](https://hackmd.io/@carrot46/r1kru7Z6s)を参照してください。
特に、本記事では問題の性質の観察を重視していて、アルゴリズムを構築するパートは少ししか言及していないため、アルゴリズム構築に関しては[公式解説](https://atcoder.jp/contests/abc299/editorial/6251)の後半などを参照してください。
また、序盤に[競プロ典型90問](https://atcoder.jp/contests/typical90)の問題の解法についての言及があるので、ネタバレを避けたい場合は注意してください。

目次
- [問題概要](#問題概要)
- [最初に考えたこと](#最初に考えたこと)
- [数え上げの重複について](#数え上げの重複について)
- [部分列の扱い方](#部分列の扱い方)
- [左詰めで部分列を作れない理由](#左詰めで部分列を作れない理由)
- [左右の部分列の自由度](#左右の部分列の自由度)
- [分からない値のみ全探索するDP](#分からない値のみ全探索するDP)
- [思考の過程のまとめ](#思考の過程のまとめ)

## 問題概要

英小文字からなる文字列 $S$ が与えられます。下記の条件を満たす空でない文字列 $T$ の個数を $998244353$ で割ったあまりを出力してください。

> $T$ を $2$ つ連結して得られる文字列 $TT$ が、$S$ に（連続とは限らない）部分列として含まれる。

制約：$1 \leq |S| \leq 100$
（引用：[F - Square Subsequence](https://atcoder.jp/contests/abc299/tasks/abc299_f)）

## 最初に考えたこと

問題設定が非常に単純ですが、数え上げの問題においてどういった点に注意すべきかを中心に、問題の性質について考察していきます。

### 数え上げの重複について

数え上げる対象について、どの $2$ つを区別し、どの $2$ つを同一視するかの定義はしっかり意識した方が良いです。
今回であれば、「$TT$ が $S$ の部分列であるような文字列 $T$ の個数」を計算しますが、$S$ の部分列と $T$ は一対一では対応していない（前者の方がパターンが多くなりうる）ことに注意が必要です。
例えば入力例 2 にあるように、$S=$`zzz` ならば、 $T$ として考えられるのは `z` のみですが、$S_1S_2, S_2S_3, S_1S_3$ の $3$ 通りの部分列が $TT$ に一致しています。
このことについては、問題文を読むときもアルゴリズムを構築する時も常に意識しましょう。

### 部分列の扱い方

数え上げる対象は $T$ の個数ですが、実際に数え上げる場合に $T$ の全列挙（指数個）をやるわけにも行かないので、以降では $S$ の部分列に注目した考察を行うことになります。
部分列を扱う際に押さえておきたいのが、次の規則に基づく部分列の構築方法です。

- $S$ の $i$ 番目までの文字を使って部分列 $T$ を構築しているとする。次にアルファベット $\sigma$ を追加する場合、**$i+1$ 番目以降で最も左にある $\sigma$** を選び、$T$ の末尾に追加する。

他の問題では、[競プロ典型90問](https://atcoder.jp/contests/typical90)の問題006"[Smallest Subsequence](https://atcoder.jp/contests/typical90/tasks/typical90_f)"でも扱われている考え方です。
（この問題に限らず、競プロ典型90問は良い問題が揃っているので、コンテスト参加以外に競プロに時間を割ける方は取り組んでみることをお勧めします。）

この構築方法は、「結果（$T$ の形）が等しくなる複数の操作がある時、**その後の操作の自由度が一番高い状態**（$=S$ の文字を出来るだけ多く使える状態）を選ぶ」という考え方で説明できます。
例えば、$S=$`zzyyx`に対して、$T=$`z`に`y`を追加するときに、

- $T=S_1S_3=$`zy` と追加すれば、この後 $T=S_1S_3S_4=$`zyy` を作れる
- $T=S_1S_4=$`zy` と追加すると、`zyy` を作ることが出来ない

という違いが表れます。
このことも含めて、この構築方法には次の2つの特徴があります。

1. 部分列として構築できるものを全て考えることが出来る
2. $S$ から選ぶ箇所と、構築した部分列 $T$ が一対一対応する

この特徴について、「典型として暗記する」ことも一つの手だと思います[^典型暗記]が、どういった考えからこの方法を導けるかを理解しておくと、将来的に忘れた時も再構築できたり、似たような考え方に基づく別の考察に活きる場合もあります。

[^典型暗記]: 解けなかった問題に対して、「この部分を典型として意識するだけで次は解ける」といった分析をした場合は、典型を覚える意識をするとよいと思います。

## 左詰めで部分列を作れない理由

部分列の扱い方について学びましたが、改めて問題を確認すると、最も左の $\sigma$ を使う方針では困った点があります。
今回の問題では、$T$ を一文字決める ($\sigma$ を追加する) と $S$ の中の二文字 $S_i, S_j \,(i < j, \sigma = S_i = S_j)$ を使うこととなりますが、**$S_j$ については、出来るだけ左の $\sigma$ ($=$ 出来るだけ小さい $j$ ) を使えば良いとは限りません**。
単純な例として、$S=$`zzzz` とすると、一旦 $T=$`z`とするときに $TT = S_1S_2$ のように左詰めして使うと、$T=$`zz` が作れなくなってしまいます。
一方で、$TT=S_1S_3$ としておくと、$(T+S_2)(T+S_4)$ のように追加すれば $T=$`zz` が作れます。

こういった場合、すぐに先ほどの構築方法を諦めるのではなく、**ダメである理由・性質**を明確にすることが大切です。
先ほどの例で言えば、$T=$`z` としている途中経過を $TT=S_1S_k$ として、$k=3$ の場合のみ $T=$`zz` が作れますが、

- $k=2$ : 左の $T$ をこれ以上伸ばせなくなってしまう
- $k=4$ : 右の $T$ をこれ以上伸ばせなくなってしまう

といったように、他の $k$ では左の $T$ と右の $T$ のどちらかの構築自由度が下がってしまっていることが分かります。

## 左右の部分列の自由度

それでは、右の $T$ に対応する部分列の各文字の位置について、どのように決めればよいでしょうか。
ここで、先ほどの具体的な考察から、左右の部分列の構築の自由度について考えると、次のことが言えます。

- $T$ の一文字目を決める際に、右の $T$ を $S$ のどこから始めるかによって、その後の自由度が変わってしまう。
- しかし、二文字目以降の取り方は左右の $T$ の自由度について相互に干渉することがないので、最も左の $\sigma$ を取れば良い。

では、右の $T$ を始める位置は予め決定できるのでしょうか。どんな $T$ を作るか分からない状態で位置を定めることは難しそうですが、今回は制約が小さいため、「開始位置を全部試してみる」という方法を取ることが出来ます。

## 分からない値のみ全探索するDP

以上の話より、右の $T$ を始める位置について全てのパターンを試す($=$予め固定しておく)方法が考えられます。
すると、[公式解説](https://atcoder.jp/contests/abc299/editorial/6251)のように、各開始位置のパターンに対して、状態数が $O(N^2)$、遷移数が $O(\Sigma)$ のDPで解くことが出来ます。始める位置が $O(N)$ 通りであることも踏まえると、全体で $O(N^3 \Sigma)$ で計算できます。
この部分は公式解説に詳細な説明があるため省略しますが、アルゴリズム構築の際にも、重複や数え残しなく数え上げられているか？は常に意識する必要があります(dpの更新や答えの計算の際にdpテーブルのどの値の合計を取るか等)。
自分は、コンテスト中は「左の$T$の末尾の位置を予め固定しておく」という方針で通しました[^自分の実装]。

[^自分の実装]: 読みにくいですが提出は[こちら](https://atcoder.jp/contests/abc299/submissions/40860455)。57行目では、答えが一文字のものだけ先に足してあります。

## 思考の過程のまとめ

本記事では、AtCoder でもよく出る数え上げの問題について、重複の扱い方や、複数の取り方の内最も自由度が高い操作を行う、といった考え方を解説しました。
特に、数え上げを言い換えるときに「問題で問われていることと一対一対応しているか？」という点は常に意識すると良いと思います。

今回書いた内容は全てコンテスト中に意識したことですが、ほとんどはすでに一回以上は触れたことのある考え方を思い出す形で考えていて、新たに考えたのは「左詰めで部分列を作れない理由」以降の一部のみだったと思います。
そういう意味で、今回の自分の解き方はかなり経験依存ではありますが、途中で出てきた考察手法の捉え方や、解くために必要な考え方を効率良く引き出すための問題との向き合い方については、参考になる方もいらっしゃるのではと思い、記事を作成しました。
本記事が数え上げの問題の考察の助けになれば幸いです。