今日解いた競プロの問題。

ABC299-F: 解説AC。なぜ重複せずに数え上げられるか、解説を読んでも分からなかったのだが、ACコードを読んで消化していたら合点がいった。

2つのTの境界を総当たりし、それぞれの場合について「1番目のTの最後の文字の位置」「2番目のTの最後の文字の位置」を持って部分列DPらしく遷移する。これは良い。問題は重複の対処だ。

例えばS=aababだったとき、a/ababからT=a、TT=aaのケースが見つかるが、aa/babやaab/abからもT=aが見つかってしまう。この重複をどうやって取り除くかが問題だ。

部分列DPの基本は「インデックス列が辞書順最小となるものだけをカウントする」というものだが、これに従って考えると、先の例でTT=aaを取り出すのは0,1番目になる一方、TT=ababを取り出すのは0,2,3,4番目になる。aからabに遷移できない。

これをどうやって対処するかというと、まず2つのTの境界の文字は必ず採用するものとする。言い換えれば、2つのTの境界を総当たりするのではなく、2番目のTの最初の文字を総当たりする。これで書く場合についてTを探す。

• a/abab→T=a
• aa/bab→T=a
• aab/ab→T=a,ab
• aaba/b→T=b

これではまだ重複が消せていない。どうやって重複を消すかというとこれが思いつけなかったところで、「1番目のTの最後の文字」と「2番目のTの最初の文字」の情報が手に入っていることを用いる。2番目のTの最初の文字と同種の文字が、1番目のTの最後の文字と2番目のTの最初の文字の間にあるならば辞書順最小ではないのでカウントしない。

辞書順最小ではないことを判定するロジックもなるほどだったが、「DPで計算した上でカウントを行わない」という発想が自分にはなかった。あくまで途中計算のためだけにある数字というのを認めるというのは、言われてみれば普通の話だが思いつけなかった。