読者です 読者をやめる 読者になる 読者になる

Codeforces Round #371 (Div. 1)

ク ソ コ ン テ ス ト

A B C D E Place
00:04 00:37 00:20 01:36 - 7th

A:
もちろんmultisetなぞ必要なく、偶奇の組み合わせごとに何個あるか持っておけばよい。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[20];
int c[1<<18];
int main(){
	int a;scanf("%d",&a);
	while(a--){
		scanf("%s",in);
		long long b;
		scanf("%I64d",&b);
		if(in[0]=='+'){
			int now=0;
			for(int i=0;i<18;i++){
				if(b%2)now+=(1<<i);
				b/=10;
			}
			c[now]++;
		}else if(in[0]=='-'){
			int now=0;
			for(int i=0;i<18;i++){
				if(b%2)now+=(1<<i);
				b/=10;
			}
			c[now]--;
		}else{
			int now=0;
			for(int i=0;i<18;i++){
				if(b%2)now+=(1<<i);
				b/=10;
			}
			printf("%d\n",c[now]);
		}
	}
}

B:
二分探索でどこに上下左右の辺があるかがわかる。あとはどの辺がどの長方形に対応しているのかを全部試せばよい。結構実装がトリッキー。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int chk(int a,int b,int c,int d){
	if(a>c||b>d)return 0;
	printf("? %d %d %d %d\n",a,b,c,d);
	fflush(stdout);
	int ret;scanf("%d",&ret);
	return ret;
}
int val[4][2];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<4;i++){
		for(int j=0;j<2;j++){
			int left=0;
			int right=a+1;
			while(left+1<right){
				int M=(left+right)/2;
				int T,B,L,R;
				if(i==0){
					T=1;B=M;L=1;R=a;
				}else if(i==1){
					T=M;B=a;L=1;R=a;
				}else if(i==2){
					T=1;B=a;L=1;R=M;
				}else{
					T=1;B=a;L=M;R=a;
				}
				int val=chk(T,L,B,R);
				if(val>j){
					if(i%2==0){
						right=M;
					}else{
						left=M;
					}
				}else{
					if(i%2==0){
						left=M;
					}else right=M;
				}
			}
			if(i%2==0){
				val[i][j]=right;
			}else val[i][j]=left;
		}
	}
	for(int i=0;i<8;i++){
		if(chk(val[1][0],val[3][i/4],val[0][i%4/2],val[2][i%2])&&chk(val[1][1],val[3][!(i/4)],val[0][!(i%4/2)],val[2][!(i%2)])){
			printf("! %d %d %d %d %d %d %d %d\n",val[1][0],val[3][i/4],val[0][i%4/2],val[2][i%2],val[1][1],val[3][!(i/4)],val[0][!(i%4/2)],val[2][!(i%2)]);fflush(stdout);
			return 0;
		}
	}
}

C:
何度同じ問題が出れば気が済むんだ...

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[3100];
long long dp[3100][3100];
int z[3100];
long long ABS(long long a){
	return max(a,-a);
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",b+i);
	for(int i=0;i<a;i++)b[i]-=i;
	for(int i=0;i<a;i++)z[i]=b[i];
		std::sort(z,z+a);
	for(int i=0;i<3100;i++)for(int j=0;j<3100;j++)dp[i][j]=inf;
	dp[0][0]=0;
	for(int i=1;i<=a;i++){
		long long tmp=inf;
		for(int j=0;j<a;j++){
			tmp=min(tmp,dp[i-1][j]);
			dp[i][j]=tmp+ABS(b[i-1]-z[j]);
		}
	}
	long long ret=inf;
	for(int i=0;i<a;i++)ret=min(ret,dp[a][i]);
	printf("%I64d\n",ret);
}

D:
そういや最大長方形忘れてたなと思ってググった。
クエリの中で二分探索をすると、答えがk以上かどうか判断するのは、長方形内の値の最大値がわかれば容易。
計算量が中途半端にきつく、そのままsegtreeとかにしてしまうと落ちる。1Dでも2Dでもいいのでsparse tableにしておけば、オーダーがわずかに落ちて間に合う。(いかにも強引に通してしまった別解のような解法だが、実際解説にはこれが書かれています......)

スパソを貼ったらポインタの代入がわからないので適当に配列に書き換えた。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;

