Hatena::Grouptopcoder

Hiro180の日記

 | 

2015-02-09

JOI 2015本選 参加記 21:35

(2/4) ノロウイルスに感染したと思わしき症状が現れる

(2/6) 参加が危ぶまれたが、何とか受けさせてもらうことが出来た。

(2/7) 体調が悪いのでプラクティスのみ参加して一旦ホテルに帰る。

(2/8) 朝オリセンに行く。各位にあって少し話す。

〜競技〜

1. 易化しすぎでしょって思ったけどそれはこれが知識ゲーだからなのであったの巻

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <queue>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
typedef long long ll;
int n,m;
int a[100005],r[100005];
int x[100005],y[100005],z[100005];
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&x[i],&y[i],&z[i]);
	}
	for(int i=1;i<m;i++)
	{
		int x = a[i-1];
		int y = a[i];
		if(x>y) swap(x,y);
		y--;
		r[x]++;
		r[y+1]--;
	}
	for(int i=2;i<n;i++)
	{
		r[i] += r[i-1];
	}
	ll res = 0;
	for(int i=1;i<n;i++)
	{
		ll s = 1LL*r[i]*x[i];
		ll t = 1LL*z[i]+1LL*r[i]*y[i];
		res += min(s,t);
	}
	printf("%lld\n",res);
}

2. あ^〜区間DPやるだけなんじゃ^〜O(N^3)^〜

>>N <= 2000 <<

どう見ても状態数O(N^2)、遷移O(1)なのに勘違いして時間を食ってしまった。先に3に行く。


3. さすがに人を舐め過ぎなんだよなぁ....

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define INF 10000000000000LL
typedef long long ll;
typedef pair<int,ll> P;
typedef pair<pair<int,int>,ll> PP;
typedef pair<ll,int> Q;
int n,m;
vector<P>edge[100005];
vector<PP>a;
map<ll,ll>ma;
ll res,sum,c;
ll d[100005];
int main()
{
	scanf("%d%d%lld",&n,&m,&c);
	for(int i=0;i<m;i++)
	{
		int x,y;ll z;
		scanf("%d%d%lld",&x,&y,&z);
		edge[x].pb(mp(y,z));
		edge[y].pb(mp(x,z));
		a.pb(mp(mp(x,y),z));
		sum += z;
	}
	priority_queue<Q,vector<Q>,greater<Q> > que;
	fill(d,d+100005,INF);
	d[1] = 0; que.push(mp(0,1));
	while(!que.empty())
	{
		Q q = que.top(); que.pop();
		if(q.fi != d[q.sc]) continue;
		for(int i=0;i<edge[q.sc].size();i++)
		{
			int v = edge[q.sc][i].fi;
			ll ad = edge[q.sc][i].sc;
			if(d[v] > q.fi+ad)
			{
				d[v] = q.fi+ad;
				que.push(mp(d[v],v));
			}
		}
	}
	for(int i=0;i<a.size();i++)
	{
		int x = a[i].fi.fi;
		int y = a[i].fi.sc;
		ll ad = a[i].sc;
		ll ke = max(d[x],d[y]);
		ma[ke] += ad;
		//cout << ke << " " << ad << " " << x << " " << y << endl;
	}
	res = sum;
	for(map<ll,ll>::iterator it = ma.begin();it != ma.end();++it)
	{
		sum -= it->sc;
		res = min(res,sum + c*it->fi);
	}
	printf("%lld\n",res);
}

2(再). 戻って見るとクソであることに気づく。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define INF 10000000000000LL
typedef long long ll;
typedef pair<int,int> P;
int n;
ll a[2005];
ll dp[2005][2005];
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%lld",&a[i]);
	queue<P>que;
	for(int i=0;i<2005;i++) for(int j=0;j<2005;j++) dp[i][j] = -INF;
	for(int i=0;i<n;i++)
	{
		dp[i][i] = a[i];
		que.push(mp(i,i));
	}
	ll res = 0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			int lb = j;
			int ub = (j+i)%n;
			res = max(res,dp[lb][ub]);
			if(i==n-1) continue;
			if(i%2==0)
			{
				if(a[(lb+n-1)%n] > a[(ub+1)%n])
				{
					dp[(lb+n-1)%n][ub] = max(dp[(lb+n-1)%n][ub],dp[lb][ub]);
				}
				else
				{
					dp[lb][(ub+1)%n] = max(dp[lb][(ub+1)%n],dp[lb][ub]);
				}
			}
			else
			{
				dp[(lb+n-1)%n][ub] = max(dp[(lb+n-1)%n][ub],dp[lb][ub]+a[(lb+n-1)%n]);
				dp[lb][(ub+1)%n] = max(dp[lb][(ub+1)%n],dp[lb][ub]+a[(ub+1)%n]);
			}
		}
	}
	printf("%lld\n",res);
}

4.

見て真面目に考えるが解けず。1年前からなんも成長してねぇな^〜となって絶望。

