↓問題のページ↓
AtCoder Beginner Contest 345 C - One Time Swap
※本記事は0-indexedを前提として記載する。
＜内容の振り返り・解法＞
方針はすぐに思い浮かんだものの、C++の言語仕様を知らなかったために80分近く無駄に時間を失い、低いパフォーマンスに終わった。
単純に\(i\)と\(j\)を全探索するのでは\( \mathcal{O}(N^2) \)の処理となり、\(N\)が最大で\(10^6\)まで達する問題であることからTLEとなってしまうため工夫して高速化が必要となる。
\(0 ≤ i ≤ N -1\)なる\(i\)を1つ決めた時、\(i < j\)なる\(j\)の選び方は、全部で\( (N-1-i) \)通りだけある。公式解説の通り、全ての\( (i,j) \)の組について、\(S_i\)と\(S_j\)が異なるのならば、この\( (N-1-i) \)通りは全て元の文字列\(S\)とは異なる文字列を創り出す\( (i,j) \)の選び方となる。\(i < j\)かつ\(S_i\)と\(S_j\)が等しいような\(j\)が\(d\)通りある場合、元の文字列\(S\)とは異なる文字列を創り出す\( (i,j) \)の選び方は、\( (N-1-i-d) \)通りとなる。このように、それぞれの\(i\)に対する適切な\(j\)の決め方を単純な数式で表すことができるため、\(d\)の値を高速に求めることができれば制限時間内に正解を出力させる処理に仕上げられると分かる。
\(d\)の値を求めるために二分探索を用いる。より具体的には、\(S\)中に文字\(c\)が\(M\)回登場し、\(S\)中におけるそれらの添字を小さい方から書き並べたリスト\(L_c\)が\begin{align} L_c = ( c_0 , c_1 , \dotsc, c_{M - 1} ) \end{align} となっているとする。ここで、\(i < c_k\)なる\(k\)のうち、\(c_k\)の値が最小であるものに注目すると、 \begin{align} d = M - k \end{align} と求められる。\(i < c_k\)なる\(k\)が存在しない場合は \begin{align} d = 0 \end{align} と分かる。また、2文字を入れ替える操作は必ず1回行わなければならず、操作を行った結果として\(S\)自身が現れた場合もその1通りを数え上げなければならないことを忘れないようにする必要がある。以上を踏まえて実装を記す。
＜具体的な実装＞
1)変数\(ans\)の値を\(0\)で初期化する。
2)\(i = 0, 1, \dotsc, N - 1\)について、\(S_i\)がaからzのうちのどれであるかを識別し、それぞれの文字用に用意した添字を記憶するリストに\(i\)を追加していく。
3)\(i = 0, 1, \dotsc, N - 1\)について、\(S_i = c\)として、\(S\)中における\(c\)の出現位置の添字を記憶したリスト\(L_c\)を対象に二分探索を実施し、\(i < c_k\)なる\(k\)のうち、\(c_k\)の値が最小であるものを求める。そのような\(k\)が存在する場合は\( d = M - k \)、\(i < c_k\)なる\(k\)が存在しない場合は\( d = 0 \)というように\(d\)の値を求める。\(ans\)に\(N-1-i-d\)の値を加算する。
4)手順2)で作り上げた26リストのうちいずれか1つでも要素数が2以上である場合は\(ans\)に\(1\)を加算する。
以上の4)までで計算した\(ans\)を出力すれば題意を満たす処理を実現できる。計算量は3)が最も重く、要素数\(N\)程度のリストを対象に\(N\)回の二分探索を実行することから、全体では\( \mathcal{O}(N\log N) \)の処理となる。