int segtree[2048][11000];
void buildRMQ(int *a, int n,int to) {
  int logn = 1;
  for (int k = 1; k < n; k *= 2) ++logn;
  int *r = new int[n * logn];
  int *b = r; copy(a, a+n, b);
  for (int k = 1; k < n; k *= 2) {
    copy(b, b+n, b+n); b += n;
    for(int i=0;i< n-k;i++) b[i] = min(b[i], b[i+k]);
  }
for(int j=0;j<n*logn;j++)segtree[to][j]=r[j];
}
int minimum(int x, int y, int *rmq, int n) {
  int z = y - x, k = 0, e = 1, s; // y - x >= e = 2^k なる最大 k
  s = ( (z & 0xffff0000) != 0 ) << 4; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x0000ff00) != 0 ) << 3; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x000000f0) != 0 ) << 2; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x0000000c) != 0 ) << 1; z >>= s; e <<= s; k |= s;
  s = ( (z & 0x00000002) != 0 ) << 0; z >>= s; e <<= s; k |= s;
  return min( rmq[x+n*k], rmq[y+n*k-e+1] );
}
int dp[1010][1010];
int f[2048][1100];
int c[1010][1010];
int L,R;
int m;
int query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return 0;
	if(c<=a&&b<=d){
	//	printf("%d %d %d %d\n",a,b,L,R);fflush(stdout);
		int ret=minimum(L,R,segtree[e],m);
		return ret;
	}
	return min(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	m=b;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++)scanf("%d",&c[i][j]);
	}
	for(int i=0;i<a;i++)for(int j=0;j<b;j++){
		if(!c[i][j])continue;
		int tmp=mod;
		if(i==0||j==0)tmp=0;
		else tmp=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
		dp[i][j]=tmp+1;
	}

	for(int i=0;i<a;i++)for(int j=0;j<b;j++)
		f[i+1024][j]=-dp[i][j];
	for(int i=2047;i>0;i--){
		for(int j=0;j<b;j++){
			f[i/2][j]=min(f[i/2][j],f[i][j]);
		}
		buildRMQ(f[i],b,i);
	//	segtree[i]=buildRMQ(f[i],b);
	}
	int T;scanf("%d",&T);
	while(T--){
		int p,q,r,s;
		scanf("%d%d%d%d",&p,&q,&r,&s);
		p--;q--;r--;s--;
		int left=0;
		int right=min(r-p+1,s-q+1)+1;
		while(left+1<right){
			int M=(left+right)/2;
			int t1=p+M-1;
			int t2=q+M-1;
			R=s;L=t2;
			//printf("%d %d\n",l,r);
			if(query(0,1023,t1,r,1)<=-M){
				left=M;
			}else{
				right=M;
			}
		}
		printf("%d\n",left);
	}
}

Codeforces Round #372 (Div. 1)

単純に2時間コンテストとは思えないほど難しい。

A B C D E Place
00:08 00:44 - - - 56th

A:
(i+1)^2(i+2)^2にしてからsqrtを使う。(i+1)^2(i+2)^2はlong longに入らないが、あらかじめ(i+1)で割っておけば対処可能。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
long long pv[110000];
long long ret[110000];
int main(){
	int a;scanf("%d",&a);
	pv[0]=2;
	for(int i=1;i<a;i++){
		pv[i]=(long long)i*(i+1);
	}
	for(int i=0;i<a;i++){
		long long t=(long long)(i+1)*(i+2);
		long long s=t*(i+2);
		ret[i]=s-pv[i]/(i+1);
	}
	for(int i=0;i<a;i++)printf("%I64d\n",ret[i]);
}

B:
ふだんCに置いてあるような難度のB。逆からコストの決まった辺だけで最短距離を求めておいて、L未満にならないような最小のコストをつけてたどっていく。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
vector<pair<int,int> > g[1100];
long long ijk[2][1100];
int v[2][1100];
int main(){
	int a,b,c,d,e;
	scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
	for(int i=0;i<b;i++){
		int p,q,r;scanf("%d%d%d",&p,&q,&r);
		g[p].push_back(make_pair(q,r));
		g[q].push_back(make_pair(p,r));
	}
	for(int i=0;i<2;i++)for(int j=0;j<a;j++)ijk[i][j]=inf;
	priority_queue<pair<long long,int> > Q;
	Q.push(make_pair(0,d));
	ijk[0][d]=0;
	while(Q.size()){
		long long cost=-Q.top().first;
		int at=Q.top().second;Q.pop();
		if(v[0][at])continue;
		v[0][at]=1;
		for(int i=0;i<g[at].size();i++){
			int to=g[at][i].first;
			if(g[at][i].second==0)continue;
			long long toc=cost+g[at][i].second;
			if(v[0][to]||ijk[0][to]<=toc)continue;
			ijk[0][to]=toc;
			Q.push(make_pair(-toc,to));
		}
	}
	if(ijk[0][e]<c){
		printf("NO\n");return 0;
	}
	Q.push(make_pair(0,e));
	ijk[1][e]=0;
	map<pair<int,int>,long long>M;
	while(Q.size()){
		long long cost=-Q.top().first;
		int at=Q.top().second;Q.pop();
		if(v[1][at])continue;
		v[1][at]=1;
		for(int i=0;i<g[at].size();i++){
			int to=g[at][i].first;
			long long toc=cost+g[at][i].second;
			if(g[at][i].second==0){
				if(M.count(make_pair(min(at,to),max(at,to))))toc=cost+M[make_pair(min(at,to),max(at,to))];
				else{
					if(cost+1+ijk[0][to]>=c){
						toc=cost+1;
						M[make_pair(min(at,to),max(at,to))]=1;
					}else{
						toc=(c-ijk[0][to]);
						M[make_pair(min(at,to),max(at,to))]=c-cost-ijk[0][to];
					}
				}
			}
			if(v[1][to]||ijk[1][to]<=toc)continue;
			ijk[1][to]=toc;
			Q.push(make_pair(-toc,to));
		}
	}
	if(ijk[1][d]>c){
		printf("NO\n");return 0;
	}
	printf("YES\n");
	for(int i=0;i<a;i++)for(int j=0;j<g[i].size();j++){
		if(i>g[i][j].first)continue;
		if(g[i][j].second)printf("%d %d %d\n",i,g[i][j].first,g[i][j].second);
		else printf("%d %d %I64d\n",i,g[i][j].first,M[make_pair(i,g[i][j].first)]);
	}
}

