TopCoder SRM433 DIV1 黄色昇格！

またしても二色コーディング(C++とJava)。

今回45位だってさ！自分すごい！

Rating 1489 => 1772 やったね！黄色昇格！

	max		Class.method		point		status
	250		MagicWords.count		148.73		Passed System Test
	500		SettingTests.countSites		288.61		Passed System Test
	1000		BarbarianInvasion.minimalDetachment		0		Opened

sum: 437.34

僕は僕らしく、堅実にコーディングすればいいってことですね。

//TopCoder SRM433 DIV1 250
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

class MagicWords
{
private:
	bool check_cycle(const string& str, int c)
	{
		if(str.size() % c != 0)return false;
		int divc = str.size() / c;
		for(int i=0;i<divc;i++) {
			char chr = str[i];
			for(int j=1;j<c;j++) {
				if(chr != str[i+divc*j]) {
					return false;
				}
			}
		}
		return true;
	}
public:
	int count(vector<string> S, int K)
	{
		int L=0;
		for(int i=0;i<S.size();i++)L+=S[i].size();
		vector<int> divisors;
		for(int i=K+1;i<=L;i++) {
			if(L%i==0)divisors.push_back(i);
		}
		vector<int> p(S.size());
		for(int i=0;i<p.size();i++)p[i]=i;
		int cnt = 0;
		do {
			string s;
			for(int i=0;i<p.size();i++)s+=S[p[i]];
			if(!check_cycle(s,K))continue;
			bool flag = true;
			for(int i=0;i<divisors.size();i++) {
				if(check_cycle(s,divisors[i])){flag=false;break;}
			}
			if(flag) {
				cnt++;
			}
		} while(next_permutation(p.begin(), p.end()));
		return cnt;
	}
};

//TopCoder SRM433 DIV1 500
public class SettingTents {
	private int gcm(int a, int b) {
		if(a<0)a=-a;
		if(b<0)b=-b;
		while(b>0) {
			int t=a%b;
			a=b;
			b=t;
		}
		return a;
	}
	public int countSites(int N, int M) {
		int min_width = Math.min(N,M);
		int max_width = Math.max(N,M);
		int count = 0;
		for(int i=1;i<=min_width;i++) {
			if(i%2==0) {
				for(int j=0;j<i;j++) {
					if(gcm(i/2,j)!=1)continue;
					for(int ta=1;;ta++) {
						int aw=i*ta;
						int ah=Math.abs(i-2*j)*ta;
						if(aw>N || ah>M)break;
						for(int tb=1;;tb++) {
							int bh=i*tb;
							int bw=Math.abs(i-2*j)*tb;
							if(bw>N || bh>M)break;
							count += (N-Math.max(aw,bw)+1)*(M-Math.max(ah,bh)+1);
						}
					}
				}
			} else {
				for(int j=0;j<i;j++) {
					if(gcm(i,j)!=1)continue;
					for(int ta=1;;ta+=2) {
						int aw=i*ta;
						int ah=Math.abs(i-2*j)*ta;
						if(aw>N || ah>M)break;
						for(int tb=1;;tb+=2) {
							int bh=i*tb;
							int bw=Math.abs(i-2*j)*tb;
							if(bw>N || bh>M)break;
							count += (N-Math.max(aw,bw)+1)*(M-Math.max(ah,bh)+1);
						}
					}
				}
			}
		}
		return count;
	}
}