2014-06-28
■ ARC #026 && 101 Hack June'14
成し遂げたぜ。
ARC #026
A: 一種のGreedy
B: やるだけ (10^10 = (5*10^9)^2とかいうひどい勘違いをしていた)
C: segtreeした
D: 時給きめうち-> MST (ただしコストが負の辺は無条件で追加)
こういう問題は昔から好きなのでラッキーでした。
#include#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; typedef long long ll; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) int par[10005]; int ran[10005]; void init() { for(int i=0;i<10005;i++) par[i]=i,ran[i]=0; } int find(int x) { if(par[x] == x) return x; else return par[x]=find(par[x]); } void unite(int x,int y) { x=find(x); y=find(y); if(x == y) return ; if(ran[x]<ran[y]) par[x]=par[y]; else { par[y]=par[x]; if(ran[x] == ran[y]) ran[x]++; } } bool same(int x,int y) { return find(x)==find(y); } vector<pair<pair<double,double>,P> > gen; int main() { int n,m; cin >> n >> m; for(int i=0;i<m;i++) { int a,b; double c,t; scanf("%d %d %lf %lf",&a,&b,&c,&t); gen.pb(mp(mp(c,t),mp(a,b))); } double lb = 0.0; double ub = 1145140.0; double mid; for(int i=0;i<114;i++) { mid = (lb+ub)/2; vector<pair<double,P> > vec; for(int j=0;j<m;j++) { double ne = gen[j].fi.fi - gen[j].fi.sc*mid; vec.pb(mp(ne,gen[j].sc)); } sort(vec.begin(),vec.end()); init(); double sum = 0.0; for(int i=0;i<vec.size();i++) { if(vec[i].fi <= 0.0) { sum += vec[i].fi; unite(vec[i].sc.fi,vec[i].sc.sc); } else if(!same(vec[i].sc.fi,vec[i].sc.sc)) { sum += vec[i].fi; unite(vec[i].sc.fi,vec[i].sc.sc); } } if(sum <= 0.0) ub = mid; else lb = mid; } printf("%.15f\n",mid); }
2位(過去最高順位)でした。やったね
101 Hack June'14
A: GCDをとる
B: まとめると調和級数で処理できる
C: bitごとにsegtreeをつくるテク
D: sa+lcpして適当ににぶたんする
#include#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; typedef long long ll; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define mod 1000000007 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define SIZE (1<<17) int ran[100005]; int n,k; int tmp[100005]; int sa[100005]; int lcp[100005]; void construct_lcp(string S) { for(int i=0;i<=n;i++) ran[sa[i]] = i; int h = 0; lcp[0] = 0; for(int i=0;i<n;i++) { int j = sa[ran[i]-1]; if(h) h--; for(;j+h if(S[j+h] != S[i+h]) break; } lcp[ran[i]-1] = h; } } bool compare_sa(int i,int j) { if(ran[i] != ran[j]) return ran[i] < ran[j]; else { int ri = i+k<=n ? ran[i+k]: -1; int rj = j+k<=n ? ran[j+k]: -1; return ri < rj; } } void construct_sa(string S) { for(int i=0;i<=n;i++) { sa[i] = i; ran[i] = i<n?S[i]:-1; } for(k=1;k<=n;k*=2) { sort(sa,sa+n+1,compare_sa); tmp[sa[0]] = 0; for(int i=1;i<=n;i++) { tmp[sa[i]] = tmp[sa[i-1]] + compare_sa(sa[i-1],sa[i]); } for(int i=0;i<=n;i++) { ran[i] = tmp[i]; } } } string s; int t; int main() { cin >> t; for(int i=0;i<t;i++) { cin >> s; n = s.size(); construct_sa(s); construct_lcp(s); ll ind; cin >> ind; ll prev = 0; for(int j=0;j<=n;j++) { ll len = (ll)(n-sa[j]); ll rem = (ll)(j?lcp[j-1]:0); ll cur = prev + (len*(len+1)/2-rem*(rem+1)/2); if(cur < ind) { prev = cur; continue; } ll lb = (rem+1); ll ub = len; ll target = ind-prev; //[lb,ub] while(ub-lb > 0) { ll mid = (lb+ub)/2; if((mid+(rem+1))*(mid-(rem+1)+1)/2 < target) lb = mid+1; else ub = mid; } //solution exists in lb target -= ((lb-1)+(rem+1))*((lb-1)-(rem+1)+1)/2; printf("%c\n",s[sa[j]+target-1]); break; } } }
E: 適当に組んだら2点ちょっともらえた
9位。まさかT-shirtもらえるとは思ってなかった...
