Kyuride Kagamiz Programming Contest(Remixed by ryunosuKe & Kensuke)
タイトルが長い
K4PC(
http://k4pc.contest.atcoder.jp/
)に参加しました,問題が割と面白かった.
開始直前にパソコンが再起動を始めてしまい5分位遅れてスタート.A~Eの5完で21位でした(5500点最下位).
A:差の和/2
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl int main(){ int n,a[100]; cin>>n; rep(i,n) cin>>a[i]; int sum=0; rep(i,n) sum+=abs(a[i]-i-1); cout<<sum/2<<endl; }
B:初め順番に仲良くなる制約を知らなくてmax-minを返した(sampleは合う).これまでで最も近いやつを探すためにsetを使えば良い
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl typedef long long ll; set<ll> c; int main(){ ll n,m; cin>>n>>m; c.insert(m); ll ans=0; rep(i,n){ ll a; cin>>a; ll mn=1e17; set<ll>::iterator it=c.lower_bound(a); if(it!=c.end()) mn=(*it-a); if(it!=c.begin()){ it--; mn=min(mn,abs(a-*it)); } ans+=mn; c.insert(a); } cout<<ans<<endl; }
C:結構変なことをしてしまった.時間反転をして、unionfind時に根との差を持たせておいてuniteする時に0を含む連結成分をuniteした時は葉をうまく見る.
普通の方法は適当にsetとかに突っ込んで頂点を消していくだけ.
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl bool is[100000]; int p[100000],w[100000],x[100000]; int d[100000]; bool isleaf[100000]; vector<int> i2g; vector<vector<int> > g2i; int n; void init(int n){ i2g.resize(n); g2i.resize(n); rep(i,n){ i2g[i]=i; g2i[i].assign(1,i); } } int mn=1e9; bool same(int ia,int ib){ return i2g[ia]==i2g[ib]; } void unite(int ia,int ib,int x){ if(g2i[i2g[ia]].size() < g2i[i2g[ib]].size()){ swap(ia,ib); x=-x; } int ga=i2g[ia],gb=i2g[ib]; bool samea=same(ia,0),sameb=same(ib,0); if(samea){ int base=d[ib]; for(auto v:g2i[gb]){ i2g[v]=ga; d[v]=d[ia]+d[v]-base+x; if(isleaf[v]) mn=min(mn,d[v]-d[0]); // } }else if(sameb){ int base=d[ib]; for(auto v:g2i[gb]){ i2g[v]=ga; d[v]=d[ia]+d[v]-base+x; } for(auto v:g2i[ga]){ if(isleaf[v]) mn=min(mn,d[v]-d[0]); } }else{ int base=d[ib]; for(auto v:g2i[gb]){ i2g[v]=ga; d[v]=d[ia]+d[v]-base+x; } } g2i[ga].insert(g2i[ga].end(),all(g2i[gb])); /* rep(i,n) cout<<i2g[i]<<" "; cout<<endl; rep(i,n) cout<<d[i]<<" "; cout<<endl<<endl;*/ } int ans[100000]; int main(){ int m; cin>>n>>m; init(n); rep(i,n) isleaf[i]=true; rep1(i,n-1){ cin>>p[i]>>w[i]; p[i]--; isleaf[p[i]]=false; } rep(i,m){ cin>>x[i]; x[i]--; is[x[i]]=true; } rep1(i,n-1){ if(!is[i]){ unite(p[i],i,w[i]); } } for(int i=m-1;i>=0;i--){ if(mn==1e9) ans[i]=-1; else ans[i]=mn; unite(p[x[i]],x[i],w[x[i]]); } // cout<<endl; rep(i,m) cout<<ans[i]<<endl; }
D:C=0の時は,O(N^2)DPがすぐに湧いて,毎回"ここより左のmax"とかが分かればいいのでsegtreeで加速させO(NlogN).C>0の時もlから始めるときC*lを加算しておく,とかするとどこから始まったかを覚えておかなくてすむ.
実はO(N)解がある.dp[R]="右端がRであるときのスコアのmax"を持って,dp[R]=max(0,dp[R-1]-C)のあと右端がRであるsegmentに対して更新すれば良い.
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl const int p2=131072; typedef long long ll; struct seg{ll l,r,f;}; ll segtree[p2*2]; void update(int x){ int p=(x-1)/2; segtree[p]=max(segtree[p*2+1],segtree[p*2+2]); if(p==0) return; update(p); } ll query(int l,int r,int a,int b,int k){ if(r<=a||b<=l) return 0; if(l<=a&&b<=r) return segtree[k]; return max(query(l,r,a,(a+b)/2,k*2+1),query(l,r,(a+b)/2,b,k*2+2)); } bool comp(const seg& l,const seg& r){ if(l.l!=r.l) return l.l<r.l; if(l.r!=r.r) return l.r<r.r; return l.f<r.f; } ll N,C; vector<seg> vc; int main(){ cin>>N>>C; rep(i,N){ int a,b,f; cin>>a>>b>>f; vc.pb(seg{a,b,f}); } sort(all(vc),comp); rep(i,N){ seg s=vc[i]; ll x=query(0,s.l+1,0,p2,0)+s.f; x=max(x,C*s.l+s.f); segtree[p2-1+s.r]=max(segtree[p2-1+s.r],x); update(p2-1+s.r); } ll ans=0; rep(i,p2){ ans=max(ans,segtree[p2-1+i]-C*i); } cout<<ans<<endl; }
E:設定が謎い.2進法表示でなんか出来ないかなあと思ったけど出来なくて,手前側で2^nを作っておき、w-pとかを足すことでパスカルの三角形の左からp+1個目までの和を足せる.nをできるだけ大きくとり、これを貪欲にやればうまくいく(貪欲時に、比が小さいため個数がそんなに少なくて済むのと、pの和も小さい(1000未満)がわかるため).x=1が罠.
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl typedef long long ll; ll x,C[70][70]; bool over[70][70]; ll s[1000]; int main(){ cin>>x; if(x==1){ puts("1 1"); puts("100"); return 0; } ll p=1; int n=0; while(p<=x){ p*=2; n++; } p/=2; n--; rep(i,70){ C[i][0]=1,C[i][i]=1; for(int j=1;j<i;j++){ if(over[i-1][j-1]||over[i-1][j]){ over[i][j]=true; continue; } C[i][j]=C[i-1][j-1]+C[i-1][j]; if(C[i][j]>1000000000000000000){ over[i][j]=true; C[i][j]=0; } } } int k; for(int i=0;!over[n][i]&&(i==0||s[i-1]<x)&&i<=n/2;i++){ s[i]=C[n][i]; if(i!=0) s[i]+=s[i-1]; k=i; } vector<int> ans; int w=1000; x-=p; rep(i,n) ans.pb(1); while(x>0){ for(int i=k;i>=0;i--) if(s[i]<=x){ x-=s[i]; ans.pb(w-i); break; } } cout<<ans.size()<<" "<<w<<endl; rep(i,ans.size()) cout<<ans[i]<<endl; }
F:コンテスト中残り4分とかで2点取ろうと思ったけど無理でした.
牛ゲー(答え).s[x]=-infからxまでの点の個数,とすると牛ゲーになる.点として現れる場所は少ないので(1000*6くらい)間に合う.要らん空白を入れて3時間位debugしていた・・・.
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl typedef long long ll; struct edge{ll from,to,cost;}; int N; ll x[1000],k[1000],d[1000],inf=1e16; ll dist[10000]; int ans[10000]; vector<ll> ash,xs; vector<edge> es; ll id(ll x){ return lower_bound(all(ash),x)-ash.begin(); } void add_edge(ll x,ll y,ll cost){ //x-y>=cost es.pb(edge{id(y),id(x),-cost}); // show(id(x)); // show(id(y)); // show(cost); // cout<<endl; } vector<int> ret; int main(){ cin>>N; rep(i,N) cin>>x[i]>>k[i]>>d[i]; rep(i,N){ ash.pb(x[i]); ash.pb(x[i]-1); ash.pb(x[i]+d[i]-1); ash.pb(x[i]-d[i]); ash.pb(x[i]+d[i]); ash.pb(x[i]-d[i]-1); } ash.pb(-inf); ash.pb(inf); sort(all(ash)); ash.erase(unique(all(ash)),ash.end()); // rep(i,ash.size()) show(ash[i]); // cout<<endl; rep(i,N) xs.pb(x[i]); sort(all(xs)); xs.erase(unique(all(xs)),xs.end()); rep(i,xs.size()){ add_edge(xs[i],xs[i]-1,count(x,x+N,xs[i])); } rep(i,N){ add_edge(x[i]+d[i],x[i]-d[i]-1,k[i]); add_edge(x[i]-d[i],x[i]+d[i]-1,1-k[i]); } rep(i,ash.size()-1) add_edge(ash[i+1],ash[i],0); rep(i,ash.size()) dist[i]=inf; dist[id(-inf)]=0; bool update; rep(i,ash.size()+2){ update=false; for(auto e:es){ if(dist[e.from]!=inf&&dist[e.from]+e.cost<dist[e.to]){ dist[e.to]=dist[e.from]+e.cost; update=true; } } if(!update) break; } if(update){ puts("impossible"); }else{ ll num=-dist[id(inf)]-N; // show(num); if(num<=100000){ cout<<num<<endl; rep(i,N) ans[id(x[i])]--; rep1(i,ash.size()-1){ ans[i]+=dist[i-1]-dist[i]; rep(j,ans[i]) ret.pb(ash[i]); } rep(i,num){ printf("%d%c",ret[i],i==num-1?'\n':' '); } }else{ puts("too many"); } } }
G:シラネ.解説が上がったら解こう.
追記:上がってないけど解いた.条件が,X_i=C+a*iなる形で表せることと同値なのはまあ自明.
傾きがa(-2e9~2e9の整数)の直線の中で,場所iではa[i]以上b[i]以下を通るようなやつを数え上げれば良い.傾きがaの時,どの条件が一番つらいかを考えると,凸包が浮かび上がる.あとはどの点が一番つらいか切り替わるところで切り替えれば良い.一番つらい点が上,下ともに決まっていれば,一次式の区間の和になるのでO(1)で計算できる.
ただ負にならないように(傾きの)区間の端っこを区切る必要がある.
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl typedef long long ll; typedef pair<ll,ll> P; P operator +(P a,P b){ return P(a.fs+b.fs,a.sc+b.sc); } P operator -(P a,P b){ return P(a.fs-b.fs,a.sc-b.sc); } typedef vector<P> Pol; inline ll cro(P a, P b) { return a.fs*b.sc-a.sc*b.fs;}; inline int ccw (P a, P b, P c){ if(cro(b-a,c-a)>0) return 1; if(cro(b-a,c-a)<0) return -1; return 0; } inline Pol convu(Pol p){ //convex int n=p.size(),k=0; Pol ret(n); rep(i,n){ while(k>=2 && ccw(ret[k-2],ret[k-1],p[i])>=0 ) --k; ret[k++]=p[i]; } ret.resize(k); return ret; } inline Pol convd(Pol p){ //convex int n=p.size(),k=0; Pol ret(n); rep(i,n){ while(k>=2 && ccw(ret[k-2],ret[k-1],p[i])<=0) --k; ret[k++]=p[i]; } ret.resize(k); return ret; } int N; Pol as,bs; vector<P> vc; ll mod=1e9+7; ll up(ll x,ll y){ if(x>0) return (x-1)/y+1; return -(-x)/y; } int main(){ cin>>N; rep(i,N){ int a; cin>>a; as.pb(P(i,a)); } rep(i,N){ int a; cin>>a; bs.pb(P(i,a)); } Pol us=convd(bs),ds=convu(as); int a=us.size(),b=ds.size(); // rep(i,a) show(us[i]); // rep(i,b) show(ds[i]); rep(i,a-1){ P x=us[i+1]-us[i]; ll t=up(x.sc,x.fs); vc.pb(P(t,i+1)); } rep(i,b-1){ P x=ds[i+1]-ds[i]; ll t=up(x.sc,x.fs); vc.pb(P(t,a+i)); } vc.pb(P(2e9+1,0)); ll x=0,y=b-1,t=-2e9,ans=0; sort(all(vc)); rep(i,vc.size()){ // show(vc[i].fs); // show(vc[i].sc); ll nt=vc[i].fs; ll p=ds[y].fs,q=ds[y].sc,r=us[x].fs,s=us[x].sc; ll L=t,R=nt-1; if(p==r){ if(s<q) L=nt; }else if(p>r){ L=max(L,up(q-s,p-r)); }else{ R=min(R,-up(q-s,r-p)); } // show(x); // show(y); if(L<=R){ // printf("tan=[%lld,%lld]\n",L,R); // printf("%lld+%lld*tan+1\n",s-q,p-r); ll pl=(R-L+1)*(s-q)+(R-L+1)*(R+L)/2*(p-r)+(R-L+1); // show(pl); ans+=pl; } t=nt; if(vc[i].sc>=a) y=min(y,vc[i].sc-a); else x=max(x,vc[i].sc); } cout<<ans%mod<<endl; }