C:
あからさまな重心分解に加え重心分解の中身を線形並みの速度にするのも難しそうなのでスルーした。また今度。

D:

田^^^8888_______________
 田^^^8888____________|
  田^^^8888__________|
   田^^^8888________|
    田^^^8888______|

みたいなのをつなげる。それぞれの田で6倍に増えて、隣の8をうまく使うと0~5倍にできるので、6進数で表記するのに対応する。
6^24>10^18なのでぎりぎり収まる。ただし右下の8を置くスペースだけは足りなくなるので、強引に押し込む。

こういう問題はそもそもサンプルがあってるのかすらわからない上デバッグしようにもどこから手をつけたらいいのかわからないので、大変困ります。良い解決方法はあるのでしょうか。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int y[60][60];
int t[60][60];
int main(){
	long long a;
	scanf("%I64d",&a);
	for(int i=0;i<23;i++){
		t[i*2+2][i*2]=t[i*2+2][i*2+1]=1;
		y[i*2+1][i*2+2]=1;
		int f=a%6;
	//	printf("%d",f);
		y[i*2][i*2+2+f]=1;
	//	if(i==22)break;
		for(int j=0;j<7;j++){
			if(i*2+3+j<49)t[i*2+1][i*2+3+j]=1;
		}
		if(i==22){
			if(f==4){
				y[i*2][i*2+2+2]=1;
				t[i*2+1][48]=0;
			}else if(f==5){
				t[i*2+1][48]=0;
			}
		}
		y[i*2+1][i*2+10]=1;
		y[i*2+2][i*2+10]=1;
		a/=6;
	}
	//printf("%d\n",(int)a);
	if(!a)y[46][46]=1;
	//printf("\n");
	printf("47 50\n");
	vector<pair<pair<int,int>,pair<int,int> > >ans;
	for(int i=0;i<60;i++)for(int j=0;j<60;j++){
		if(i+1<47&&j<50&&t[i][j])ans.push_back(make_pair(make_pair(i+1,j+1),make_pair(i+2,j+1)));
		if(i<47&&j+1<50&&y[i][j])ans.push_back(make_pair(make_pair(i+1,j+1),make_pair(i+1,j+2)));
		
	}
	printf("%d\n",(int)(ans.size()));
	for(int i=0;i<ans.size();i++){
		printf("%d %d %d %d\n",ans[i].first.first,ans[i].first.second,ans[i].second.first,ans[i].second.second);
	}
}

Codeforces Round #373 (Div. 1)

紫コーダーはDiv1のwriterやるのやめてほしい。

A B C D E Place
00:13 削除*1 01:02 -4 - 42th

A:
一番左に出てきた5を四捨五入していく。ひどい実装問題。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[210000];
char str[210000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	scanf("%s",in);
	int ind=0;
	int sz=0;
	for(int i=0;i<a;i++){
		if(in[i]=='.')ind=i;
		else str[sz++]=in[i];
	}
	int one=0;
	for(int i=0;i<sz;i++){

		if(i>=ind&&str[i]>='5'&&str[i]<='9'){
			int at=i;
			while(b--){
				if(at<ind)break;
				if(str[at]>='5'&&str[at]<='9'){
					if(at==0){
						one++;
					}else{
						str[at-1]++;
						int t=at-1;
						while(str[t]>'9'){
							str[t]-=10;
							if(t==0){
								one=1;break;
							}
							else str[t-1]++;
							t--;
						}
					}
				}else break;
				sz=at;
				at--;
			}
			break;
		}
	}
	
	while(sz>ind){
		if(str[sz-1]=='0')sz--;
		else break;
	}
	if(one)printf("1");
	for(int i=0;i<sz;i++){
		if(i==ind)printf(".");
		printf("%c",str[i]);
		
	}printf("\n");
}

B:
(^_^;)

C:
例の区間加算と区間和のsegtreeで行列やベクトルで値を持つ。こんな実装をする前に行列やベクトルのライブラリを用意すべきである。それにしても全く面白くない問題。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
struct mat{
	long long t[2][2];
	mat(){t[0][0]=t[0][1]=t[1][0]=t[1][1]=0;}
};

