Hatena::Grouptopcoder

Hiro180の日記

|

2015-12-31

2015年を振り返る(2回目) 20:08

2015年の目標( http://topcoder.g.hatena.ne.jp/Hiro180/20150101/1420076631 )の結果発表(?)です。

ちなみに(2回目)とついてるのは http://hiro180.hatenablog.com/entry/2015/12/30/122054 を書いたからです。良かったらそちらもどうぞ。


TopCoder Algorithmの最高レート 2431 (3/10) 最後に出たのが5/8らしくアクティブじゃなくなってた()


Codeforcesの最高レート 2371 (0/5) こちらも最後に出たのが6/6ですね...


JOI本選 & JOI春 &APIO (1/25) つらい(つらい)


JMO本選 (9/19)銅賞とれたしIMO行けなかったのは残念だけどまぁ良かった。


音ゲー (0/11)copulaになって7段になった。(昔は9段)


iPad模試 (8/10) 総合3位だったし高2内1位だし言うことなし。


東大模試 (6/6) 全項目で唯一の満点。理三A判とれて良かった。


実テ (0/3) このテストダメ。


TOEIC (0/5) そもそも1回も受けてないし。


遅刻 (3/5) 年間16回だった。(健全)


計 30/100


<総括>

あっちの記事に書くこと全部書いたので何も言うことがない。まぁ色々あって楽しい1年だった。

30点って評価を下すほど悪い1年では決してなかったので目標の作りかたが悪かったですね...

2016年はまともな目標をつくることを目標にします。(大嘘)

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に行ってきた身なので春合宿は本気でやりたいと思います。

2015-01-01

2015年の目標 10:43

2014年のkagamizさんや今年のtozanさんの形式をお借りすることにします〜


(得点は累積和です)


<競プロ>


TopCoder Algorithmの最高レート


2300~2399 : 1点

2400~2499 : 2点

2500~2599 : 3点

2600~ : 4点


Codeforcesの最高レート


2500~2599 1点

2600~ 4点


JOI本選


銅: 1点

銀: 3点

金: 5点


JOI


代表になる: 10点


APIO


銅: 1点

銀: 2点

金: 3点


<JMO>


予選通過: 1点

本選通過: 8点

IMO代表: 10点


<音ゲー>


SP10段: 1点

SP皆伝: 11点


<勉強系>


iPad模試: Max(11-決勝の順位,0)点


東大模試: 理一A判を出す: 1点 理三A判を出す: 5点


実テ: Max(4-最高順位,0)点


TOEIC: Min(5, 5* [ (最高点-730) / 120 ] )点


<遅刻>


Max(5-[ 5 * (2015年の遅刻数) / 35 ],0)点



(一番比重がでかいのがSP皆伝なのは秘密)

2014-12-31

2014年を振り返る 19:55

http://topcoder.g.hatena.ne.jp/Hiro180/20131231/1388502726 に対する結果発表です

<絶対達成すること>


・絶対にIOI2014に行く。日本代表になる。(迫真)


 行けてしまった。本当に行けると思ってたかと言われるとそんなことは決してないんだけど、ひたすらIOIに行くと宣言していたら行けた。

 (もう何回も言ってる気がするけど、) 春合宿の2日目で、執念の枝刈りのお陰で残り15秒で65点増やすことが出来て、(競技時間は5時間)

 そのおかげで7位から5位に上がり、日本代表は4人だから初めは落とされたんだけど、後日IMO代表とIOI代表が被ったことで

 2人辞退し6位までが繰り上がった、という格好だったので「理屈では説明できない力」の存在を強く感じた。


・全国統一高校生テストで10位以内に入る。


 18位でした。まぁこれだけ見るとダメっぽいけど「10位以内に入る」というのは「ハーバードの資格を得る」という意味なので

 ハーバードの面接の資格がある13人に入れたのでOKだと思います。(面接こわい><><)


<達成すべきこと>


・PCKで金ですぽよする。


 2位だったしギリギリ許容範囲だと思う。1位をとれるチャンスはあったと思うので、7番が解けなかったのがめっちゃ悔しい.......来年は頑張りたい


TopCoder, CodeforcesでRedcoderになる。


 最後のほうは「今日も戦略的撤退...あたしのいくじなし〜><」を実施してたので若干逃げた感あるけど

 TCは2288、CFは2284なので両方赤で年を越すことができてよかった。


・オンサイトのプログラミングコンテストに出る(JOIIOI以外)


 天プロがやばかった。予選Aでも予選Bでも本選出場権を得られる順位がとれたし、中高生で唯一本選にいけたし最高の思い出になった。

 本選は13位だったけど、ガチプロの方々の気迫を身近に感じられて凄く恵まれた機会だったと思います。

 (CodeFormula...?そんなのもあったっけ...?)


<達成できればうれしい>


・弐寺初段とる


 @去年の自分 いくら3級に受からないからと言ってこの目標は低すぎると思います!!! (想像以上に音ゲー沼にはまってしまったってことだろ!いい加減にしろ!!)

 はい。昨日9段取りました! やったぜ。(初段はゴールデンウィークあたりに取った)


・学校でそこそこの成績(10位くらい)をとる


 実テも定期考査も最下位でした。まぁ学校のテストとかどうでもいいので...


・まじめに生きる

 

 遅刻は減ったけど真面目に生きてはないと思う。(反省)


・人権を得る


 大分人権を生やせた気がする。(大勝利)


総括: 2014年はいい1年だった。2015年はもっといい1年になるように頑張りたいです (保育園生並の感想)

2014-09-05

天プロ2013本選D 18:34

あのあと1hくらい考えてわかった。

何も考えないとN^D通りあって、

そのなかに制約を満たさないものがあるからそれを取り除く。

少なくともi種類の筋肉は制約を満たさず、それらのトレーニングでj日間を費やしているような場合の数を考えると

(i種類の筋肉を選び、そこにj日間費やすようなトレーニングの仕方) * (N-i)^(D-j)

であることがわかる。あとは包除原理により,この値をi%2==1なら引き、i%2==0なら足せばよい。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
ll dp[35][35][1000];
int n,d;
int a[35];
ll c[1005][35];
long long modpow(long long x,long long n)
{
	long long res=1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll C(int a,int b)
{
	ll res = 1;
	for(int i=a;i>a-b;i++) res = (res*1LL*i)%mod;
	for(int i=1;i<=b;i++) res = (res*modpow(i,mod-2))%mod;
	return res;
}
int main()
{
	cin >> n >> d;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	}
	dp[0][0][0] = 1;
	for(int k=0;k<1000;k++) for(int x=0;x<30;x++) c[k][x] = C(d-k,x);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			for(int k=0;k<1000;k++)
			{
				if(dp[i][j][k] == 0) continue;
				dp[i+1][j][k] = (dp[i+1][j][k] + dp[i][j][k])%mod;
				for(int x=0;x<a[i+1];x++)
				{
					dp[i+1][j+1][k+x] = (dp[i+1][j+1][k+x] + dp[i][j][k] * c[k][x])%mod;
				}
			}
		}
	}
	ll res = modpow(1LL*n,1LL*d);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=min(d,999);j++)
		{
			if(dp[n][i][j] == 0) continue;
			if(i%2 == 1)
			{
				res = (res+mod-(dp[n][i][j]*modpow(1LL*(n-i),1LL*(d-j))%mod))%mod;
			}
			else
			{
				res = (res+(dp[n][i][j]*modpow(1LL*(n-i),1LL*(d-j))%mod))%mod;
			}
		}
	}
	cout << res << endl;
}

天プロ2013本選 17:14

撃沈

A:

bitDPやる

B:

面白かった。

考察するとリフルシャッフルの回数さえ同じならば、数の並びかたは同じ(いくつかずらしただけ)であり、

またk枚のカットをするとk*2^(カット後のリフルシャッフルの数)分ずれることがわかる。

これより、100点解法ではリフルシャッフルの回数を決めうちし、mod 2*n+1でk個分ずらすために必要な数を計算してdijkstraすると解ける。200点解法はDPが必要になる(?)はずで、TLEすることが明らかなオーダーになり絶望

C:

知らない

D:

数え上げが得意なほうだとかいうのは幻想でした

E:

見てない

40+100+0+0+0 = 140

別に(puke)(handshake)なセットではないけどどうしようもなかった...

|