JOI夏季セミナー2017 チューター参加記
昨日までの5日間八王子の大学セミナーハウスでJOI夏季セミナーにチューターとして参加していました。
僕はMLPの「劣モジュラ最適化と機械学習」を担当しました。
5日間とにかく色んなことがあってある意味生徒として参加した時以上に濃い時間を過ごした(?)ので時系列順で書きます(一部当事者以外意味不明な部分があるかとは思いますがご容赦ください)
〜Day0
- 本が到着したのが試験期間直前だったので夏休みに入ってから色々予習する。
- 完全に読者は大学生以上の知識を前提として書かれていたので質問対応などを考えたりする
Day1
- 12時半頃出発してチューター当て用のカントリーマアムを買って八王子へ。八王子で道迷いしてバスを逃して15時集合に3分遅刻する
- potetiが生徒の集合時間にすら遅刻する
- 生徒の自己紹介のあとチューターの自己紹介&本紹介。だいぶ知らない顔ぶれになったなぁと感じる
- 今年はだいぶ予測しやすかったらしくチューター当て全完が3人も出てしまう
- セミナーはとりあえず初めの方の基礎的な章を読んでもらってわからないことがあったら聞いてくださいという感じでいく
- 全く質問が来ない(優秀)
- 生徒が全員AGCに出たいと言うので早めにセミナーを切り上げる。
- そして自分もAGCに出て死ぬ(これ以上は言及しません)(つよいこころをもってしょうじんします)
- ベッドでゴキブリ出現、萎える
Day2
- 朝食で恒例のしなしなポテトを食べる
- セミナーは昨日の続き
- 休憩がてら絵しりとりでも、と思いホワイトボードにりんごを書くも誰も続きを書いてくれない()
- omeさんの講義。自分の本で扱っている内容に近い話などもあって面白かった
- Pulmnくんがグラフカットで白黒画像のノイズ除去に成功する、進捗はやい
(ノイズ画像はX - この問題はほんとうにひどい問題であるため，できれば先に他の問題のほうをお楽しみいただければと思っておりまして，ですので他の問題を通し終えて暇になり，かつその暇をより)
- Xycaさんが実は割とつらいとのことなのでここからチューターらしく仕事し始める
- トイレに行って帰ってきたらセミナー室のドア付近に大量のスズメバチが発生しており部屋に入れない
- 施設の方にお願いして駆除してもらう
- 夜はチューター部屋にmaroonが遊びに来てpotetiが買ってきたNationalEconomyをみんなでやる
- 労働者大事(それはそう),果樹園つよい(それはそう)
Day3
- この日悲劇が起こることなど誰も予想していなかった
- この日の10時間のセミナーの進捗は大事なので助けが必要な人をサポートしつつ各位に頑張ってもらう
- 夕食に行く頃に髪が茶色の集団が現れる
- 交流の時間、各々いつくかのグループに分かれてボドゲをした。
- 持ってきたコードネームピクチャーズというのをした
- maroonが何度リベンジしても理不尽な負け方してて面白かった(可哀想)
明◯大学井.上ゼミナールはクソ
Day4
- チューター全員朝食を逃す
- 朝一で事務局に相談
- 眠すぎる
- 講義「競プロが何かは知りませんが、競プロでは食っていけません。コミュ力を上げましょう」
- 生徒部屋でCFの問題見たりする
- 昨日の睡眠不足でつらいので寝る
Day5
- いよいよ発表、各位のスライドを最終チェックする
- みんな大丈夫そうだったので安心する
- 青春アルゴリズムのモデルを聞いて納得したりする
- 筧先生「日本代表は大騒ぎで睡眠を阻害されて競技に影響が出るような精神力ではいけません」
- poteti,shiatsumatさんと中本に寄って帰宅
まとめ
全体的にJOIerの雰囲気もだいぶ変わったなぁという印象でした(老害)
代表になれなかったのでもうJOI関連のイベントには参加できないと思っていたのに今回たまたま声をかけて頂いて参加することができて嬉しかったです。
機会学習の本をじっくり読んだり、あったことのない次世代の競プロerと交流するいい機会になり、たくさんの刺激を受けて、本当に楽しかったです。
チューターとしての任務を全うできたかどうかはわかりませんが、自分の本を選んでくれた生徒各位がセミナーを楽しんでくれたことを願っています。
今後も競プロ、その他の情報分野の勉強を進め、精進していこうと思います。
ありがとうございました。
http s:// sound cloud.com/user-733379012/inoue-seminar-ha-kuso
AOJ 2450 Do use segment tree
重い。ただただ重い。
#define MAX_N 200100 #define MAX_LOG_V 20 const int SIZE = 1<<19; struct node{ int l,m,r,sum,lazy,ig; node(){ l = m = r = sum = ig = 0; lazy = INF; } node(int _ig){ l = m = r = sum = 0; lazy = INF; ig = _ig; } }; node update_node(node lch,node rch){ if(lch.ig)return rch; if(rch.ig)return lch; node ret; ret.m = max(max(lch.m,rch.m),lch.r+rch.l); ret.l = max(lch.l,lch.sum+rch.l); ret.r = max(rch.r,lch.r+rch.sum); ret.sum = lch.sum+rch.sum; return ret; } struct segtree{ node seg[SIZE*2]; void lazy_evaluate(int k,int l,int r){ if(seg[k].lazy==INF)return; seg[k].m = max(seg[k].lazy*(r-l),seg[k].lazy); seg[k].l = seg[k].m; seg[k].r = seg[k].m; seg[k].sum = seg[k].lazy*(r-l); if(k<SIZE-1){ seg[k*2+1].lazy = seg[k].lazy; seg[k*2+2].lazy = seg[k].lazy; } seg[k].lazy=INF; } void update(int a,int b,int k,int l,int r,int x){ lazy_evaluate(k,l,r); if(r<=a||b<=l)return; else if(a<=l&&r<=b){ seg[k].lazy = x; lazy_evaluate(k,l,r); return; }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] = update_node(seg[k*2+1],seg[k*2+2]); } } void update(int a,int b,ll x){ if(a>=b)return; update(a,b,0,0,SIZE,x); } node query(int a,int b,int k,int l,int r){ lazy_evaluate(k,l,r); if(r<=a||b<=l)return node(1); else if(a<=l&&r<=b)return seg[k]; else{ node lch = query(a,b,k*2+1,l,(l+r)/2); node rch = query(a,b,k*2+2,(l+r)/2,r); seg[k] = update_node(seg[k*2+1],seg[k*2+2]); return update_node(lch,rch); } } node query(int a,int b){ if(a>=b)return node(1); return query(a,b,0,0,SIZE); } }seg; struct HeavyLightDecomposition{ vector<int> g[MAX_N]; int N,root; int par[MAX_N]; int depth[MAX_N],chnum[MAX_N]; void add_edge(int a,int b){ g[a].pb(b); g[b].pb(a); } struct state{ int v,p,d; bool go; state(int v,int p,int d,bool go):v(v),p(p),d(d),go(go){} state(int v,int p,bool go):v(v),p(p),go(go){} }; void init(){ dfs(); decompose(); construct_toseg(); } void dfs(){ stack<state> st; st.push(state(0,-1,0,true)); while(!st.empty()){ state now = st.top(); st.pop(); int v = now.v,p = now.p,d = now.d; if(now.go){ depth[v]=d; par[v]=p; st.push(state(v,p,d,false)); for(int i=0;i<g[v].size();i++){ if(g[v][i]==p)continue; st.push(state(g[v][i],v,d+1,true)); } }else{ chnum[v]=1; for(int i=0;i<g[v].size();i++){ chnum[v]+=chnum[g[v][i]]; } } } return; } vector<int> top; int head[MAX_N]; int heavy[MAX_N]; int toseg[MAX_N]; int chain_len[MAX_N]; void decompose(){ stack<state> st; st.push(state(0,-1,true)); while(!st.empty()){ state now = st.top(); st.pop(); int v=now.v,p=now.p,istop=now.go; if(istop)top.pb(v); int hev = -1; int val = -1; for(int i=0;i<g[v].size();i++){ if(g[v][i]==p)continue; if(val<chnum[g[v][i]]){ val = chnum[g[v][i]]; hev = g[v][i]; } } heavy[v]=hev; for(int i=0;i<g[v].size();i++){ if(g[v][i]==p)continue; if(g[v][i]==hev)st.push(state(g[v][i],v,false)); else st.push(state(g[v][i],v,true)); } } } void construct_toseg(){ int id = 0; for(int i=0;i<top.size();i++){ int now = top[i]; while(1){ if(now==-1)break; toseg[now]=id++; head[now]=top[i]; now = heavy[now]; chain_len[top[i]]++; } } } int lca(int u,int v){ while(head[u]!=head[v]){ if(depth[head[u]]<depth[head[v]])swap(u,v); u = par[head[u]]; } return (depth[u]<depth[v])?u:v; } void update(int u,int v,int x){ if(u==v){ seg.update(toseg[u],toseg[u]+1,x); return; } int lc = lca(u,v); int nu = u,nv = v; while(depth[head[nu]]>depth[lc]){ seg.update(toseg[head[nu]],toseg[nu]+1,x); nu = par[head[nu]]; } seg.update(toseg[lc],toseg[nu]+1,x); while(depth[head[nv]]>depth[lc]){ seg.update(toseg[head[nv]],toseg[nv]+1,x); nv = par[head[nv]]; } seg.update(toseg[lc],toseg[nv]+1,x); } int query(int u,int v){ if(u==v)return seg.query(toseg[u],toseg[u]+1).m; int lc = lca(u,v); int nu=u,nv=v; node ansu = node(1); node ansv = node(1); while(depth[head[nu]]>depth[lc]){ ansu = update_node(seg.query(toseg[head[nu]],toseg[nu]+1),ansu); nu = par[head[nu]]; } bool flag = false; if(nu!=lc){ ansu = update_node(seg.query(toseg[lc],toseg[nu]+1),ansu); flag = true; } while(depth[head[nv]]>depth[lc]){ ansv = update_node(seg.query(toseg[head[nv]],toseg[nv]+1),ansv); nv = par[head[nv]]; } if(!flag){ ansv = update_node(seg.query(toseg[lc],toseg[nv]+1),ansv); } swap(ansu.l,ansu.r); node ans = update_node(ansu,ansv); return ans.m; } }hld; int N,Q; int w[200100]; int main(){ scanf("%d %d",&N,&Q); hld.N = N; for(int i=0;i<N;i++)scanf("%d",&w[i]); for(int i=0;i<N-1;i++){ int a,b; scanf("%d %d",&a,&b); a--;b--; hld.add_edge(a,b); } hld.root = 0; hld.init(); for(int i=0;i<N;i++)hld.update(i,i,w[i]); for(int i=0;i<Q;i++){ int t,u,v,x; scanf("%d %d %d %d",&t,&u,&v,&x); u--;v--; if(t==1)hld.update(u,v,x); else printf("%d\n",hld.query(u,v)); } return 0; }
JOI 春合宿 2013 Day2
2時間45分で全完。
取れる問題ちゃんと取れたので良かった
建設事業
平面走査 + segtree + Kruskal + 貪欲
典型盛り合わせみたいな問題で難しいとは感じなかった。
struct edge{ int from,to; ll cost; edge(){} edge(int from,int to,ll cost):from(from),to(to),cost(cost){} bool operator < (const edge& a) const{ return cost < a.cost; } }; struct event{ int x,type; P l,r; // [l,r] event(){} event(int x,P l,P r,int type):x(x),l(l),r(r),type(type){} bool operator < (const event& a) const{ if(x!=a.x)return x < a.x; return type < a.type; } }; const int SIZE = 1<<20; struct segtree{ int seg[SIZE*2],lazy[SIZE*2]; void lazy_evaluate(int k,int l,int r){ seg[k]+=lazy[k]*(r-l); if(k<SIZE-1){ lazy[k*2+1]+=lazy[k]; lazy[k*2+2]+=lazy[k]; } lazy[k]=0; } void update(int a,int b,int k,int l,int r,int x){ lazy_evaluate(k,l,r); if(r<=a||b<=l)return; else if(a<=l&&r<=b){ lazy[k]+=x; lazy_evaluate(k,l,r); }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]=seg[k*2+1]+seg[k*2+2]; } } int query(int a,int b,int k,int l,int r){ lazy_evaluate(k,l,r); if(r<=a||b<=l)return 0; else 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]=seg[k*2+1]+seg[k*2+2]; return lch+rch; } } void update(int a,int b,int x){ update(a,b,0,0,SIZE,x); } int query(int a,int b){ return query(a,b,0,0,SIZE); } }; struct UnionFind{ int par[SIZE],rank[SIZE]; void init(){ for(int i=0;i<SIZE;i++){ par[i]=i; rank[i]=0; } } int find(int x){ if(par[x]==x)return x; else 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); } }; int N,M,C; int X[200100],Y[200100],H[500100]; int p[200100],q[200100],r[200100],s[200100]; ll B[500100]; vector<P> fx[600100],fy[600100]; vector<int> zx,zy; vector<ll> uc; vector<edge> es; vector<event> evx,evy; segtree seg; UnionFind uf; int main(){ scanf("%d %d %d",&N,&M,&C); for(int i=0;i<N;i++){ scanf("%d %d",&X[i],&Y[i]); zx.pb(X[i]); zy.pb(Y[i]); } for(int i=0;i<M;i++){ scanf("%d %d %d %d",&p[i],&q[i],&r[i],&s[i]); zx.pb(p[i]);zx.pb(r[i]); zy.pb(q[i]);zy.pb(s[i]); } for(int i=0;i<C;i++){ scanf("%lld %d",&B[i],&H[i]); } sort(all(zx)); sort(all(zy)); zx.erase(unique(all(zx)),zx.end()); zy.erase(unique(all(zy)),zy.end()); for(int i=0;i<N;i++){ X[i] = lower_bound(all(zx),X[i])-zx.begin(); Y[i] = lower_bound(all(zy),Y[i])-zy.begin(); } for(int i=0;i<M;i++){ p[i] = lower_bound(all(zx),p[i])-zx.begin(); q[i] = lower_bound(all(zy),q[i])-zy.begin(); r[i] = lower_bound(all(zx),r[i])-zx.begin(); s[i] = lower_bound(all(zy),s[i])-zy.begin(); } // | ---> for(int i=0;i<N;i++){ fx[X[i]].pb(P(Y[i],i)); } for(int i=0;i<zx.size();i++)sort(all(fx[i])); for(int i=0;i<zx.size();i++){ for(int j=1;j<fx[i].size();j++){ evx.pb(event(i,fx[i][j-1],fx[i][j],1)); } } for(int i=0;i<M;i++){ evx.pb(event(p[i],P(q[i],-1),P(s[i],-1),0)); evx.pb(event(r[i],P(q[i],-1),P(s[i],-1),2)); } sort(all(evx)); for(int i=0;i<evx.size();i++){ event e = evx[i]; //printf("%d %d %d %d\n",zx[e.x],zy[e.l.fi],zy[e.r.fi],e.type); if(e.type==0){ seg.update(e.l.fi,e.r.fi+1,1); }else if(e.type==1){ if(seg.query(e.l.fi,e.r.fi+1)==0){ es.pb(edge(e.l.sec,e.r.sec,zy[e.r.fi]-zy[e.l.fi])); } }else{ seg.update(e.l.fi,e.r.fi+1,-1); } } // ----- ^ for(int i=0;i<N;i++){ fy[Y[i]].pb(P(X[i],i)); } for(int i=0;i<zy.size();i++)sort(all(fy[i])); for(int i=0;i<zy.size();i++){ for(int j=1;j<fy[i].size();j++){ evy.pb(event(i,fy[i][j-1],fy[i][j],1)); } } for(int i=0;i<M;i++){ evy.pb(event(q[i],P(p[i],-1),P(r[i],-1),0)); evy.pb(event(s[i],P(p[i],-1),P(r[i],-1),2)); } sort(all(evy)); for(int i=0;i<evy.size();i++){ event e = evy[i]; //printf("%d %d %d %d\n",zy[e.x],zx[e.l.fi],zx[e.r.fi],e.type); if(e.type==0){ seg.update(e.l.fi,e.r.fi+1,1); }else if(e.type==1){ if(seg.query(e.l.fi,e.r.fi+1)==0){ es.pb(edge(e.l.sec,e.r.sec,zx[e.r.fi]-zx[e.l.fi])); } }else{ seg.update(e.l.fi,e.r.fi+1,-1); } } sort(all(es)); ll base = 0ll; uf.init(); for(int i=0;i<es.size();i++){ edge e = es[i]; //printf("%d %d %lld\n",e.from,e.to,e.cost); if(!uf.same(e.from,e.to)){ uf.unite(e.from,e.to); uc.pb(e.cost); base += e.cost; } } int cnt = sz(uc); vector<ll> sum = uc; sum.pb(0ll); for(int i=cnt-1;i>=0;i--)sum[i]+=sum[i+1]; for(int i=0;i<C;i++){ if(N-cnt>H[i]){ printf("-1\n"); }else{ ll ans = base+(N-cnt)*B[i]; int k = upper_bound(all(uc),B[i])-uc.begin(); int chg = min(H[i]-(N-cnt),cnt-k); ans += B[i]*(ll)chg-sum[cnt-chg]; printf("%lld\n",ans); } } return 0; }
マスコットの片付け
上下、左右を同時に扱ってDPの計算量を落とす。問題読んですぐに解法がわかった。
#define MOD 1000000007 int N,R,C; int ax=INF,ay=INF,bx=-1,by=-1; ll fac[4010]; ll dp[3010][3010]; ll mpow(ll a,ll x){ ll res = 1ll; while(x){ if(x&1)res = (res*a)%MOD; a = (a*a)%MOD; x >>= 1; } return res; } ll fact(int x){ if(x<4000)return fac[x]; ll res = 1; for(int i=1;i<=x;i++)res = (res*(ll)i)%MOD; return res; } ll func(int a,int b){ ll res = fact(a+b); ll inva = mpow(fact(a),MOD-2); ll invb = mpow(fact(b),MOD-2); res = (res*inva%MOD)*invb%MOD; return res; } int main(){ scanf("%d %d",&R,&C); scanf("%d",&N); for(int i=0;i<N;i++){ int x,y; scanf("%d %d",&x,&y); ax = min(ax,x); ay = min(ay,y); bx = max(bx,x); by = max(by,y); } fac[0]=1ll; for(int i=1;i<4000;i++)fac[i]=(fac[i-1]*(ll)i)%MOD; int cx = bx-ax+1,cy = by-ay+1; int f = cx*cy-N; int rx = R-cx,ry = C-cy; dp[0][0]=1ll; for(int i=0;i<=rx;i++){ for(int j=0;j<=ry;j++){ if(i<rx)dp[i+1][j] = (dp[i+1][j]+dp[i][j]*fac[cy+j])%MOD; if(j<ry)dp[i][j+1] = (dp[i][j+1]+dp[i][j]*fac[cx+i])%MOD; } } ll ans = fact(f)*dp[rx][ry]%MOD; ans = ans*func(ax-1,R-bx)%MOD; ans = ans*func(ay-1,C-by)%MOD; printf("%lld\n",ans); return 0; }
スパイ
オイラーツアー + 2次元imos法
vector<int> g[2][2010]; vector<int> euler[2]; int beg[2][2010],end[2][2010]; int root[2]; int k,idx; void dfs(int v){ beg[k][v]=idx++; for(int i=0;i<g[k][v].size();i++){ dfs(g[k][v][i]); } end[k][v]=idx++; } int N,M; int cnt[4010][4010]; void add(int a,int b,int c,int d){ cnt[a][c]++; cnt[a][d]--; cnt[b][c]--; cnt[b][d]++; } int main(){ scanf("%d %d",&N,&M); for(int i=0;i<N;i++){ int p,q; scanf("%d %d",&p,&q); p--;q--; if(p>=0)g[0][p].pb(i); else root[0]=i; if(q>=0)g[1][q].pb(i); else root[1]=i; } for(k=0;k<2;k++){ idx=0; dfs(root[k]); } /*for(int i=0;i<2;i++){ for(int j=0;j<N;j++){ printf("%d %d\n",beg[i][j],end[i][j]); } }*/ for(int i=0;i<M;i++){ int r,s; scanf("%d %d",&r,&s); r--;s--; add(beg[0][r],end[0][r],beg[1][s],end[1][s]); } for(int i=1;i<4010;i++){ for(int j=0;j<4010;j++){ cnt[i][j]+=cnt[i-1][j]; } } for(int j=1;j<4010;j++){ for(int i=0;i<4010;i++){ cnt[i][j]+=cnt[i][j-1]; } } for(int i=0;i<N;i++)printf("%d\n",cnt[beg[0][i]][beg[1][i]]); return 0; }
解き初め JOI 2012春 Building 2
解き納めにするつもりやったのにくだらんバグで6分間に合わんかった…。
典型の組合せで綺麗。好き。
今年は最後の一年やから何事も悔いのないように全力でやり切ります。
難易度12は残り3問。
int N; int H[100100]; vector<int> up[100100]; vector<int> down[100100]; vector<int> g[100100]; void merge(vector<int> &a,vector<int> &b){ if(sz(a)<sz(b))swap(a,b); for(int i=0;i<sz(b);i++)a[i]=min(a[i],b[i]); } int dfs(int v,int p){ int res = 0; for(int i=0;i<g[v].size();i++){ if(g[v][i]==p)continue; int u = g[v][i]; res = max(res,dfs(u,v)); bool flag = false; if(sz(up[v])>sz(down[u])){ swap(up[v],down[u]); flag = true; } for(int j=0;j<up[v].size();j++){ int k = lower_bound(all(down[u]),-up[v][j])-down[u].begin(); res = max(res,j+k+1); if(up[v][j]<(flag?-H[v]:H[v])){ k = lower_bound(all(down[u]),(flag?H[v]:-H[v]))-down[u].begin(); res = max(res,j+k+2); } } if(flag)swap(up[v],down[u]); flag = false; if(sz(up[u])>sz(down[v])){ swap(up[u],down[v]); flag = true; } for(int j=0;j<up[u].size();j++){ int k = lower_bound(all(down[v]),-up[u][j])-down[v].begin(); res = max(res,j+k+1); if(up[u][j]<(flag?-H[v]:H[v])){ k = lower_bound(all(down[v]),(flag?H[v]:-H[v]))-down[v].begin(); res = max(res,j+k+2); } } if(flag)swap(up[u],down[v]); merge(up[v],up[u]); merge(down[v],down[u]); } vector<int>::iterator it; it = lower_bound(all(up[v]),H[v]); if(it==up[v].end())up[v].pb(H[v]); else *it=H[v]; it = lower_bound(all(down[v]),-H[v]); if(it==down[v].end())down[v].pb(-H[v]); else *it=-H[v]; res = max(res,sz(up[v])); res = max(res,sz(down[v])); return res; } int main(){ scanf("%d",&N); for(int i=0;i<N;i++)scanf("%d",&H[i]); for(int i=0;i<N-1;i++){ int a,b; scanf("%d %d",&a,&b); a--;b--; g[a].pb(b); g[b].pb(a); } printf("%d\n",dfs(0,-1)); return 0; }
JOI2016 予選
最後のJOI予選、やるだけセットやったのに誤読で時間消費してデバッグギリギリ間に合わんかった。
しかもバグは2箇所!が|になってただけ。クソクソクソクソ。死にたい。
本選、春まで死ぬ気で問題解きまくる。
予選満点ちゃうかっても代表にはなったるからな。
1
int main(){ vector<int> a(4),b(2); for(int i=0;i<4;i++)scanf("%d",&a[i]); for(int i=0;i<2;i++)scanf("%d",&b[i]); sort(all(a),greater<int>()); sort(all(b),greater<int>()); int ans = 0; for(int i=0;i<3;i++)ans += a[i]; ans += b[0]; printf("%d\n",ans); return 0; }
2
int N,M; int A[105]; int main(){ scanf("%d %d",&N,&M); for(int i=0;i<N;i++)scanf("%d",&A[i]); for(int i=1;i<=M;i++){ for(int j=0;j<N-1;j++){ if(A[j]%i>A[j+1]%i)swap(A[j],A[j+1]); } } for(int i=0;i<N;i++)printf("%d\n",A[i]); return 0; }
3
int N,M; string s[55]; int culc(int u,int d){ int res = 0; for(int i=0;i<N;i++){ for(int j=0;j<M;j++){ if(i<=u&&s[i][j]!='W')res++; if(i>u&&i<=d&&s[i][j]!='B')res++; if(i>d&&s[i][j]!='R')res++; } } return res; } int main(){ scanf("%d %d",&N,&M); for(int i=0;i<N;i++)cin >> s[i]; int ans = INF; for(int i=0;i<N-2;i++){ for(int j=i+1;j<N-1;j++){ ans = min(ans,culc(i,j)); } } printf("%d\n",ans); return 0; }
4
int N,Q,D[100100],X[1010]; ll T,A[100100]; int east[100100],west[100100]; int main(){ scanf("%d %lld %d",&N,&T,&Q); memset(east,-1,sizeof(east)); memset(west,-1,sizeof(west)); for(int i=0;i<N;i++){ scanf("%lld %d",&A[i],&D[i]); if(D[i]==1)east[i]=i; else west[i]=i; } for(int i=1;i<N;i++)east[i]=(east[i]==-1)?east[i-1]:east[i]; for(int i=N-2;i>=0;i--)west[i]=(west[i]==-1)?west[i+1]:west[i]; //for(int i=0;i<N;i++)printf("%d%c",east[i],(i==N-1)?'\n':' '); //for(int i=0;i<N;i++)printf("%d%c",west[i],(i==N-1)?'\n':' '); for(int i=0;i<Q;i++){ scanf("%d",&X[i]); X[i]--; } for(int i=0;i<Q;i++){ if(D[X[i]]==1){ int a = west[X[i]]; if(a==-1){ printf("%lld\n",A[X[i]]+T); continue; } int b = east[a]; ll crash = A[a]/2ll+A[b]/2ll; printf("%lld\n",min(A[X[i]]+T,crash)); }else{ int a = east[X[i]]; if(a==-1){ printf("%lld\n",A[X[i]]-T); continue; } int b = west[a]; ll crash = A[a]/2ll+A[b]/2ll; printf("%lld\n",max(A[X[i]]-T,crash)); } } return 0; }
5
int N,M,K,S; ll p,q; int C[100100]; vector<int> g[100100]; struct edge{ int to; ll cost; edge(int to,ll cost):to(to),cost(cost){} }; vector<edge> G[100100]; int a[200100],b[200100]; ll d[100100]; void dijkstra(){ for(int i=0;i<N;i++)d[i]=INF; priority_queue<P,vector<P>,greater<P> > q; for(int i=0;i<K;i++){ d[C[i]]=0; q.push(P(0,C[i])); } while(!q.empty()){ P a = q.top(); q.pop(); int v = a.sec; if(d[v]<a.fi)continue; for(int i=0;i<g[v].size();i++){ int to = g[v][i]; if(d[to]>d[v]+1){ d[to]=d[v]+1; q.push(P(d[to],to)); } } } /*for(int i=0;i<N;i++)printf("%d ",d[i]); printf("\n");*/ } ll D[100100]; void dijkstra2(){ for(int i=0;i<N;i++)D[i]=LLINF; priority_queue<P,vector<P>,greater<P> > Q; Q.push(P(0ll,0)); D[0]=0ll; while(!Q.empty()){ P a = Q.top(); Q.pop(); int v = a.sec; if(D[v]<a.fi)continue; for(int i=0;i<G[v].size();i++){ edge e = G[v][i]; if(D[e.to]>D[v]+e.cost){ D[e.to]=D[v]+e.cost; Q.push(P(D[e.to],e.to)); } } } } int main(){ scanf("%d %d %d %d",&N,&M,&K,&S); scanf("%lld %lld",&p,&q); for(int i=0;i<K;i++){ scanf("%d",&C[i]); C[i]--; } for(int i=0;i<M;i++){ scanf("%d %d",&a[i],&b[i]); a[i]--;b[i]--; g[a[i]].pb(b[i]); g[b[i]].pb(a[i]); } dijkstra(); for(int i=0;i<M;i++){ if(d[a[i]]==0||d[b[i]]==0)continue; if(d[a[i]]<=S)G[b[i]].pb(edge(a[i],q)); else G[b[i]].pb(edge(a[i],p)); if(b[i]==N-1)G[a[i]].pb(edge(b[i],0ll)); else if(d[b[i]]<=S)G[a[i]].pb(edge(b[i],q)); else G[a[i]].pb(edge(b[i],p)); } dijkstra2(); printf("%lld\n",D[N-1]); return 0; }
6
int H,W; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int dp[1050][1050][32]; int f[1050][1050]; int cost(int i,int j,int k,int m){ int c = 0; if(!(k&16))c+=f[i][j]; if(m!=0)c+=f[i][j+1]; if(m!=1)c+=f[i+1][j]; if(m!=2&&!(k&2))c+=f[i][j-1]; if(m!=3&&!(k&4))c+=f[i-1][j]; return c; } int moved(int k,int m){ int nk = 0; if(k&1)nk|=2; nk|=4; if(m!=0)nk|=8; if(m!=1)nk|=16; return nk; } int mover(int k,int m){ int nk = 0; if(k&8)nk|=4; nk|=2; if(m!=1)nk|=1; if(m!=0)nk|=16; return nk; } int main(){ scanf("%d %d",&H,&W); for(int i=0;i<H;i++){ string s; cin >> s; for(int j=0;j<W;j++){ if(s[j]=='.')f[i+1][j+1]=0; else f[i+1][j+1]=(int)(s[j]-'0'); } } for(int i=1;i<=H;i++)for(int j=1;j<=W;j++)for(int k=0;k<32;k++)dp[i][j][k]=INF; dp[1][1][0]=0; for(int i=1;i<=H;i++){ for(int j=1;j<=W;j++){ //printf("%d %d : ",i,j); for(int k=0;k<32;k++){ if(dp[i][j][k]==INF)continue; //printf("%d ",dp[i][j][k]); for(int m=0;m<4;m++){ int c = cost(i,j,k,m); int dk = moved(k,m); int rk = mover(k,m); //if(i==1)printf("%d %d %d\n",c,dk,rk); dp[i+1][j][dk]=min(dp[i+1][j][dk],dp[i][j][k]+c); dp[i][j+1][rk]=min(dp[i][j+1][rk],dp[i][j][k]+c); } } //printf("\n"); } } int ans = INF; for(int i=0;i<32;i++)ans=min(ans,dp[H][W][i]); printf("%d\n",ans); return 0; }
PCK 2015 本選 参加記
激冷え。
PCK 2015 予選
9AC1WAでした。8間に合わなくて速度不足を痛感。本選までもっと実装力も発想力も鍛えます。
1~7を自分が解いて9をeyさんが解いて10を二人で解きました(eyさんが最初に解いたがWAが出て自分がデバッグした)
8ほぼ書き終わってたのに間に合わなくて辛い(TrieでやるとMLEするらしいのでどの道通せてなかったかも)
おそらく4位。去年より順位下がってつらい。
1 やるだけ
int main() { int p,m,c; cin >> p >> m >> c; cout << p+m+c << endl; return 0; }
2 やるだけ
int h1,h2; int k1,k2; int a,b,c,d; int main() { scanf("%d %d",&h1,&h2); scanf("%d %d",&k1,&k2); scanf("%d %d %d %d",&a,&b,&c,&d); int h = 0,k = 0; h = h1*a+h2*b+(h1/10)*c+(h2/20)*d; k = k1*a+k2*b+(k1/10)*c+(k2/20)*d; if(h>k)printf("hiroshi\n"); else if(k>h)printf("kenjiro\n"); else printf("even\n"); return 0; }
3 やるだけ
int D,L; int main() { scanf("%d %d",&D,&L); printf("%d\n",(D/L)+(D%L)); return 0; }
4 やるだけ
int N; int a[105]; int main() { memset(a,0,sizeof(a)); scanf("%d",&N); for(int i=0;i<3;i++) { int k; scanf("%d",&k); for(int j=0;j<k;j++) { int val; scanf("%d",&val); val--; a[val]|=(1<<i); } } int ans = 0; for(int i=0;i<N;i++) { //printf("%d %d\n",i,a[i]); if(a[i]==7||a[i]==6||a[i]==4)ans++; } printf("%d\n",ans); return 0; }
5 やるだけ
int N; int p[105]; int imos[105]; int main() { scanf("%d",&N); for(int i=0;i<N;i++)scanf("%d",&p[i]); for(int i=0;i<N;i++)imos[p[i]]++; for(int i=100;i>0;i--)imos[i-1]+=imos[i]; for(int i=100;i>=0;i--)if(imos[i]>=i) { printf("%d\n",i); return 0; } return 0; }
6 やるだけ
int C,N; char ch[1010][1010]; int f[1010][1010]; bool ok[1010][1010]; int bad = 0; bool check(int x,int y) { if(f[x][y]==f[x][N-1-y]&&f[x][y]==f[N-1-x][y]&&f[x][y]==f[N-1-x][N-1-y])return true; return false; } int ans = 0; int main() { scanf("%d %d",&C,&N); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { cin >> ch[i][j]; } } for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { if(ch[i][j]=='0')f[i][j]=0; else f[i][j]=1; } } int M = N/2; for(int i=0;i<M;i++) { for(int j=0;j<M;j++) { if(check(i,j))ok[i][j]=true; else { ok[i][j]=false; bad++; } } } if(bad==0)ans++; for(int i=0;i<C-1;i++) { int k; scanf("%d",&k); for(int j=0;j<k;j++) { int x,y; scanf("%d %d",&x,&y); x--;y--; f[x][y]^=1; if(x>=M)x=N-1-x; if(y>=M)y=N-1-y; bool d = check(x,y); if(d!=ok[x][y]) { if(d)bad--; else bad++; } ok[x][y]=d; } if(bad==0)ans++; } printf("%d\n",ans); return 0; }
7 UnionFind使うだけ
const int SIZE = 250000; struct UnionFind { int par[SIZE]; void init(int n) { for(int i=0;i<n;i++) { par[i] = i; } } 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(x > y)par[y] = x; else par[x] = y; } bool same(int x,int y) { return find(x) == find(y); } }uf; int N,M,K; int main() { scanf("%d %d %d",&N,&M,&K); //0 N-1 N N+M-1 uf.init(N+M); for(int i=0;i<K;i++) { int type; int a,b,c,x; scanf("%d",&type); if(type==1) { scanf("%d %d",&a,&b); a--;b--; a = uf.find(a); b = uf.find(b); //cout << a << ' ' << b << endl; if(a>=N&&b>=N&&a!=b) { printf("%d\n",i+1); return 0; } uf.unite(a,b); } else { scanf("%d %d",&c,&x); c--;x--; c = uf.find(c); //cout << c << ' ' << x+N << endl; if(c>=N&&c!=x+N) { printf("%d\n",i+1); return 0; } uf.unite(c,x+N); } } printf("0\n"); return 0; }
8 Trieで数えるだけだと思ったけどロリハじゃないと通らないらしい
9 二分探索
#define INF 100000000 using namespace std; typedef pair<double,double> P; long long x[100000]; long long r[100000]; double min(double a,double b){return a<b?a:b;} double max(double a,double b){return a>b?a:b;} P cross(P a,P b){ return P(max(a.first,b.first),min(a.second,b.second)); } bool solve(double w,int n){ P seg=P(-INF,INF); for(int i=0;i<n;i++){ if(w>r[i])return false; double left=x[i]-sqrt(r[i]*r[i]-w*w); double right=x[i]+sqrt(r[i]*r[i]-w*w); P cseg=cross(seg,P(left,right)); if(cseg.first>cseg.second)return false; else seg=cseg; } return true; } int main(){ int n,i; scanf("%d",&n); for(i=0;i<n;i++)scanf("%lld %lld",&x[i],&r[i]); double bottom=0,top=1000001; for(int bi=0;bi<40;bi++){ double mid=(bottom+top)/2; if(solve(mid,n))bottom=mid; else top=mid; } printf("%.12lf\n",bottom); return 0; }
10 JOI春のオリエンテーリングみたいにトポソして片方先に行かせながらDP
#define INF 1000000000000LL typedef pair<int,int> P; vector<P> re[1000]; int cost1[2000]; int cost2[2000]; bool used[1000]; vector<int> ord; long long dp[1000][1000]; int depth[1000]; long long min(long long a,long long b){return a<b?a:b;} void dfs(int v){ used[v]=true; for(int i=0;i<re[v].size();i++){ int u=re[v][i].first; if(!used[u])dfs(u); } ord.push_back(v); } int main(){ int n,m,i,j,k,l; scanf("%d %d",&n,&m); for(i=0;i<m;i++){ int a,b; scanf("%d %d %d %d",&a,&b,&cost1[i],&cost2[i]); a--;b--; re[b].push_back(P(a,i)); } for(i=0;i<n;i++)used[i]=false; dfs(n-1); for(i=0;i<n;i++)for(j=0;j<n;j++)dp[i][j]=INF; dp[ord[0]][ord[0]]=0; for(i=0;i<n;i++)depth[ord[i]]=i; for(i=0;i<n;i++){ for(j=i;j<n;j++){ int u=ord[i]; int v=ord[j]; if(u!=v){ for(k=0;k<re[v].size();k++){ int w=re[v][k].first; int e=re[v][k].second; if(depth[u]<=depth[w])dp[u][v]=min(dp[u][v],dp[u][w]+cost1[e]); else dp[u][v]=min(dp[u][v],dp[w][u]+cost1[e]); } } else{ for(k=0;k<re[v].size();k++){ for(l=0;l<re[v].size();l++){ int w1=re[v][k].first; int e1=re[v][k].second; int w2=re[v][l].first; int e2=re[v][l].second; if(e1==e2)dp[v][v]=min(dp[v][v],dp[w1][w1]+cost1[e1]+cost2[e1]); else{ if(depth[w1]<=depth[w2])dp[v][v]=min(dp[v][v],dp[w1][w2]+cost1[e1]+cost1[e2]); else dp[v][v]=min(dp[v][v],dp[w2][w1]+cost1[e1]+cost1[e2]); } } } } } } printf("%lld\n",dp[n-1][n-1]); return 0; }
