Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

Codeforces Round #598 - F. Equalizing Two Strings

codeforces.com

概要

2つの長さNの文字列S, Tが与えられる。次の操作を任意回行えるとして、SとTを一致させることはできるか?

  • x <= Nとなるようなxを選ぶ。Sの中で長さxとなる連続部分列を1つ選び、Tの中で長さxの連続部分列をまた、1つ選ぶ。そして、選んだ連続部分列を、同時に反転させる。

例えば、S="sen", T="shojin"でx=3の連続部分列を次のように選べる。
S'="sen", T'="hoj"
これを同時に入れ替えると、S="nes", T="sojhin"になる。

制約: 1 <= N <= 2 * 10^5

ACするまで

1. ひとまず、絶対に不可能なのは、構成する文字の種類と数が一致しない場合。
2. 転倒させるという作業は、なかなか扱いづらい。回文みたいなのが絡むかと思いきや、そうでもなかったりする。
3. 何回行ってもいいので、転倒させるという作業を分解して言い換えできないか?と考える。
4. よく考えてみると、転倒させるという作業は、隣接同士のswap(長さ2の連続部分文字列での反転)で構成できる。
5. 反転すると考えれば、転倒数の偶奇を考えるのが定石!
6. 転倒数に至るまでのほかのコーナーケースも、個の考察ルートで排除できるので、勝った。

考察

明らかにできないのが、構成してる文字の種類と数が一致してない場合である。


Point
扱いづらそうな操作が与えられたら、簡単な操作に言い換えられるか?を考える!

今回の場合、無限回行える区間反転の果てに、一致するか?という判定は、区間反転と考えると考察しづらい。
しかし、区間反転」という操作は、「隣同士をswap」という操作の積み重ねででき、しかもこの操作も長さ2の区間反転とみなせる。

というわけで、区間反転ではなく、隣同士のswapを代わりに行うと考える。

さて、隣同士をswapという操作は、バブルソートというソートの中の行われる手順として非常に有名で、転倒数とかが絡むことも多い。

とりあえず、S(Tもそうだが)をソートした文字列をtargetとして、そのtargetになるまでの回数、すなわち転倒数を求めてみる。

両隣のswapという操作は、大学数学の群論などをやるとわかりやすいが、2回同じ場所をswapすることで、元に戻るという性質がある。(それはそう) 2つの転倒数の偶奇が一致すれば、この操作を繰り返すことで、一致させることができる。(隣り合ったものを2回swapを使って、手数潰せばよい)

というわけで、SとTの転倒数を計算して、これらの偶奇が同じならば、作れる、そうでなければ作れない、というのが大本の筋である。

ところで、これだけでは正解ではない。

先ほど、隣同士でのswapを2回繰り返すことで、偶数回転倒数が異なれば一致させることができた。しかし、これに似た操作ができる状況というのもあるのではないか?

これに似た操作ができる状況というのは、同じ文字が2つ以上使われてる時である。同じ文字が隣接してる時、何回swapしても変わらないので、何回でも操作回数を稼げるのだ。
この場合は、転倒数の偶奇関係なく、必ず作れる。

ACソースコード
Submission #74205985 - Codeforces

転倒数を使う場合を考えると、SegTreeで転倒数の計算をしなくても間に合う。

一言

一つ一つ、積み重ねるのみ