SRM 704

7ヶ月ぶりにTopCoderに出た。

300:
これはAGC005のCと全く同じ。

// I like wolves!!
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;
 
class TreeDistanceConstruction {
	public:
	int v[110];
	int e[110];
	vector <int> construct(vector <int> d) {
		int n=d.size();
		int c=0;
		for(int i=0;i<110;i++)v[i]=0;
		for(int i=0;i<n;i++)c=max(c,d[i]);
		int cnt=0;
		for(int i=0;i<n;i++)if(c==d[i])cnt++;
		if(cnt==1)return vector<int>(0);
		int D=99999999;
		for(int i=0;i<=c;i++){
			int tmp=c-min(i,c-i);
			D=min(D,tmp);
			bool ok=false;
			for(int j=0;j<n;j++){
				if(v[j])continue;
				if(d[j]==tmp){
					v[j]=1;
					ok=true;
					e[i]=j;
					break;
				}
			}
			if(!ok)return vector<int>(0);
		}
		vector<int>ret;
		for(int i=0;i<c;i++){
			ret.push_back(e[i]);
			ret.push_back(e[i+1]);
		}
		for(int i=0;i<n;i++){
			if(v[i])continue;
			if(d[i]<=D)return vector<int>(0);
			bool ok=false;
			for(int j=0;j<=c;j++){
				if(d[e[j]]+1==d[i]){
					v[i]=1;
					ret.push_back(e[j]);
					ret.push_back(i);
					ok=true;break;
				}
			}
			if(!ok)return vector<int>(0);
		}
		return ret;
	}
<%:testing-code%>};
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

500:
DDCCの予選にもあった方針。

// I like wolves!!
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;
const long long mod=1000000007;
class ModEquation {
	public:
	int dp[3000];
	long long dp2[52][3000];
	int to[2500][2500];
	long long pw(long long a,long long b){
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			b/=2;
			a=a*a%mod;
		}
		return ret;
	}
	long long gcd(long long a,long long b){
		while(a){
			b%=a;swap(a,b);
		}
		return b;
	}
	vector <int> count(int n, int K, vector <int> query) {
		vector<int>y;
		for(int i=1;i*i<=K;i++){
			if(K%i==0){
				y.push_back(i);
				if(i*i<K)y.push_back(K/i);
			}
		}
		std::sort(y.begin(),y.end());
		int sz=y.size();
		for(int i=sz-1;i>=0;i--){
			dp[i]=K/y[i];
			for(int j=i+1;j<sz;j++)if(y[j]%y[i]==0)dp[i]-=dp[j];
		}
		for(int i=0;i<52;i++)for(int j=0;j<3000;j++)
			dp2[i][j]=0;
		dp2[0][0]=1;
		for(int i=0;i<sz;i++)for(int j=0;j<sz;j++){
			long long f=gcd((long long)y[i]*y[j],K);
			to[i][j]=lower_bound(y.begin(),y.end(),(int)f)-y.begin();
		//	printf("%d %d: %d\n",i,j,to[i][j]);
		}
		
		for(int i=0;i<n;i++){
			for(int j=0;j<sz;j++){
				if(!dp2[i][j])continue;
				for(int k=0;k<sz;k++){
					dp2[i+1][to[j][k]]=(dp2[i+1][to[j][k]]+dp2[i][j]*dp[k])%mod;
				}
			}
		}
		vector<int>ret;
		for(int i=0;i<query.size();i++){
			int t=lower_bound(y.begin(),y.end(),gcd(K,query[i]))-y.begin();
			long long ks=dp2[n][t];
		//	printf("%d %lld\n",t,ks);
			ks=ks*pw(dp[t],mod-2)%mod;
			ret.push_back(ks);
		}
		return ret;
	}
<%:testing-code%>};
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

800:
実装要素がほとんどなくて見つけたら勝ちみたいな問題だった。そういうのは大概見つけられないので詰む。

Challenge:
するメリットがなかった。

270.54 + 367.54 + 0 + 0 = 638.08 (6th)
Rating: 2489 -> 2606

事故らなければ地道に上がっていくタイプのコンテストだし、事故らなければまだまだ上がる。