JOI 春合宿 2010 Day 3
何日か前にやったのに書くの忘れてた
本選会場
うまいこと待ってやれば、最小全域木のコスト分しかかからない。K個まで分割することが許されるので、全域木に含まれる辺からコストの大きい順にK-1個とって木をK個に分割してやればいい。
int N,M,K; struct edge { int from,to,cost; edge(int from,int to,int cost):from(from),to(to),cost(cost){} bool operator < (const edge& a) const { return cost < a.cost; } }; struct UnionFind { int par[100100],rank[100100]; void init(){rep(i,100100)par[i]=i;} int find(int x) { if(par[x]==x)return x; return par[x]=find(par[x]); } void unite(int a,int b) { a = find(a); b = find(b); if(a==b)return; if(rank[a]<rank[b])par[a]=b; else { par[b]=a; if(rank[a]==rank[b])rank[a]++; } } bool same(int a,int b) { return find(a)==find(b); } }uf; vector<edge> es; int main() { scanf("%d %d %d",&N,&M,&K); rep(i,M) { int a,b,c; scanf("%d %d %d",&a,&b,&c); es.pb(edge(a,b,c)); } sort(all(es)); uf.init(); int cnt = 0,ans = 0; rep(i,es.size()) { if(cnt==N-K)break; if(uf.same(es[i].from,es[i].to))continue; uf.unite(es[i].from,es[i].to); cnt++; ans += es[i].cost; } printf("%d\n",ans); return 0; }
かくれんぼ
よくある感じのsegtreeで平面走査。
すんなり書けた。
前に一度解いたことがあるらしいけど、全然覚えてなかったので初見と同じ感覚で解いた。
前解いたときは何日もつかった気がするけど今回はサクッと解けたのでなんとなく成長を感じた(?)
const int SIZE = 1<<17; struct segtree { int seg[SIZE*2],lazy[SIZE*2]; void lazy_evaluate(int k) { seg[k]+=lazy[k]; if(k<SIZE-1) { lazy[2*k+1]+=lazy[k]; lazy[2*k+2]+=lazy[k]; } lazy[k]=0; } void update(int a,int b,int k,int l,int r,int x) { lazy_evaluate(k); if(r<=a||b<=l)return; if(a<=l&&r<=b) { lazy[k]+=x; lazy_evaluate(k); } else { update(a,b,k*2+1,l,(l+r)/2,x); update(a,b,k*2+2,(l+r)/2,r,x); seg[k] = max(seg[k*2+1],seg[k*2+2]); return; } } int query(int a,int b,int k,int l,int r) { lazy_evaluate(k); if(r<=a||b<=l)return 0; if(a<=l&&r<=b)return seg[k]; else { int lch = query(a,b,k*2+1,l,(l+r)/2); int rch = query(a,b,k*2+2,(l+r)/2,r); seg[k] = max(seg[k*2+1],seg[k*2+2]); return max(lch,rch); } } int value(int v){return seg[v]+lazy[v];} int get_index(int x) { int p=0; while(p<SIZE-1) { lazy_evaluate(p); if(value(2*p+1)>=x)p = p*2+1; else p = p*2+2; } return p-(SIZE-1); } }seg; int N,M; struct obstacle { int x,y,w; obstacle(int x,int y,int w):x(x),y(y),w(w){} bool operator < (const obstacle a) const { if(y!=a.y)return y < a.y; return x < a.x; } }; int a[100100],ans_x[100100],ans_y[100100]; vector<int> weapon; vector<obstacle> obs; int main() { scanf("%d %d",&N,&M); rep(i,N) { int x,y,w; scanf("%d %d %d",&x,&y,&w); obs.pb(obstacle(x,y,w)); } sort(all(obs)); rep(i,M) { scanf("%d",&a[i]); weapon.pb(a[i]); } sort(all(weapon)); weapon.erase(unique(all(weapon)),weapon.end()); memset(ans_x,-1,sizeof(ans_x)); memset(ans_y,-1,sizeof(ans_y)); int id = 0; rep(i,obs.size()) { seg.update(obs[i].x,obs[i].x+obs[i].w,0,0,SIZE,1); int max_val = seg.query(0,SIZE,0,0,SIZE); while(id<M&&weapon[id]<max_val) { ans_y[id] = obs[i].y; ans_x[id] = seg.get_index(weapon[id]+1); id++; } } rep(i,M) { int k = lower_bound(all(weapon),a[i])-weapon.begin(); printf("%d %d\n",ans_x[k],ans_y[k]); } return 0; }
シムロード
実は始めてのOutput onlyだった。
シュタイナー木やんこれ、ってなって適当にdijkstraで貪欲チックにやったら96.3点も帰ってきて
驚愕。snukeさんどうやって解いてるんだろう…
string s[105]; int d[105][105]; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int W,H; P village[10010]; P prev[10010]; int sx,sy; void dijkstra() { rep(i,H)rep(j,W)d[i][j]=INF; rep(i,H)rep(j,W)prev[i*W+j]=P(-1,-1); d[sx][sy]=0; priority_queue<T,vector<T>,greater<T> > q; q.push(T(0,P(sx,sy))); while(!q.empty()) { T a = q.top(); q.pop(); rep(i,4) { int nx=a.sec.fi+dx[i],ny=a.sec.sec+dy[i]; if(nx<0||nx>=H||ny<0||ny>=W)continue; int ne = a.fi; if(s[nx][ny]=='w')ne++; if(d[nx][ny]>ne) { d[nx][ny]=ne; prev[nx*W+ny]=a.sec; q.push(T(ne,P(nx,ny))); } } } } void cut(int v) { P cur = village[v]; while(1) { cur = prev[cur.fi*W+cur.sec]; if(cur==village[0])break; if(s[cur.fi][cur.sec]=='w')s[cur.fi][cur.sec]='.'; } return; } int main() { scanf("%d %d",&W,&H); rep(i,H)cin >> s[i]; int num = 0; rep(i,H)rep(j,W)if(s[i][j]=='@')village[num++]=P(i,j); sx = village[0].fi,sy = village[0].sec; while(1) { dijkstra(); int mv,mn=INF; rep(i,num) { if(d[village[i].fi][village[i].sec]<=0)continue; if(mn>d[village[i].fi][village[i].sec]) { mn = d[village[i].fi][village[i].sec]; mv = i; } } if(mn==INF)break; cut(mv); } rep(i,H)cout << s[i] << endl; return 0; }
100+100+96.3 = 296.3
全完出来なくて悲しいけどわりと嬉しい点数だった
JOI 春合宿 2008 Day 3 Origami
問題文はちゃんと読みましょう
Origami,簡単だけど5ではないでしょ…
— おくら (@okuraofvegetabl) 2015, 2月 22ええええええええええ辺の長さ20cm以下とか聞いてないぞおおおおお
— おくら (@okuraofvegetabl) 2015, 2月 22mapで数えるだけの問題を2次元座圧+2次元imosでやりました。
普通にやったらMLEするので、平面走査風にやってメモリ節約しました。
int imos[10050],cnt[10050]; int a,b,n; int p[5050],q[5050],r[5050],s[5050]; vector<int> vx,vy; vector<T> event; ll size(int x,int y) { if(x+1>=(int)vx.size()||y+1>=(int)vy.size())return 0ll; return (ll)(vx[x+1]-vx[x])*(ll)(vy[y+1]-vy[y]); } int main() { scanf("%d",&n); scanf("%d %d",&a,&b); for(int i=0;i<n;i++) { scanf("%d %d %d %d",&p[i],&q[i],&r[i],&s[i]); p[i]--;q[i]--; vx.pb(p[i]);vy.pb(q[i]);vx.pb(r[i]);vy.pb(s[i]); } sort(all(vx)); sort(all(vy)); vx.erase(unique(all(vx)),vx.end()); vy.erase(unique(all(vy)),vy.end()); for(int i=0;i<n;i++) { p[i]=lower_bound(all(vx),p[i])-vx.begin(); q[i]=lower_bound(all(vy),q[i])-vy.begin(); r[i]=lower_bound(all(vx),r[i])-vx.begin(); s[i]=lower_bound(all(vy),s[i])-vy.begin(); //printf("%d %d %d %d\n",p[i],q[i],r[i],s[i]); event.pb(T(P(p[i],q[i]),1)); event.pb(T(P(p[i],s[i]),-1)); event.pb(T(P(r[i],q[i]),-1)); event.pb(T(P(r[i],s[i]),1)); } sort(all(event)); int SX = vx.size(),SY = vy.size(); int id = 0; int ans_sz = 0; ll ans_num = 0ll; for(int i=0;i<=SX;i++) { if(!(id<event.size()))break; if(event[id].fi.fi!=i)continue; memset(cnt,0,sizeof(cnt)); while(id<event.size()&&event[id].fi.fi==i) { cnt[event[id].fi.sec]+=event[id].sec; id++; } for(int j=0;j<=SY;j++)cnt[j+1]+=cnt[j]; for(int j=0;j<=SY;j++) { imos[j]+=cnt[j]; if(ans_sz<imos[j]) { ans_sz = imos[j]; ans_num = size(i,j); } else if(ans_sz==imos[j]) { ans_num += size(i,j); } } } printf("%d\n",ans_sz); printf("%lld\n",ans_num); return 0; }
JOI 春合宿 2010 Day 2
はい、2日目。
足し算
繰り上がりがあって、和が10を超えない時
繰り上がりがあって、和が10を超える時
繰り上がりがなくて、和が10を超えない時
繰り上がりがなくて、和が10を超える時
に場合分けしてやった。
最後に残った繰り上がりの1を忘れていてWAをはいて、
それを治したらWAで80点になった。
そこから色々ミス探したけど見つからず。
終了後に実際のテストケースで試したらセグフォしたので、配列の大きさが足りてないだけだとわかった。ほんまにキレそう。腹たつ。こんなミスした自分に腹立つ。
int m,M; int a[20100],A[20100]; ll l[20100],L[20100]; int dig[80100]; ll num[80100]; int main() { scanf("%d",&m); rep(i,m)scanf("%d %lld",&a[i],&l[i]); scanf("%d",&M); rep(i,M)scanf("%d %lld",&A[i],&L[i]); reverse(l,l+m); reverse(a,a+m); reverse(A,A+M); reverse(L,L+M); l[m]=INF; L[M]=INF; int cnt1=0,cnt2=0,k=0,ans_id=0; while(cnt1<m||cnt2<M) { int p = min(l[cnt1],L[cnt2]); if(k&&a[cnt1]+A[cnt2]+k<10) { dig[ans_id]=a[cnt1]+A[cnt2]+k; num[ans_id++]=1; l[cnt1]--; L[cnt2]--; if(l[cnt1]==0)cnt1++; if(L[cnt2]==0)cnt2++; k=0; } else if(k&&a[cnt1]+A[cnt2]+k>=10) { dig[ans_id]=(a[cnt1]+A[cnt2]+k)%10; num[ans_id++]=min(l[cnt1],L[cnt2]); l[cnt1]-=p; L[cnt2]-=p; if(l[cnt1]==0)cnt1++; if(L[cnt2]==0)cnt2++; k=1; } else if(a[cnt1]+A[cnt2]<10) { dig[ans_id]=a[cnt1]+A[cnt2]; num[ans_id++]=min(l[cnt1],L[cnt2]); l[cnt1]-=p; L[cnt2]-=p; if(l[cnt1]==0)cnt1++; if(L[cnt2]==0)cnt2++; } else { dig[ans_id]=(a[cnt1]+A[cnt2])%10; num[ans_id++]=1; dig[ans_id]=(a[cnt1]+A[cnt2]+1)%10; num[ans_id++]=p-1; l[cnt1]-=p; L[cnt2]-=p; if(l[cnt1]==0)cnt1++; if(L[cnt2]==0)cnt2++; k=1; } } if(k) { dig[ans_id]=1; num[ans_id++]=1; } vector<P> ans; rep(i,ans_id) { if(num[i]==0)continue; if(!ans.empty()&&dig[i]==ans.back().fi)ans[(int)ans.size()-1].sec+=num[i]; else ans.pb(P(dig[i],num[i])); } while(!ans.empty()&&ans.back().fi==0)ans.pop_back(); reverse(all(ans)); printf("%d\n",(int)ans.size()); rep(i,ans.size())printf("%d %lld\n",ans[i].fi,ans[i].sec); return 0; }
DNAの合成
普通にDP。文字列が一致してるかどうかの判定はロリハでする。
毎回ハッシュ求めてたら遅いので順番に求めてやる。
定数20は重い。
const ull B = 1000000007ull; ull hash(string s,int a,int b) { ull res = 0ull; for(int i=a;i<a+b;i++) { res *= B; res += s[i]-'A'+4; } return res; } int dp[150100]; int N; vector<ull> dna; string target; ull BB[30]; int main() { BB[0]=1ll; for(int i=1;i<30;i++)BB[i]=BB[i-1]*B; scanf("%d",&N); cin >> target; rep(i,N) { string s; cin >> s; dna.pb(hash(s,0,(int)s.size())); } SORT(dna); dp[0]=0; for(int i=1;i<=(int)target.size();i++)dp[i]=INF; ull h=0ull; for(int i=1;i<=(int)target.size();i++) { h*=B; h+=target[i-1]-'A'+4; if(binary_search(all(dna),h))dp[i]=1; } for(int i=2;i<=(int)target.size();i++) { int t = INF; h = target[i-1]-'A'+4; for(int j=2;j<=20;j++) { if(i-j<0)break; h += BB[j-1]*(target[i-j]-'A'+4); t = min(t,dp[i-j+1]); if(binary_search(all(dna),h))dp[i]=min(dp[i],t+1); } } printf("%d\n",dp[(int)target.size()]); return 0; }
地域
木の直径って書いてあったので、木DPかな?と思ったけどNが結構でかいので違うなぁと踏む。
最大値の最小値だしどうせにぶたんでしょ、と思って判定を考えた。
葉から順に直径がX以下になるように切っていって、最終的に切った回数がM未満ならOKだと考えて、嘘臭いなぁと思いつつとりあえず書いて投げたら通ってしまった。(解法が正しいことはあとで解説読んで確認するつもりです)
int N,M; struct edge { int to,cost; edge(int to,int cost):to(to),cost(cost){} }; vector<edge> g[30100]; int X,divide; int dfs(int v,int p) { vector<int> vec; for(int i=0;i<g[v].size();i++) { edge e = g[v][i]; if(e.to==p)continue; int f = dfs(e.to,v)+e.cost; if(f<=X)vec.pb(f); else divide++; } if(vec.empty())return 0; sort(all(vec),greater<int>()); int i; for(i=0;i<(int)vec.size()-1;i++) { if(vec[i]+vec[i+1]>X)divide++; else break; } if(i==(int)vec.size()-1)return vec[(int)vec.size()-1]; return vec[i]; } int main() { scanf("%d %d",&N,&M); for(int i=0;i<N-1;i++) { int a,b,c; scanf("%d %d %d",&a,&b,&c); a--;b--; g[a].pb(edge(b,c)); g[b].pb(edge(a,c)); } int l=-1,r=INF; while(r-l>1) { int mid = (l+r)/2; X = mid; divide = 0; dfs(0,-1); if(divide>=M)l=mid; else r = mid; } printf("%d\n",r); return 0; }
80+100+100 = 280
こんなミスで満点取れなかったの悔しすぎる。
本番だったら20点で代表になれるかどうか左右されるのにこんなんじゃまずいのでもっと問題解きまくります。
期末が近づいてきてるらしいけどしらん。
ここまで 580/600
頑張ろう。
JOI 春合宿 2010 Day 1
5時間ちゃんと時間測ってやってみた。
JOI ポスター
なんか昔解いた気がするけどまぁやるだけ。
適当に再帰で書きました。
時間かけすぎた気がする。
string rec(int N,int K) { string ret; if(!N)return "J"; if(K>=(1<<(N-1))) { rep(i,1<<(N-1))ret+='I'; return ret+rec(N-1,K-(1<<(N-1))); } else { rep(i,(1<<(N-1)))ret+='J'; rep(i,(1<<(N-1)))ret+='O'; return ret; } } int main() { int N,K; scanf("%d %d",&N,&K); cout << rec(N,K-1) << endl; return 0; }
戦国時代
各武将は角の動ける範囲を守れる。
↗方向と↘方向に分けて考える。
それぞれ(x,y)->(x+y,x-y)みたいな変換をしてやると数えられる。
後は重複を引く。重複は各↗方向に対して、かぶりうる↘の範囲を求めて、にぶたんする。
この時偶奇にわけないといけないことに注意。
LとN間違えてて、デバッグでハマった。
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <complex> #include <string> #include <sstream> #include <algorithm> #include <numeric> #include <vector> #include <queue> #include <stack> #include <functional> #include <iostream> #include <map> #include <set> using namespace std; typedef pair<int,int> P; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; #define pu push #define pb push_back #define mp make_pair #define eps 1e-9 #define INF 2000000000 #define sz(x) ((int)(x).size()) #define fi first #define sec second #define SORT(x) sort((x).begin(),(x).end()) #define all(x) (x).begin(),(x).end() #define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++) #define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++) #define EQ(a,b) (abs((a)-(b))<eps) int L,N; ll ans = 0ll; vector<int> xy,yx; vector<int> odd,even; int x[100100],y[100100]; int main() { scanf("%d %d",&L,&N); rep(i,N)scanf("%d %d",&x[i],&y[i]); rep(i,N) { xy.pb(x[i]+y[i]); yx.pb(y[i]-x[i]); if((y[i]-x[i])%2)odd.pb(y[i]-x[i]); else even.pb(y[i]-x[i]); } sort(all(xy)); sort(all(yx)); sort(all(odd)); sort(all(even)); xy.erase(unique(all(xy)),xy.end()); yx.erase(unique(all(yx)),yx.end()); odd.erase(unique(all(odd)),odd.end()); even.erase(unique(all(even)),even.end()); rep(i,xy.size())ans += L-abs(xy[i]-(L-1)); rep(i,yx.size())ans += L-abs(yx[i]); rep(i,xy.size()) { int beg,end,k; end = (xy[i]>L-1)?2*L-2-xy[i]:xy[i]; beg = -end; if(xy[i]%2)k = upper_bound(all(odd),end)-lower_bound(all(odd),beg); else k = upper_bound(all(even),end)-lower_bound(all(even),beg); ans -= k; } printf("%lld\n",ans); return 0; }
階段
なんの変哲もない普通のDP。segtreeで加速してやるだけ。
#define MOD 1234567 const int SIZE = 1<<19; struct segtree { int seg[SIZE*2]; void update(int k,int x) { k += SIZE-1; seg[k]=x; while(k) { k = (k-1)/2; seg[k]=(seg[k*2+1]+seg[k*2+2])%MOD; } } int query(int a,int b,int k,int l,int r) { if(r<=a||b<=l)return 0; if(a<=l&&r<=b)return seg[k]; return (query(a,b,k*2+1,l,(l+r)/2)+query(a,b,k*2+2,(l+r)/2,r))%MOD; } }seg; int dp[500100]; int h[500100]; int N,P; int main() { scanf("%d %d",&N,&P); for(int i=1;i<=N;i++)scanf("%d",&h[i]); rep(i,N+1)h[i+1]+=h[i]; dp[0]=1; seg.update(0,1); for(int i=1;i<=N;i++) { int k = lower_bound(h,h+N+1,h[i]-P)-h; if(k<i)dp[i]=seg.query(k,i,0,0,SIZE); seg.update(i,dp[i]); } printf("%d\n",dp[N]); return 0; }
100+100+100=300 (2:03)
終わってからDEGwerさんにこの日はクソ簡単な日だと教えていただいた。
実際簡単でほぼ3時間余らせて全完できたので良かった
JOI 2015 本選参加記
昨日までJOIの本選に参加していました。
結果からいうと一応通過しました。
去年こんな感じで(JOI 2014 本選 - (#・∀・))
この時の悔しさを噛み締めながら一年やって来たので、通過できたことは素直に喜びたいと思います。
2/7
potetiと一緒に新神戸から新幹線に乗って,akouryy,eyさんと新大阪で合流。
僕の友達は小さいを解いた。添字でハマってかなり時間食った。
その他色々問題見かえしたりした。
参宮橋についてから、昼飯を食べていなかったのでpotetiとMTKに入った。
注文したあとによくよく考えるとプラクティス開始まで30分しかないことに気づく。
爆速で食べ終えて走ってオリセンへ。
3時58分に会場に入る(クズ)
プラクティスはサクっと全完して師匠やHIRさん、yokozuna氏たちとお話する。
その後の講演会は全く聞かずにPKUの問題考えてた。
その後、食事会。
自己紹介で言う事なかったので予選満点じゃなくて反省してるって言った気がする。
去年同様、筑駒の部誌もらったりsnukeさんやwoさん,hogloidさんなどチューターの方とお話したりした。
風呂でpotetiが汚い話をしていた気がする。
その後師匠とnamonaki氏とravenさんと一緒にpotetiの部屋に言って色々した。
11時45分頃に就寝。
2/8
6時20分に起床して着替えて飯を食って荷物片付けて鍵返して控え室でしばらく待って、会場の席に着いた。
競技開始。
1
imosやるだけ。15分くらいでAC.
#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int N,M; int P[100100]; ll A[100100],B[100100],C[100100]; ll imos[100100]; int main() { scanf("%d %d",&N,&M); for(int i=0;i<M;i++)scanf("%d",&P[i]); for(int i=0;i<M;i++)P[i]--; for(int i=0;i<N-1;i++)scanf("%lld %lld %lld",&A[i],&B[i],&C[i]); for(int i=0;i<M-1;i++) { int start=P[i],end=P[i+1]; if(start>end)swap(start,end); imos[start]++; imos[end]--; } for(int i=0;i<N;i++)imos[i+1]+=imos[i]; ll ans = 0ll; for(int i=0;i<N-1;i++) { ll paper = A[i]*imos[i]; ll IC = C[i]+B[i]*imos[i]; ans += min(paper,IC); } printf("%lld\n",ans); return 0; }
2
1分位考えて区間DPやるだけだな〜と思って書く。
慎重に書いたらコンパイルエラーでず、サンプルも全部通ってさすがにビックリした。
ちょっと怖くなったのでprintfしたりして確認したけどやっぱり合ってるので提出。
AC。(ここまで45分くらい)
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; int N; ll A[4010]; ll dp[4010][4010]; ll rec(int l,int r) { if(l>r)return 0ll; if(l==r)return A[l]; if(dp[l][r]!=-1)return dp[l][r]; ll res; ll eat_l,eat_r; if(A[l+1]<A[r])eat_l = rec(l+1,r-1)+A[l]; else eat_l = rec(l+2,r)+A[l]; if(A[l]<A[r-1])eat_r = rec(l,r-2)+A[r]; else eat_r = rec(l+1,r-1)+A[r]; res = max(eat_l,eat_r); return dp[l][r]=res; } int main() { memset(dp,-1,sizeof(dp)); scanf("%d",&N); for(int i=0;i<N;i++)scanf("%lld",&A[i]); for(int i=0;i<N;i++)A[i+N]=A[i]; ll ans = 0ll; for(int i=0;i<N;i++) { //printf("%lld\n",rec(i,i+N-1)); ans = max(ans,rec(i,i+N-1)); } printf("%lld\n",ans); return 0; }
3
さすがにココらへんでムズいの来るかなと思って身構えたけどまさかのdijkstraやるだけ。
この調子で行けば目標のメダル獲得いけるのでは、思ったりする。
AC。(ここまで1時間15分くらい)
#include <cstdio> #include <algorithm> #include <queue> #include <utility> #include <vector> #include <iostream> using namespace std; typedef long long ll; typedef pair<ll,int> P; #define INF 30000000000000000ll #define fi first #define sec second #define pb push_back ll dist[100100]; ll ava[100100]; vector<P> vec; int N,M; ll C; struct edge { int to; ll cost; edge(int to,ll cost):to(to),cost(cost){} }; vector<edge> g[100100]; void dijkstra() { for(int i=0;i<N;i++)dist[i]=INF; dist[0]=0; priority_queue<P,vector<P>,greater<P> > q; q.push(P(0ll,0)); while(!q.empty()) { P a = q.top(); q.pop(); int v = a.sec; for(int i=0;i<g[v].size();i++) { edge e = g[v][i]; if(dist[e.to]>dist[v]+e.cost) { dist[e.to]=dist[v]+e.cost; q.push(P(dist[e.to],e.to)); } } } return; } int main() { ll sum = 0ll; scanf("%d %d %lld",&N,&M,&C); for(int i=0;i<M;i++) { int a,b; ll c; scanf("%d %d %lld",&a,&b,&c); a--;b--; sum+=c; g[a].pb(edge(b,c)); g[b].pb(edge(a,c)); } dijkstra(); for(int i=0;i<N;i++)vec.pb(P(dist[i],i)); sort(vec.begin(),vec.end()); ll ans = INF; for(int i=0;i<N;i++) { int v = vec[i].sec; //cout << v << endl; sum -= ava[v]; ans = min(C*vec[i].fi+sum,ans); //cout << C*vec[i].fi << ' ' << sum << endl; for(int j=0;j<g[v].size();j++) { edge e = g[v][j]; ava[e.to]+=e.cost; } } printf("%lld\n",ans); return 0; }
4
考えてみたけどイマイチよくわからなくて、制約的ににぶたんぽいなぁと踏んで、
判定関数以外のところをまず書いて、O(N)くらいで判定する方法を考えるもわからず。
とりあえず自明な部分点(8点)だけとって5へ。
5
去年の切り取り線みたいなヤバ問かと思ったら案外シンプルで解けそうだな〜と思いながら考える。
平面走査かなぁと踏んでsegtreeで平面走査して解けないか考えたり、PCKのFrameみたいに枠を半分に分けて出来ないかどうか考えたりしたけど結局わからず部分点を狙いに行く。
小課題1は2次元imosやるだけなのでOK.小課題2は包除原理でいけそうだなぁと思ったけど複数点通る枠の数を数えるのが複雑すぎて挫折。
とりあえず小課題1だけを取った(4点)
その後4の判定考えたり色々したけど時間だけが過ぎていき、競技終了。
100 + 100 + 100 + 8 + 4 = 312点
結果ほぼ0点同然の点だった。本当に自明な問題しか解いていないしとてもつらくなった。
競技終了直後に師匠に点数を聞いたら笑顔で全完と言っていてさすがだなぁと思った
解説を聞いた。4番はやはり予想は合っていたらしく、O(N)の判定が美しくて感動した。
反省しないといけないのは、三分木に見えていなかったことで、そう見えていればあとはできたと思う。
5番もそこまでヤバくなかったし、解けないといけない問題だった。
で、その後は特になにもなく帰りました。
今日のお昼に学校で春合宿にいけると知りました。
正直落ちたんじゃないかと思っていたので、ボーダーぎりぎりとはいえチャンスをつかめたので
嬉しいです。
更に実力をあげて、春合宿に望むつもりです。
2015年の目標
CF:赤
TC:赤
PCK:金
JOI:メダル獲得
IOIに行く
2014年を振り返って
一年前に
2014年 今年の目標 - (#・∀・)
という記事を書きました。
残念ながら全く目標を達成できませんでした(CFに関してはgood bye 2014で達成できたはずなのにくだらないミスでチャンスを逃しました)
来年はかならず目標を達成して見せます(目標は来年発表します)