さすがににぶたんは考えるので24点は自明だなぁと思って通す。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define INF 10000000000000LL
typedef long long ll;

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	if(n > 20) return 0;
	int x[20],y[20];
	bool q[20]={};
	vector<int>v;
	for(int i=0;i<m;i++)
	{
		cin >> x[i] >> y[i];
		v.pb(x[i]); q[y[i]] = true;
	}
	vector<int>s;
	for(int i=1;i<=n;i++) if(!q[i]) s.pb(i);
	for(int i=m;i<n;i++)
	{
		cin >> x[i]; v.pb(x[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	
	for(int i=v.size()-1;i>=0;i--)
	{
		int bit = 0;
		for(int j=m;j<n;j++) if(x[j] >= v[i]) bit++;
		int a[50];
		for(int j=0;j<m;j++) a[y[j]] = (x[j] >= v[i]);
		for(int j=0;j<(1<<(n-m));j++)
		{
			if(__builtin_popcount(j) != bit) continue;
			for(int k=0;k<s.size();k++) a[s[k]] = (((j>>k)&1));
			int lb=1,ub=n;
			while(ub-lb>1)
			{
				int d = a[lb]+a[lb+1]+a[lb+2];
				if(d>=2) a[ub+1] = 1;
				else a[ub+1] = 0;
				lb+=3; ub++;
			}
			if(a[ub] == 1)
			{
				printf("%d\n",v[i]); return 0;
			}
		}
	}
}

5. どうみてもこれクソムズだよなぁ...(この判断が致命傷であった) 20点解法だけ書こう.....ということで実装する。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define INF 10000000000000LL
typedef long long ll;
typedef pair<int,int> P;
int n,m,l,p;
P za[100005];
int rui[4005][4005],s[4005][4005];
ll res;
ll zan[12];
int rec(int a,int b,int c,int d)
{
	return rui[b][d] - rui[a-1][d] - rui[b][c-1] + rui[a-1][c-1];
}
int cnt(int a,int b,int c,int d)
{
	return rec(a,b,c,d)-rec(a+1,b-1,c+1,d-1);
}
void solve()
{
	int res = 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=l;k<=min(n+1-i,m+1-j);k++)
			{
				if(!cnt(i,i+k-1,j,j+k-1)) res++;
			}
		}
	}
	cout << res << endl;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&l,&p);
	for(int i=0;i<p;i++)
	{
		scanf("%d%d",&za[i].fi,&za[i].sc);
		s[za[i].fi][za[i].sc] = 1;
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) rui[i][j] = rui[i-1][j]+rui[i][j-1]-rui[i-1][j-1]+s[i][j];
	if(p>10 && n>500) return 0;
	else if(n <= 500) {solve(); return 0;}
	
	for(int i=l;i<=min(n,m);i++)
	{
		res += 1LL*(n-i+1)*(m-i+1);
	}
	for(int ii=0;ii<p;ii++)
	{
		int x = za[ii].fi;
		int y = za[ii].sc;
		for(int i=1;i<=n;i++)
		{
			for(int j=i+l-1;j<=n;j++)
			{
				if(!(i<=x && x<=j)) continue;
				if(y+i-j < 1) continue;
				int a = cnt(i,j,y+i-j,y);
				zan[a]++;
			}
		}
		for(int i=1;i<=m;i++)
		{
			for(int j=i+l-1;j<=m;j++)
			{
				if(!(i<=y && y<j)) continue;
				if(x+j-i > n) continue;
				int a = cnt(x,x+j-i,i,j);
				zan[a]++;
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=i+l-1;j<=n;j++)
			{
				if(!(i<x && x<=j)) continue;
				if(y+j-i > m) continue;
				int a = cnt(i,j,y,y+j-i);
				zan[a]++;
			}
		}
		for(int i=1;i<=m;i++)
		{
			for(int j=i+l-1;j<=m;j++)
			{
				if(!(i<y && y<j)) continue;
				if(x+i-j < 1) continue;
				int a = cnt(x+i-j,x,i,j);
				zan[a]++;
			}
		}
	}
	for(int i=1;i<=p;i++) res -= (zan[i]/i);
	printf("%lld\n",res);
}

4(再). 何度見てもわからずなので諦める。


5(再). 満点解法を真面目に考えているとクソであることがわかる。この時点で1時間はあったのだが3ヶ月以上引退してる人は書き終わらなかったよ....


終了。100+100+100+24+20 = 344 (おそらく6位) (クソクソ & クソ)


