Codeforces Round 498(Div.3) D. Two Strings Swaps

Problem - D - Codeforces

問題概要

長さ $N$ の2つの文字列a,bが与えられる。文字列はともに小文字のアルファベットから構成される。
はじめに、好きな回数だけ以下の置換操作を行うことができる。

$1 \le i \le N$ となる $i$ を一つ選び、 $a_i$ を任意のアルファベットに置換する

その後、以下の3つの操作を繰り返して文字列a,bを等しくしたい。

$1 \le i \le N$ となる $i$ を一つ選び、 $a_i$ と $b_i$ を入れ替える
$1 \le i \le N$ となる $i$ を一つ選び、 $a_i$ と $a_{n-i+1}$ を入れ替える
$1 \le i \le N$ となる $i$ を一つ選び、 $b_i$ と $b_{n-i+1}$ を入れ替える

最初の置換操作の回数の最小値を求めよ。

制約

$1 \le N \le 10^5$

解法

$1 \le i \le N$ となる $i$ を一つ選び、 $a_i$ と $b_i$ を入れ替える
$1 \le i \le N$ となる $i$ を一つ選び、 $a_i$ と $a_{n-i+1}$ を入れ替える
$1 \le i \le N$ となる $i$ を一つ選び、 $b_i$ と $b_{n-i+1}$ を入れ替える

の3つの操作をすることによって、{ $a_i$ , $a_{n-i+1}$ , $b_i$ , $b_{n-i+1}$ }を自由に入れ替えることができる。
また、 $i \neq j$ のとき、{ $a_i$ , $a_{n-i+1}$ , $b_i$ , $b_{n-i+1}$ }と{ $a_j$ , $a_{n-j+1}$ , $b_j$ , $b_{n-j+1}$ }は独立している。
よって、 $1 \le i \le \frac{N}{2}$ について置換操作の回数を計算して足し合わせればよい。

{ $a_i$ , $a_{n-i+1}$ , $b_i$ , $b_{n-i+1}$ }の4つの文字が全て等しければ置換操作はしなくてよい。
また、{ $a_i$ , $a_{n-i+1}$ , $b_i$ , $b_{n-i+1}$ }に2つの等しい文字が含まれているときも置換操作はしなくてよい。

そうでないとき、 $a_i$ と $a_{n-i+1}$ の片方だけを置換すればいいか、両方とも置換する必要があるかを調べればよい。