mat seg1[262144];
bool flag[262144];
long long seg2[262144][2];
int p[110000];
mat tmp;
mat I;
mat F(int a){
	mat ret;
	mat val;
	ret.t[0][0]=ret.t[1][1]=1;
	val.t[0][0]=val.t[0][1]=val.t[1][0]=1;
	while(a){
		if(a%2){
			for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
			for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+ret.t[i][k]*val.t[k][j])%mod;
			for(int i=0;i<2;i++)for(int j=0;j<2;j++)ret.t[i][j]=tmp.t[i][j];
		}
		a/=2;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+val.t[i][k]*val.t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)val.t[i][j]=tmp.t[i][j];
	}
	return ret;
}
long long t2[2];
void add(int a,int b,int c,int d,int e,mat f){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		flag[e]=true;
		t2[0]=seg2[e][0]*f.t[0][0]+seg2[e][1]*f.t[0][1];
		t2[1]=seg2[e][0]*f.t[1][0]+seg2[e][1]*f.t[1][1];
		seg2[e][0]=t2[0]%mod;
		seg2[e][1]=t2[1]%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+f.t[i][k]*seg1[e].t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)seg1[e].t[i][j]=tmp.t[i][j];
		return;
	}
	if(flag[e]){
		flag[e*2]=flag[e*2+1]=true;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+seg1[e].t[i][k]*seg1[e*2].t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)seg1[e*2].t[i][j]=tmp.t[i][j];
		t2[0]=seg2[e*2][0]*seg1[e].t[0][0]+seg2[e*2][1]*seg1[e].t[0][1];
		t2[1]=seg2[e*2][0]*seg1[e].t[1][0]+seg2[e*2][1]*seg1[e].t[1][1];
		seg2[e*2][0]=t2[0]%mod;
		seg2[e*2][1]=t2[1]%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+seg1[e].t[i][k]*seg1[e*2+1].t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)seg1[e*2+1].t[i][j]=tmp.t[i][j];
		t2[0]=seg2[e*2+1][0]*seg1[e].t[0][0]+seg2[e*2+1][1]*seg1[e].t[0][1];
		t2[1]=seg2[e*2+1][0]*seg1[e].t[1][0]+seg2[e*2+1][1]*seg1[e].t[1][1];
		seg2[e*2+1][0]=t2[0]%mod;
		seg2[e*2+1][1]=t2[1]%mod;
		flag[e]=false;
		seg1[e]=I;
	}
	add(a,(a+b)/2,c,d,e*2,f);
	add((a+b)/2+1,b,c,d,e*2+1,f);
	seg2[e][0]=(seg2[e*2][0]+seg2[e*2+1][0])%mod;
	seg2[e][1]=(seg2[e*2][1]+seg2[e*2+1][1])%mod;
	
}
long long calc(int a,int b,int c,int d,int e){
	if(d<a||b<c)return 0;
	if(c<=a&&b<=d){
	//	return (seg2[e][0]*seg1[e].t[0][0]+seg2[e][1]*seg1[e].t[0][1])%mod;
		return seg2[e][0];
	}
	if(flag[e]){
		flag[e*2]=flag[e*2+1]=true;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+seg1[e].t[i][k]*seg1[e*2].t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)seg1[e*2].t[i][j]=tmp.t[i][j];
		t2[0]=seg2[e*2][0]*seg1[e].t[0][0]+seg2[e*2][1]*seg1[e].t[0][1];
		t2[1]=seg2[e*2][0]*seg1[e].t[1][0]+seg2[e*2][1]*seg1[e].t[1][1];
		seg2[e*2][0]=t2[0]%mod;
		seg2[e*2][1]=t2[1]%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=0;
		for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)tmp.t[i][j]=(tmp.t[i][j]+seg1[e].t[i][k]*seg1[e*2+1].t[k][j])%mod;
		for(int i=0;i<2;i++)for(int j=0;j<2;j++)seg1[e*2+1].t[i][j]=tmp.t[i][j];
		t2[0]=seg2[e*2+1][0]*seg1[e].t[0][0]+seg2[e*2+1][1]*seg1[e].t[0][1];
		t2[1]=seg2[e*2+1][0]*seg1[e].t[1][0]+seg2[e*2+1][1]*seg1[e].t[1][1];
		seg2[e*2+1][0]=t2[0]%mod;
		seg2[e*2+1][1]=t2[1]%mod;
		flag[e]=false;
		seg1[e]=I;
	}
	long long ret=(calc(a,(a+b)/2,c,d,e*2)+calc((a+b)/2+1,b,c,d,e*2+1))%mod;

	seg2[e][0]=(seg2[e*2][0]+seg2[e*2+1][0])%mod;
	seg2[e][1]=(seg2[e*2][1]+seg2[e*2+1][1])%mod;
	return ret;
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",p+i);
	}
	for(int i=0;i<a;i++){
		mat tmp=F(p[i]-1);
		seg2[i+131072][0]=tmp.t[0][0];
		seg2[i+131072][1]=tmp.t[1][0];

	}
	for(int i=131071;i>=0;i--){
		seg2[i][0]=(seg2[i*2][0]+seg2[i*2+1][0])%mod;
		seg2[i][1]=(seg2[i*2][1]+seg2[i*2+1][1])%mod;
	}
	for(int i=0;i<262144;i++){
		for(int j=0;j<2;j++)for(int k=0;k<2;k++)seg1[i].t[j][k]=(j==k);
	}
	I.t[0][0]=I.t[1][1]=1;
	while(b--){
		int v;scanf("%d",&v);
		if(v==1){
			int x,y,z;scanf("%d%d%d",&x,&y,&z);x--;y--;
			add(0,131071,x,y,1,F(z));
		}else{
			int x,y;scanf("%d%d",&x,&y);x--;y--;
			printf("%I64d\n",calc(0,131071,x,y,1));
		}
	}
}

D:
重心を求めてから対称性をチェックしつつ非対称な場所を答えに加えるみたいなことをしたけどWAなので、嘘解法なのだろうか。確かにAC人数は少ないけども。

