AOJ 2642 Dinner

自炊する日を{ \displaystyle a_0,a_1,...,a_{k-1}}{ \displaystyle k}日間(日は0-indexed)とし、{ \displaystyle S = \sum_{i=0}^{N-1} C_i}とおくと幸福度は{ \displaystyle S+\sum_{i=0}^{k-1}\{P(Q-a_i+2i)-C_{a_i}\} = S+kPQ+Pk(k-1)-\sum_{i=0}^{k-1}\{Pa_i+C_{a_i}\}}
よってkを固定した時、P*i+C[i]が小さいものから順にk個選ぶのが最適。

ちゃんと定式化するの大事…

ll N,P,Q;
ll C[500100];
vector<ll> vec;
int main(){
	scanf("%lld %lld %lld",&N,&P,&Q);
	ll sum = 0;
	for(int i=0;i<N;i++){
		scanf("%lld",&C[i]);
		sum += C[i];
		vec.pb(P*i+C[i]);
	}
	sort(all(vec));
	for(int i=1;i<vec.size();i++)vec[i]+=vec[i-1];
	ll ans = sum;
	for(int i=1;i<=N;i++)chmax(ans,sum+i*P*Q+P*i*(i-1)-vec[i-1]);
	cout << ans << endl;
	return 0;
}

JOI夏季セミナー2017 チューター参加記

昨日までの5日間八王子の大学セミナーハウスでJOI夏季セミナーにチューターとして参加していました。
僕はMLPの「劣モジュラ最適化と機械学習」を担当しました。
5日間とにかく色んなことがあってある意味生徒として参加した時以上に濃い時間を過ごした(?)ので時系列順で書きます(一部当事者以外意味不明な部分があるかとは思いますがご容赦ください)

〜Day0
  • 本が到着したのが試験期間直前だったので夏休みに入ってから色々予習する。
  • 完全に読者は大学生以上の知識を前提として書かれていたので質問対応などを考えたりする
Day1
  • 12時半頃出発してチューター当て用のカントリーマアムを買って八王子へ。八王子で道迷いしてバスを逃して15時集合に3分遅刻する
  • potetiが生徒の集合時間にすら遅刻する
  • 生徒の自己紹介のあとチューターの自己紹介&本紹介。だいぶ知らない顔ぶれになったなぁと感じる
  • 今年はだいぶ予測しやすかったらしくチューター当て全完が3人も出てしまう
  • セミナーはとりあえず初めの方の基礎的な章を読んでもらってわからないことがあったら聞いてくださいという感じでいく
  • 全く質問が来ない(優秀)
  • 生徒が全員AGCに出たいと言うので早めにセミナーを切り上げる。
  • そして自分もAGCに出て死ぬ(これ以上は言及しません)(つよいこころをもってしょうじんします)
  • ベッドでゴキブリ出現、萎える
Day2
  • 朝食で恒例のしなしなポテトを食べる
  • セミナーは昨日の続き
  • 休憩がてら絵しりとりでも、と思いホワイトボードにりんごを書くも誰も続きを書いてくれない()
  • omeさんの講義。自分の本で扱っている内容に近い話などもあって面白かった
  • Pulmnくんがグラフカットで白黒画像のノイズ除去に成功する、進捗はやい

f:id:okuraofvegetable:20170831202513p:plain
f:id:okuraofvegetable:20170831202526p:plain
(ノイズ画像はX: この問題はほんとうにひどい問題であるため,できれば先に他の問題のほうをお楽しみいただければと思っておりまして,ですので他の問題を通し終えて暇になり,かつその暇を - お誕生日コンテスト | AtCoderより)

  • Xycaさんが実は割とつらいとのことなのでここからチューターらしく仕事し始める
  • トイレに行って帰ってきたらセミナー室のドア付近に大量のスズメバチが発生しており部屋に入れない
  • 施設の方にお願いして駆除してもらう
  • 夜はチューター部屋にmaroonが遊びに来てpotetiが買ってきたNationalEconomyをみんなでやる

f:id:okuraofvegetable:20170831065126j:plain

  • 労働者大事(それはそう),果樹園つよい(それはそう)
Day3
  • この日悲劇が起こることなど誰も予想していなかった
  • この日の10時間のセミナーの進捗は大事なので助けが必要な人をサポートしつつ各位に頑張ってもらう
  • 夕食に行く頃に髪が茶色の集団が現れる
  • 交流の時間、各々いつくかのグループに分かれてボドゲをした。
  • 持ってきたコードネームピクチャーズというのをした

f:id:okuraofvegetable:20170831071051j:plain

  • maroonが何度リベンジしても理不尽な負け方してて面白かった(可哀想)
  • 部屋に帰ると何度も別団体がドアを開けてくるとnamonakiが言っていて草を生やす
  • namonakiが聞いた「し◯◯◯よ◯◯◯」で草を生やす
  • 風呂に入って193くんがチューター部屋に遊びに来る、またNationalEconomyをする
  • 何度も別団体がドアを開けてくる(草)
  • 見えないモノを見ようとして望遠鏡を覗き込む奴に草を生やす
  • 12時頃から騒がしさが増してくる
  • 1時半頃うわさを聞きつけたKmcodeくんがチューター部屋に遊びに来てしまう
  • 2時を過ぎても異常なうるささが続いて到底寝れない状態が続く
  • 流石に笑い事では済まないので証拠提出のために僕が録音する
  • 廊下を酔っぱらいが徘徊していて危険な状態なので生徒2人はやむなくチューター部屋待機
  • 3時前にチューター付き添いで生徒帰還成功
  • 静まって来たかと思ったが甘かった
  • 3時半頃大音量で音楽を流し叫び始める
  • 寝ようと努力するも寝れず
  • 4時頃鍵を閉めているのに無理やり開けようとし、身の危険を感じるレベルでドアを蹴ってきて寝ていた人も起きる
  • 各々イヤホンしたりして頑張って寝る
  • 明◯大学井.上ゼミナールはクソ
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箇所!が|になってただけ。クソクソクソクソ。死にたい。
f:id:okuraofvegetable:20151213234736p:plain
本選、春まで死ぬ気で問題解きまくる。
予選満点ちゃうかっても代表にはなったるからな。

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;
}