TCO12 R1C 1000pt : PasswordXPalindrome

問題概要

与えられた文字列を最小何回のスワップで回文にできるか求める問題。無理なら指摘する。

解法

まず、できるかどうかは奇数回出現する文字を数えれば良い。もし奇数回出現する文字が真ん中にないのなら、まずスワップして真ん中に持っていく。
後は貪欲っぽくやればよい。文字が前半に余分にあるならそれを後ろにもっていったり、文字の回数が同じなら後ろの中でスワップしたりするのを注意深く実装すれば良い。ただ、もう少し綺麗な解法もありそう。

acceptされたコード

#include <string>
#include <cstdio>
using namespace std;

int cnt[0x100];
int fcnt[0x100];

struct PasswordXPalindrome {

	int minSwaps(string password) {
		if(password.length()%2 == 0){
			password = password.substr(0, password.length()/2) + string(1, 'z' + 1) + password.substr(password.length()/2);
		}
		puts(password.c_str());

		const int L = password.length();
		for(int i=0; i<L; ++i){
			++cnt[password[i]];
		}

		int ans = 0;
		int odd = 0;
		for(char c='a'; c<='z' + 1; ++c){
			odd += (cnt[c]&1);
		}
		if(odd > 1){
			return -1;
		}
		for(char c = 'a'; c<='z' + 1; ++c){
			if( (cnt[c]&1) && password[L/2] != c){
				int cf = 0, cs = 0, kf = -1, ks = -1;
				for(int i=0; i<L/2; ++i){
					if(password[i] == c){
						++cf;
						if(password[i] != password[L-1-i]){
							kf = i;
						}
					}
				}
				for(int i=L/2+1; i<L; ++i){
					if(password[i] == c){
						++cs;
						ks = i;
						if(password[i] != password[L-1-i]){
							ks = i;
						}
					}
				}
				if(cf > cs){
					swap(password[L/2], password[kf]);
				}
				else{
					swap(password[L/2], password[ks]);
				}

				++ans;
			}
		}
		puts(password.c_str());

		for(int i=0; i<L/2; ++i){
			++fcnt[password[i]];
		}

		for(int i=0; i<L/2; ++i)if(password[i] != password[L-1-i]){
			++ans;
			//前と後ろで数は合っている
			if(fcnt[password[i]] == cnt[password[i]] / 2){
				int key = -1;
				for(int j=L/2+1; j<L; ++j){
					if(password[i] == password[j] && password[j] != password[L-1-j]){
						key = j;
					}
				}
				swap(password[L-1-i], password[key]);
			}

			//前に余りがある
			else if(fcnt[password[i]] > cnt[password[i]] / 2){
				int key = -1;
				for(int j=i+1; j<L/2; ++j){
					if(password[i] == password[j] && password[j] != password[L-1-j]){
						key = j;
					}
				}
				++fcnt[password[L-1-i]];
				--fcnt[password[key]];
				swap(password[key], password[L-1-i]);
			}

			//後ろに余りがある
			else if(fcnt[password[i]] < cnt[password[i]] / 2){
				int key = -1;
				for(int j=L-2-i; j>=L/2 + 1; --j){
					if(password[i] == password[j] && password[j] != password[L-1-j]){
						key = j;
					}
				}
				swap(password[key], password[L-1-i]);
			}

			puts(password.c_str());
		}

		return ans;
	}

};