UPD: 解法は合っていた。木の同型性判定をするときは普通のローリングハッシュだと衝突が狙って簡単に起こせるらしく、頂点に変な係数をかけてやったりしないといけないらしい。そのうえジャッジデータには mod 2^k ローリングハッシュを落とすケースもちゃんと存在していた。
今回解いた中で唯一解きがいがあった。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
typedef unsigned long long wolf;
vector<int>g[110000];
wolf key[110000];
int st[110000];
int ra[110000];
wolf ran[]={114514,1919810,364364,4545334};
int n;
const long long M=1000000009;
int dfs(int a,int b){
	int rem=n-1;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		int tmp=dfs(g[a][i],a);
		ra[a]=max(ra[a],tmp);
		rem-=tmp;
		st[a]+=tmp;
	}
	ra[a]=max(ra[a],rem);
	st[a]++;
	return st[a];
}
vector<int>gp;
wolf calc(int a,int b){
	vector<wolf> ch;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		ch.push_back(calc(g[a][i],a));
	}
	std::sort(ch.begin(),ch.end());
	wolf ret=ch.size()+1;
	for(int i=0;i<ch.size();i++){
		ret=(ret*mod+ch[i]*ran[i])%M;
	}
	key[a]=ret;
	return ret;
}
int ans;
void cnt(int a,int b){
	if(g[a].size()<4){
		ans++;
	}
	vector<pair<wolf,int> > v;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		v.push_back(make_pair(key[g[a][i]],g[a][i]));
	}
	std::sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++){
		if(i==0||v[i].first!=v[i-1].first){
			cnt(v[i].second,a);
		}
	}
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a-1;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);g[q].push_back(p);
	}
	n=a;
	dfs(0,-1);
	int mv=999999999;
	//for(int i=0;i<a;i++)printf("%d\n",ra[i]);
	for(int i=0;i<a;i++)mv=min(mv,ra[i]);
	for(int i=0;i<a;i++)if(ra[i]==mv)gp.push_back(i);
	
	if(gp.size()>2){
		printf("yabai\n");while(1);
	}else if(gp.size()==2){
		calc(gp[0],gp[1]);
		calc(gp[1],gp[0]);
		cnt(gp[0],gp[1]);
		if(key[gp[0]]!=key[gp[1]])cnt(gp[1],gp[0]);
	}else{
		calc(gp[0],-1);
		cnt(gp[0],-1);
	}
	printf("%d\n",ans);
}

*1:多分出題ミスで消えたんだと思う。跡形もなく消え去っていた。

2017年の目標

去年は実験的に目標を立てなかったのですが、なんかいまいち何もできませんでした。今年は逆に努力系の目標を立ててみることにします。

競技プログラミング

Div1 Hard のAC数を450以上にする

現在、306。ここ2年間と難しい時代のはまだまだたくさん問題が残っています。

2013年以降の CF の Div1 コンテストは全部 Virtual Participation する

最近始めました。数はあんまり多くないのですが、それ以前は相当に古いので結構現実的だと思います。

OpenCup にちゃんと出る

時間ずらしても参加できるし今年こそはちゃんと出よう

枠の数が正常のオンサイトに出る

2015年はFHC、2016年はDCJに出られました。今年も何か行けるといいですね。

自分でも良問と思える問題を3問以上作る

僕の良問の基準は結構厳しめで、満足できる問題を作れたことがほとんどありません。最近AtCoderのwriterも賑わってることだし、満足できる問題を作りたいです。

TC Highest 2800以上、CF Highest 2800以上、AtCoder Highest 3200以上

最後が一番厳しいと思うけど頑張ります。そもそも参加することも結構難しいですけどね......。

学業

研究して院試して卒業する

当たり前。

非ネイティブとしては申し分ない程度の英単語力と、まあ全般的になんとかやっていける程度の英語力をつける

GREレベルまで分かれば英単語はもういいと思う。SpeakingとWritingがなのをなんとかする。
試験の点数みたいなのを目標にするとクソゲーになるのでしませんが、なんとか海外のPhDに入れてもらえそうなレベルを目指そう。

その他

Youtube 動画...?

なんかもっと面白い題材を見つけたらそういうのをたくさん投稿していきたいな。今は投稿ペースが低い。

市町村系とか

もっと実地に行こう。

DP未難25

DBRもがんばろう。

Intel Code Challenge Elimination Round (Div.1 + Div.2, combined)

これはどうするべきだったのだろうか......

A B C D E F Place
00:03 00:07 00:18 00:31 -5 - 154th

順位が低いのは、本番がHackゲーだったからなので仕方がないが、仮にHackできる環境だったとしても50位くらいだと思う。Eが解けてないのが大問題。

A:
空気。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;

int main(){
	int a;scanf("%d",&a);
	int H,M;
	scanf("%d:%d",&H,&M);
	if(a==24){
		if(H>23){
			H%=10;
		}
	}else{
		if(H==0){
			H=1;
		}else if(H>12){
			if(H%10)H%=10;
			else H=10;
		}
	}
	if(M>=60){
		M%=10;
	}
	printf("%02d:%02d\n",H,M);
}

