CodeChef-LUCKYSWP : Little Elephant and Swapping

問題概要

4,7からなる文字列S(|S|<10^5)が与えられる。文字列Sから部分文字列を抜き出してその後適当な箇所に挿入した文字列をTとする。F(T)を、Tの部分列で44..44 or 77..77 or 444..477..77の形をしている最長の長さとする。max F(T)を求める問題。

解法

置換はとりあえず無視して、各iに対してF(S[0:i])を求めておく。また、F(S[i:$])も求めておく。これにより4と7の切り替わる位置を全探索することができる。位置iで切ったときの最大値はF(S[0:i])+F(S[i:$])になるからである。

acceptされたコード

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = (int)(1e5);

int L;
int accum4[MAX_N + 1];
int accum7_rev[MAX_N + 1];
int opt[MAX_N + 1], opt_rev[MAX_N + 1];
char buf[MAX_N + 1];

void init(){
	scanf(" %s ", buf);
	L = strlen(buf);
	if(buf[L-1] != '4' && buf[L-1] != '7'){
		buf[L-1] = '\0';
		--L;
	}
}

int solve(){
	for(int i=0; i<L; ++i){
		accum4[i+1] = accum4[i] + (buf[i] == '4' ? 1 : 0);
	}
	for(int i=0; i<L; ++i){
		accum7_rev[i+1] = accum7_rev[i] + (buf[L-1-i] == '7' ? 1 : 0);
	}

	for(int i=0; i<L; ++i){
		opt[i+1] = max(opt[i],  2*accum4[i+1] - (i+1));
	}
	for(int i=0; i<L; ++i){
		opt[i+1] += (i+1) - accum4[i+1];
	}

	for(int i=0; i<L; ++i){
		opt_rev[i+1] = max(opt_rev[i], 2*accum7_rev[i+1] - (i+1));
	}
	for(int i=0; i<L; ++i){
		opt_rev[i+1] += (i+1) - accum7_rev[i+1];
	}

	int ans = opt[L];
	for(int i=0; i<L; ++i){
		ans = max(ans, opt[i] + opt_rev[L-i]);
	}
	return ans;
}

int main(){
	int T;
	scanf("%d ", &T);
	for(int _=0; _<T; ++_){
		init();
		printf("%d\n", solve());
	}

	return 0;
}