/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
長さ 2N で、0 と 1 をそれぞれ N 個含む文字列をよい文字列と呼びます。
よい文字列 S, T に対して、S の隣り合う 2 文字を入れ替える操作を 0 回以上行って T に一致させるために必要な操作回数の最小値を \operatorname{dist}(S, T) とします。
よい文字列 A, B, C が与えられます。すべてのよい文字列 X のうち、
\[ \operatorname{dist}(A, X)+\operatorname{dist}(B, X)+\operatorname{dist}(C, X) \]
の値を最小にするものを 1 つ求め、その最小値とともに出力してください。
制約
- 1 \le N \le 2 \times 10^5
- A, B, C はそれぞれ長さ 2N のよい文字列
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N A B C
出力
求める最小値を K とし、それを達成するよい文字列を X とする。 以下の形式で K と X を出力せよ。
K X
条件を満たす出力が複数存在する場合、どれを出力してもよい。
入力例 1
2 1100 1010 0011
出力例 1
4 1010
よい文字列 X として 1010 を選ぶと、\operatorname{dist}(A, X)、
\operatorname{dist}(B, X)、\operatorname{dist}(C, X) はそれぞれ 1, 0, 3 となり、その和は 4 です。
距離の和を 4 より小さくすることはできません。
入力例 2
3 101010 101010 101010
出力例 2
0 101010
入力された 3 つの文字列がすべて等しいため、X に同じ文字列を選ぶと距離の和は 0 です。
Score : 400 points
Problem Statement
A string of length 2N that contains N occurrences of each of 0 and 1 is called a good string.
For good strings S and T, let \operatorname{dist}(S, T) denote the minimum number of swaps required to make S equal to T by swapping two adjacent characters of S zero or more times.
You are given good strings A, B, and C. Among all good strings X, find one that minimizes the value of
\[ \operatorname{dist}(A, X)+\operatorname{dist}(B, X)+\operatorname{dist}(C, X), \]
and output it together with the minimum value.
Constraints
- 1 \le N \le 2 \times 10^5
- Each of A, B, and C is a good string of length 2N.
- N is an integer.
Input
The input is given from Standard Input in the following format:
N A B C
Output
Let K be the minimum value to be found, and let X be a good string that achieves it. Output K and X in the following format:
K X
If multiple outputs satisfy the conditions, you may output any of them.
Sample Input 1
2 1100 1010 0011
Sample Output 1
4 1010
If we choose 1010 as the good string X, then \operatorname{dist}(A, X), \operatorname{dist}(B, X), and \operatorname{dist}(C, X) are 1, 0, 3, respectively, and their sum is 4. The sum of the distances cannot be made smaller than 4.
Sample Input 2
3 101010 101010 101010
Sample Output 2
0 101010
Since the three input strings are all equal, choosing the same string as X makes the sum of the distances 0.