B:
未だに1行読むのが苦手。入力にスペースを含まないでほしい。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int p[110];
char in[210];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",p+i);
	gets(in);
	for(int i=0;i<a;i++){
		gets(in);
		int cnt=0;
		for(int j=0;in[j];j++){
			if(in[j]=='a'||in[j]=='i'||in[j]=='u'||in[j]=='e'||in[j]=='o'||in[j]=='y'){
				cnt++;
			}
		}
		if(cnt!=p[i]){
			printf("NO\n");return 0;
		}
	}
	printf("YES\n");
}

C:
やるだけ。冗長すぎ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
long long sum[110000];
int p[110000];
int L[110000];
int R[110000];
int q[110000];
long long ans[110000];
int v[110000];
int UF[110000];
vector<int> ct[110000];
long long tot[110000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
long long cur=0;
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;
	if(UF[a]>UF[b])swap(a,b);
	for(int i=0;i<ct[b].size();i++)ct[a].push_back(ct[b][i]);
	tot[a]+=tot[b];
	cur=max(cur,tot[a]);
	ct[b].clear();
	UF[a]+=UF[b];UF[b]=a;
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",p+i);
	for(int i=0;i<a;i++){
		sum[i+1]=sum[i]+p[i];
	}
	for(int i=0;i<a;i++){
		scanf("%d",q+i);q[i]--;
	}
	for(int i=0;i<a;i++){
		UF[i]=-1;
		ct[i].push_back(p[i]);
		tot[i]=p[i];
	}
	for(int i=a-1;i>=0;i--){
		ans[i]=cur;
		v[q[i]]=1;
		cur=max(cur,tot[FIND(q[i])]);
		if(q[i]&&v[q[i]-1]){
			UNION(q[i],q[i]-1);
		}
		if(q[i]<a-1&&v[q[i]+1]){
			UNION(q[i],q[i]+1);
		}
	}
	for(int i=0;i<a;i++)printf("%I64d\n",ans[i]);
}

D:
Greedyにつめていく。上位勢速すぎだった。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[60000];
int ans[60000];
int n;
bool chk(int a){
	set<int>S;
	for(int i=0;i<n;i++){
		int c=b[i];
		bool ok=false;
		while(c){
			if(c<=a&&!S.count(c)){
				ok=true;break;
			}
			c/=2;
		}
		if(!ok)return false;
		S.insert(c);
		ans[i]=c;
	}
	return true;
}
int main(){
	int a;scanf("%d",&a);
	n=a;
	for(int i=0;i<a;i++)scanf("%d",b+i);
	int left=0;
	int right=mod;
	while(left+1<right){
		int M=(left+right)/2;
		if(chk(M)){
			right=M;
		}else left=M;
	}
	chk(right);
	for(int i=0;i<a;i++){
		if(i)printf(" ");printf("%d",ans[i]);
	}
	printf("\n");
}

E:
20回以上変なマスを踏むケースは踏む回数の偶奇で符号を変えて足してまとめてしまえばいいと思うんだけど、うまくいかない。嘘なのだろうか?

F:
こっちをやったほうがよかった説

総評として、こういうセットでやるだけしかできないとやるだけパートが瞬殺すぎるのも相まって本当につまらない

Good Bye 2016

思えば3年前、Good Bye 2013では問題もろくに解けずHackすることだけしてレートを減らしていました。
tozangezan.hatenablog.com

3年後、Codeforcesをやる気になったためついに戻ってきました。

A B C D E F G H Place
00:24 00:10 00:06 00:21 01:09 - - - 44th

Rating: 25102581 (+71)
残念でした。IGMにはなれませんでした。

A:
これはどうでもいいです。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[32];
int vis[410][410];
bool f[410][410][30][8];
int dx[]={1,1,0,-1,-1,-1,0,1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int D=200;
int main(){
	int a,b;scanf("%d%d",&a,&b);
	int t=(240-b)/5;
	for(int i=a;i>=0;i--){
		if(i*(i+1)/2<=t){
			printf("%d\n",i);
			return 0;
		}
	}
}

B:
問題文を読めればどうでもいいです。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[510];
int main(){
	int a;scanf("%d",&a);
	int at=0;
	while(a--){
		int b;scanf("%d%s",&b,in);
		if(in[0]=='S'){
			if(at+b>20000){
				printf("NO\n");return 0;
			}
			at+=b;
		}else if(in[0]=='N'){
			if(at-b<0){
				printf("NO\n");return 0;
			}
			at-=b;
		}else{
			if(at==0||at==20000){
				printf("NO\n");return 0;
			}
		}
	}
	if(at==0)printf("YES\n");else printf("NO\n");
}

C:
直感的に思ったことを書けば通ります。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int p[210000];
int q[210000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d",p+i,q+i);
	}
	int tt=0;
	for(int i=0;i<a;i++)if(q[i]==2)tt++;
	if(!tt){
		printf("Infinity\n");return 0;
	}
	int L=-999999999;
	int R=999999999;
	for(int i=0;i<a;i++){
		if(q[i]==1){
			L=max(L,1900);
		}else{
			R=min(R,1899);
		}
		L+=p[i];
		R+=p[i];
	//	printf("%d %d\n",L,R);
	}
	if(L>R){
		printf("Impossible\n");return 0;
	}
	printf("%d\n",R);
}

