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
事故らなければ地道に上がっていくタイプのコンテストだし、事故らなければまだまだ上がる。
