Submission #65071503

---

Source Code Expand

#include <stdio.h>
#include <ctype.h>
#include <limits.h>

#define NUM (1 << CHAR_BIT)

int N;
char S[212345];
char T[212345];

int to[NUM];

int visited[NUM];
char is_loop[NUM];
char cost_canceled[NUM];

int main(void) {
	int i;
	int ans = 0;
	int loop_ok = 0, loop_exists = 0;
	if (scanf("%d", &N) != 1) return 1;
	if (scanf("%212344s", S) != 1) return 1;
	if (scanf("%212344s", T) != 1) return 1;
	for (i = 0; i < N; i++) {
		int f = (unsigned char)S[i], t = (unsigned char)T[i];
		if (to[f] != 0 && to[f] != t) {
			puts("-1");
			return 0;
		}
		to[f] = t;
	}
	/* 明らかにループ可能か (空き文字があるか) をチェックする */
	for (i = 1; i < NUM; i++) {
		if (islower(i) && to[i] == 0) {
			loop_ok = 1;
			break;
		}
	}
	/* ループをカウントする */
	for (i = 1; i < NUM; i++) {
		int cur = i;
		int steps = 0;
		while (to[cur] != 0 && to[cur] != cur) {
			if (visited[cur] == i) {
				/* ループである */
				loop_exists = 1;
				is_loop[i] = 1;
				ans++;
				break;
			} else if (visited[cur] != 0) {
				/* 調査済のところに着いた */
				int v = visited[cur];
				if (cur != i && is_loop[v] && !cost_canceled[v]) {
					cost_canceled[v] = 1;
					ans--;
				}
				break;
			}
			visited[cur] = i;
			cur = to[cur];
			steps++;
		}
		if (cur != i) {
			/* ループや行き止まりに至る前に、置換元の数字がある */
			loop_ok = 1;
			/* 今回ループで、スタート位置はループ外だった */
			if (is_loop[i]) {
				cost_canceled[i] = 1;
				ans--;
			}
		}
	}
	if (loop_exists && !loop_ok) {
		puts("-1");
		return 0;
	}
	/* 置換をカウントする */
	for (i = 1; i < NUM; i++) {
		ans += to[i] != 0 && to[i] != i;
	}
	printf("%d\n", ans);
	return 0;
}

/*

ある文字が複数種類の文字になる → 無理 (失格)
ループがある → 一旦使っていない文字に退避して処理する 使っていない文字がなければ失格

26
abcdefghijklmnopqrstuvwxyz
bacdefghijklmnopqrstuvwxxz

このとき、使われていない文字は無いが、まずyをxにするとyが空くので退避できる
よって、「使っていない文字がなければ失格」は嘘

26
abcdefghijklmnopqrstuvwxyz
bacdefghijklmnopqrstuvwxaz

b → y
a → b
y → a

の3回でいけるが、工夫しないと 4 が出てしまう

通常、ループがある場合は退避によりコストが1増えるが、
ループ外からループに入る文字がある場合、退避先をその文字にすることで、
「退避先からループに戻す」と「その文字を欲しい文字にする」を重ねることができ、
コストが相殺される

26
abcdefghijklmnopqrstuvwxyz
badcefghijklmnopqrstuvwxaz

b → y
c → b
d → c
b → d
a → b
y → a

26
abcdefghijklmnopqrstuvwxyz
bcbdefghijklmnopqrstuvwxyz

c → a
b → c
a → b

ループにおけるコストの相殺判定が、1セットでループ外からループに入ると、行われない

*/

Submission Info

Judge Result