D:
適当にBFSしてください。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[32];
int vis[410][410];
bool f[410][410][30][8];
int dx[]={1,1,0,-1,-1,-1,0,1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int D=200;
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
	}
	b[0]--;
	queue<pair<pair<int,int>,pair<int,int> > > Q;
	Q.push(make_pair(make_pair(D,D),make_pair(0,0)));
	f[D][D][0][0]=1;
	while(Q.size()){
		int row=Q.front().first.first;
		int col=Q.front().first.second;
		int ph=Q.front().second.first;
		int dir=Q.front().second.second;Q.pop();
		vis[row][col]=1;
		for(int i=0;i<b[ph];i++){
			row+=dx[dir];
			col+=dy[dir];
			vis[row][col]=1;
		}
		if(ph==a-1)continue;

		if(!f[row][col][ph+1][(dir+1)%8]){
			f[row][col][ph+1][(dir+1)%8]=true;
			Q.push(make_pair(make_pair(row,col),make_pair(ph+1,(dir+1)%8)));
		}
		if(!f[row][col][ph+1][(dir+7)%8]){

			f[row][col][ph+1][(dir+7)%8]=true;
			Q.push(make_pair(make_pair(row,col),make_pair(ph+1,(dir+7)%8)));
		}
	}
	int ret=0;
	for(int i=0;i<410;i++)for(int j=0;j<410;j++)ret+=vis[i][j];
		printf("%d\n",ret);
}

E:
AtCoderでも見た、SegtreeにDPの状態i→jのコストをもっておくやつです。もしかしたらこれをライブラリにしておくと強いかも。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[210000];
struct wolf{
	int t[5][5];
	wolf(){for(int i=0;i<5;i++)for(int j=0;j<5;j++)t[i][j]=-1;}
};
wolf segtree[524288];
wolf zero;
wolf dame;
wolf query(int a,int b,int c,int d,int e){
	if(d<=a||b<=c)return zero;
	if(c<=a&&b<=d){
		//printf("%d %d %d %d %d\n",a,b,c,d,e);

		return segtree[e];
	}
	wolf L=query(a,(a+b)/2,c,d,e*2);
	wolf R=query((a+b)/2,b,c,d,e*2+1);
	//for(int i=0;i<5;i++){
//		for(int j=0;j<5;j++)printf("%d ",R.t[i][j]);printf("\n");
//	}
	wolf ret;
	for(int i=0;i<5;i++)for(int j=i;j<5;j++){
		for(int k=i;k<=j;k++){
			//printf("%d %d %d\n",L.t[i][k],R.t[k][j],ret.t[i][j]);
			if(~L.t[i][k]&&~R.t[k][j]&&(ret.t[i][j]==-1||ret.t[i][j]>L.t[i][k]+R.t[k][j])){

				ret.t[i][j]=L.t[i][k]+R.t[k][j];
			}
		}
	}
	return ret;
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	scanf("%s",in);
	for(int i=0;i<a;i++){
		for(int j=0;j<5;j++)segtree[i+262144].t[j][j]=0;
		if(in[i]=='2'){
			segtree[i+262144].t[0][0]=1;
			segtree[i+262144].t[0][1]=0;
		}else if(in[i]=='0'){
			segtree[i+262144].t[1][1]=1;
			segtree[i+262144].t[1][2]=0;
		}else if(in[i]=='1'){
			segtree[i+262144].t[2][2]=1;
			segtree[i+262144].t[2][3]=0;
		}else if(in[i]=='6'){
			segtree[i+262144].t[3][3]=1;
			segtree[i+262144].t[4][4]=1;
		}else if(in[i]=='7'){
			segtree[i+262144].t[3][3]=1;
			segtree[i+262144].t[3][4]=0;
		}
		
	}
	for(int i=a;i<262144;i++)for(int j=0;j<5;j++)segtree[i+262144].t[j][j]=0;
	for(int i=262143;i>0;i--){
		for(int j=0;j<5;j++)for(int k=j;k<5;k++){
			for(int l=j;l<=k;l++){
				if(segtree[i*2].t[j][l]==-1||segtree[i*2+1].t[l][k]==-1)continue;
				if(~segtree[i].t[j][k])segtree[i].t[j][k]=min(segtree[i].t[j][k],segtree[i*2].t[j][l]+segtree[i*2+1].t[l][k]);
				else segtree[i].t[j][k]=segtree[i*2].t[j][l]+segtree[i*2+1].t[l][k];
			}
		}
	}
	for(int i=0;i<5;i++)zero.t[i][i]=0;
	for(int i=0;i<5;i++)for(int j=0;j<5;j++)dame.t[i][j]=-1;
	while(b--){
		int p,q;scanf("%d%d",&p,&q);p--;
		wolf res=query(0,262144,p,q,1);

		printf("%d\n",res.t[0][4]);
	}
}

F:
解法は単純なのですが、コードに落とすのが大変です。ICPCの参加権がある人は練習にやってみては?

Codeforces Round #380 (Div. 1, Rated, Based on Technocup 2017 - Elimination Round 2)

なぜに6問...充実しすぎて2時間でやるなら5問でも十分だと思えるセット。

A B C D E F Place
00:19 00:28 00:37 01:49 (+2) - - 34th