5番が解析が始まると同時に通る。(終了30秒前にはこれが書き上がったと思われるが何故か正しく挙動しなかった...)(実際には最後マイナーチェンジしてたかもしれない)

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
typedef long long ll;
int n,m,lim,p;
bool f[4005][4005];
int le[4005][4005];
int ri[4005][4005];
int d[4005][4005];
int u[4005][4005];
vector<int>seg[8200];
void update(int a,int b)
{
	a+=4095;
	seg[a].pb(b);
}
void all()
{
	for(int i=4094;i>=0;i--)
	{
		if(seg[i*2+1].empty() && seg[i*2+2].empty()) continue;
		else if(seg[i*2+1].empty()) seg[i] = seg[i*2+2];
		else if(seg[i*2+2].empty()) seg[i] = seg[i*2+1];
		else
		{
			seg[i].resize(seg[i*2+1].size()+seg[i*2+2].size());
			merge(seg[i*2+1].begin(),seg[i*2+1].end(),seg[i*2+2].begin(),seg[i*2+2].end(),seg[i].begin());
		}
	}
}
int query(int a,int b,int k,int lb,int ub,int x)
{
	if(ub < a || b < lb) return 0;
	if(a <= lb && ub <= b)
	{
		int z = -1;
		if(!seg[k].empty())
		{
			z = lower_bound(seg[k].begin(),seg[k].end(),x)-seg[k].begin();
			return (seg[k].size()-z);
		}
		else return 0;
	}
	int lk = query(a,b,k*2+1,lb,(lb+ub)/2,x);
	int uk = query(a,b,k*2+2,(lb+ub)/2+1,ub,x);
	return lk+uk;
}
void init()
{
	for(int i=0;i<8200;i++) if(!seg[i].empty()) seg[i].clear();
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&lim,&p);
	for(int i=0;i<p;i++)
	{
		int x,y; scanf("%d%d",&x,&y);
		f[x][y] = true;
	}
	for(int i=1;i<=n;i++)
	{
		int l = 1;
		for(int j=1;j<=m;j++)
		{
			if(f[i][j])
			{
				while(l!=j)
				{
					ri[i][l] = j-l;
					l++;
				}
			}
		}
		while(l<=m)
		{
			ri[i][l] = m-l+1;
			l++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		int l = m;
		for(int j=m;j>=1;j--)
		{
			if(f[i][j])
			{
				while(l!=j)
				{
					le[i][l] = l-j;
					l--;
				}
			}
		}
		while(l>=1)
		{
			le[i][l] = l;
			l--;
		}
	}
	for(int i=1;i<=m;i++)
	{
		int l = 1;
		for(int j=1;j<=n;j++)
		{
			if(f[j][i])
			{
				while(l!=j)
				{
					d[l][i] = j-l;
					l++;
				}
			}
		}
		while(l<=n)
		{
			d[l][i] = n-l+1;
			l++;
		}
	}
	for(int i=1;i<=m;i++)
	{
		int l = n;
		for(int j=n;j>=1;j--)
		{
			if(f[j][i])
			{
				while(l!=j)
				{
					u[l][i] = l-j;
					l--;
				}
			}
		}
		while(l>=1)
		{
			u[l][i] = l;
			l--;
		}
	}

	ll res = 0;
	for(int i=-n+1;i<=0;i++)
	{
		if(min(m-i,n)+i < lim) continue;
		bool uu = 0;
		for(int j=1-i;j<=min(m-i,n);j++)
		{
			if(f[j][i+j]) continue;
			if(min(d[j][i+j],ri[j][i+j]) >= lim) uu = 1;
			update(j-(1-i),min(le[j][i+j],u[j][i+j])-(j-(1-i)));
		}
		if(!uu){ init(); continue;}
		all();
		for(int j=1-i;j<=min(m-i,n);j++)
		{
			if(min(d[j][i+j],ri[j][i+j]) < lim) continue;
			if(f[j][i+j]) continue;
			int k = j-(1-i);
			int h = min(d[j][i+j],ri[j][i+j]);
			res += query(k+lim-1,k+h-1,0,0,4095,-k+1);
			//cout << query(k+lim-1,k+h-1,0,0,4095,-k+1) << " " << j << " " << i+j << endl;
		}
		init();
	}
	for(int i=1;i<=m-1;i++)
	{
		if(min(m-i,n) < lim) continue;
		bool uu = 0;
		for(int j=1;j<=min(m-i,n);j++)
		{
			if(f[j][i+j]) continue;
			if(min(d[j][i+j],ri[j][i+j]) >= lim) uu = 1;
			update(j-1,min(le[j][i+j],u[j][i+j])-(j-1));
		}
		if(!uu){ init(); continue;}
		all();
		for(int j=1;j<=min(m-i,n);j++)
		{
			if(min(d[j][i+j],ri[j][i+j]) < lim) continue;
			if(f[j][i+j]) continue;
			int k = j-1;
			int h = min(d[j][i+j],ri[j][i+j]);
			res += query(k+lim-1,k+h-1,0,0,4095,-k+1);
			//cout << query(k+lim-1,k+h-1,0,0,4095,-k+1) << " " << j << " " << i+j << endl;
		}
		init();
	}
	printf("%lld\n",res);
}

予選も6番ギリで終わらなかったし何か改善しないと春でもやらかしそうで怖い。


本選は完全に最下位でしたが、一応IOIに行ってきた身なので春合宿は本気でやりたいと思います。

 |