C - One Time Swap
https://atcoder.jp/contests/abc345/tasks/abc345_c
問題文
文字列
S が与えられます。次の操作を ちょうど
1 回 行った後の文字列としてあり得るものがいくつあるか求めてください。
S の長さを N とする。 1≤i<j≤N をみたす整数の組 (i,j) を選び、S の i 文字目とj 文字目を入れ替える。
なお、この問題の制約下で操作を必ず行うことができることが証明できます。
制約
S は英小文字からなる長さ 2 以上 10^6 以下の文字列
ふつうにやればもちろんLTEなので考えないといけない。
https://atcoder.jp/contests/abc345/editorial/9575
こちらの解説ではまず
- vector で同じ文字の数を数えておく cnt[((int)(s[i]-'a'))]++;
- 全部のswapの数をまずansに入れておく ans = n*n; この中には自分自身を自分とswap する数も入っている。
- そこから同じ文字と同じ文字をswapするものを引いていく ans -= cnt[i]*cnt[i];この中には自分自身を自分とswap する数も入っている。
- swap は一方向だけ考えればいいので ans/=2
- 同じ文字があった場合 if(cnt[i]>1) 最後にans に1つ足す。なぜなら swap しなかった状態(元と同じ)がswap後にあるはずなのにそれは ans -= cnt[i]*cnt[i] で引かれてしまっているから。
まとめ
文字をswapしてと出たら絶対swapしてはだめ。TLEになる。
swapした全パターンの数から特別なswapパターンの数を引く。