A:
Aですらいつもより難しい。短すぎるものを除けば一次式になるのでうんたらかんたら

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
pair<int,int> p[210000];
int f[210000];
int g[210000];

int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	int ret=mod;
	for(int i=0;i<a;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		p[i]=make_pair(y,x);
	}
	std::sort(p,p+a);
	for(int i=0;i<b;i++)scanf("%d",f+i);
	f[b]=c;
	std::sort(f,f+b+2);
	for(int i=0;i<b+1;i++){
		g[i]=f[i+1]-f[i];
	}
	std::sort(g,g+b+1);
	b++;
	int at=0;
	long long tn=0;
	long long al=0;
	for(int i=0;i<b;i++)tn+=g[i];
	tn*=3;
	for(int i=0;i<a;i++){
		if(g[b-1]>p[i].first)continue;
		while(at<b&&g[at]*2<=p[i].first){
			tn-=3LL*g[at];
			al+=g[at];
			at++;
		}
		long long cost=al+tn-(long long)(b-at)*p[i].first;

		//printf("%d: %d %I64d %d %d\n",i,at,tn,al,cost);
		if(cost<=d)ret=min(ret,p[i].second);
	}
	if(ret==mod)ret=-1;
	printf("%d\n",ret);
}

B:
左から戦艦の長さごとに漁っていくと残り候補が減っていく。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[210000];
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	scanf("%s",in);
	int rem=0;
	int ren=0;
	for(int i=0;i<a;i++){
		if(in[i]=='0'){
			ren++;
		}else{
			rem+=ren/c;
			ren=0;
		}
	}
	rem+=ren/c;
	vector<int>ret;
	ren=0;
	for(int i=0;i<a;i++){
		if(rem<b)break;
		if(in[i]=='0'){
			ren++;
			if(ren%c==0){
				ret.push_back(i+1);
				rem--;
			}
		}else{
			ren=0;
		}
	}
	printf("%d\n",(int)(ret.size()));
	for(int i=0;i<ret.size();i++){
		if(i)printf(" ");
		printf("%d",ret[i]);
	}printf("\n");
}

C:
nがあるなら1~n-1が全部揃っているので、nを全部試す。他所に0があるとか0のあるべきところに0が入ってないとか、変なケースが多い。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int c[210000];
int d[210000];
int z[210000];
int sum[210000];
int main(){
	int a,b;scanf("%d%d",&a,&b);b--;
	if(a==1){
		printf("0\n");return 0;
	}
	for(int i=0;i<a;i++)scanf("%d",c+i);
	int ba=0;
	int f=0;
	for(int i=0;i<a;i++){
		if(b==i&&c[i]){
			ba++;
		}else if(b!=i&&c[i]==0){
			//ba++;
			f++;
		}else{
			d[c[i]]++;
		}
	}
	int ret=88888888;
	for(int i=1;i<a;i++){
		z[i]=z[i-1];
		if(!d[i])z[i]++;
	}
	for(int i=a-1;i>0;i--){
		sum[i]=sum[i+1]+d[i];
	}
	for(int i=1;i<a;i++){
		int t=f+sum[i+1];
		int tot=max(t,z[i]);
		ret=min(ret,ba+tot);
	}
	printf("%d\n",ret);
}

D:
実は状態数が少ない(取ったカードの枚数の差がk以下、kもO(N^0.5))ので普通にDPすればよい。
遷移先とかを間違えていて本番だったら落ちてた。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[4100];
int sum[4100];
int dp[4100][200][100];
int K=95;
int ABS(int a){
	return max(a,-a);
}
int N;
int calc(int a,int b,int c){
	//if(a<0||b+K<0||c<0)printf("dame\n");
	///if(a>=4100||b+K>=200||c>=100)printf("dame\n");
	
	if(dp[a][b+K][c]!=-mod)return dp[a][b+K][c];
	int s=a;int t=a+b;
	int L=a;
	int R=N-a-b;
	if(R-L<c){
		return dp[s][t-s+K][c]=0;
	}
	int ret=-mod;
	if(s<=t){
		if(L+c+1<=R){
			ret=max(ret,-calc(s+c+1,t-(s+c+1),c+1)+sum[L+c+1]-sum[L]);
		}
		ret=max(ret,-calc(s+c,t-s-c,c)+sum[L+c]-sum[L]);
	}else{
		if(L+c+1<=R){
			ret=max(ret,-calc(s,t+c+1-s,c+1)+sum[R]-sum[R-c-1]);
		}
		ret=max(ret,-calc(s,t+c-s,c)+sum[R]-sum[R-c]);
	}
	//if(s<0||t-s+K<0||c<0)printf("%d %d %d: %d\n",s,t-s+K,c,ret);
	return dp[s][t-s+K][c]=ret;
}
int main(){
	int a;scanf("%d",&a);
	N=a;
	for(int i=0;i<a;i++)scanf("%d",b+i);
	for(int i=0;i<a;i++)sum[i+1]=sum[i]+b[i];
	for(int i=0;i<4100;i++)for(int j=0;j<200;j++)for(int k=0;k<100;k++)
		dp[i][j][k]=-mod;
	printf("%d\n",calc(0,0,1));
}

E:
フローでできることの範疇を超えている気がする。また今度。