ABC345 - C - One Time Swap 自己解法
問題
結論
下記の手順で答えを求めることができます
文字列Sの中に何回文字が現れるか、それぞれ種類ごとに数え上げる。
「各々の種類が現れた回数」同士を掛けた数を合計する。
もし、1種類でも「2回以上現れた文字種」があれば、「2.で求めた数+1」が答え。なければ「2.で求めた数」が答え。
考察
与えられた文字列の中から2つの文字を選んで入れ替えます。この操作を1回だけ実施後、できる文字列としてあり得るものがいくつあるか求めてくださいという問題です。
全てのパターンをシミュレーションし、できた文字列を数え上げていくのでは計算量的に間に合わないことが予想されます。
そこで、計算量的に間に合うような方針を立てる考察を進めてみます。
実験として適当な文字列Sに対して、操作を1回だけ実施。その後の文字列はどのようなものになるか分析してみましょう。
すると、下記の2パターンのうちのどちらかに当てはまることが分かるはずです。
操作を実施後、与えられた文字列Sと異なる文字列になるパターン
操作を実施後、文字列Sから変わらないパターン
上記2パターンについて、「いつパターンが当てはまるか」「それぞれのパターンで作り得る文字列の数はいくつか」という観点で考察を進めます。
文字列Sと異なる文字列になるパターン
まず、「いつパターンが当てはまるか」についてです。
Sと異なるパターンが当てはまるときは、操作を実施するときに選ぶ文字の種類が異なる場合です。（「aとb」や「cとx」など）
次に「Sと異なるパターンで作り得る文字列の数はいくつか」についてです。
そのために、このパターンが起こる通り数は何通りかを考えます。
先ほど、Sと異なるパターンが起こるのは「選ばれた文字種が異なる場合」だと書きました。
そこで、文字列Sの中に何回文字が現れるか、それぞれ種類ごとに数え上げます。場合の数はその後で算出できます。
算出の仕方は「各々の種類が現れた回数」同士を掛けた数を合計すればいいです。
例:文字列Sが「aabcdcdd」の場合。
それぞれの文字種が現れた数を数える。
a:2
b:1
c:2
d:3
各々の現れた回数同士を掛けた数を合計する。
a b → 2 * 1 = 2
a c → 2 * 2 = 4
a d → 2 * 3 = 6
b c → 1 * 2 = 2
b d → 1 * 3 = 3
c d → 2 * 3 = 6
合計:23これで、Sと異なる文字列になるパターンの場合の数を数え上げることができます。
そして、このパターンで出来上がった文字列同士は、互いに重複することはあり得ません。なぜなら操作を実施するときに「選ぶ文字の位置」がそれぞれ異なっているからです。
ゆえに「文字列Sと異なる文字列になるパターンで作り得る文字列の数」は、文字列Sの中に何回文字が現れるか、それぞれ種類ごとに数え上げることで計算できることが分かります。
操作を実施後、文字列Sから変わらないパターン
まず、「いつパターンが当てはまるか」についてです。
これは、操作を実施するときに選ぶ文字の種類が同じ場合です。
すなわち、Sの中から同種の文字が1組でも存在すればこのパターンが存在することになります。
次に「Sから変わらないパターンで作り得る文字列の数はいくつか」についてです。
これは明らかに1つしかないことが分かります。
まとめると
文字列Sのの中に何回文字が現れるか、それぞれ種類ごとに数え上げる。
「各々の種類が現れた回数」同士を掛けた数を合計する。
もし、1種類でも「2回以上現れた文字種」があれば、「2.で求めた数+1」が答え。なければ「2.で求めた数」が答え。
と結論で出した手順で答えを求めることができます。
これだと計算量的にも間に合いそうです。(英小文字は26種類しかないため2.の計算も十分高速)
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。
この記事が気に入ったらサポートをしてみませんか？