SRM566-div2-med-500

二色のペンギンで構成される輪が与えられる。
同じ色のペンギンを直線でむすび、結ぶ直線の本数の最大数を求める。
制約として、直線が交差しないという条件がある。

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



class PenguinPals{
public:
	int findMaximumMatching(string colors){
		int ans=0;
		
		for(int i=1;i<colors.size();i++){
			if(colors[i-1]==colors[i]){
				ans++;
				colors.erase(i-1,2);
				i-=2;
				if(i<0)i=0;
			}
		}
		cout<<ans<<endl;
		cout<<colors<<endl;
		while((colors[0]==colors[colors.size()-1])&&(colors.size()!=1)){
			colors.erase(0,1);
			colors.erase(colors.size()-1,1);
			cout<<colors<<endl;
			ans++;
		}
		cout<<colors<<endl;
		ans+=colors.size()/2;
		if(colors.size()/2>0){
			ans--;
		}
		return ans;
	}
};

解法

隣り合ったペンギンを結んだ時に生じる直線は、
他の直線と交差することは絶対にないので、
①まず隣り合ったペンギンを結ぶ。
②結ばれたペンギンは他に影響しないので考えないで①を続ける

これらを行ったあと残るのは
色の違うペンギンが交互に並んだ輪であるので
[残りの人数-2]/2を足せば良い

最後残らなかったりした時にハマるのでそこは適宜修正