Hatena::Grouptopcoder

Hiro180の日記

|

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)なセットではないけどどうしようもなかった...

2014-08-31

2012天プロ本選解いた 22:43

A:

Greedyだなあ...と書くと通る

int main()
{
	vector<ll>vec;
	vec.pb(1); vec.pb(1);
	while(vec[vec.size()-2] + vec[vec.size()-1] <= 1e10)
	{
		vec.pb(vec[vec.size()-2] + vec[vec.size()-1]);
	}
	ll n;
	cin >> n;
	int res = 0;
	while(n > 0)
	{
		int a = upper_bound(vec.begin(),vec.end(),n)-vec.begin();
		n -= vec[a-1];
		res++;
	}
	cout << res << endl;
}

B:

O(N^2)を死ぬ気で改善しただけ。たぶん落とされるべき解法

int n;
int x[10005],y[10005];
P gcd[100][100];
ll tw[10005];
ll th[10005];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&x[i],&y[i]);
	}
	for(int i=1;i<100;i++) for(int j=1;j<100;j++)
	{
		int a = i,b = j;
		gcd[i][j] = mp(a/__gcd(i,j),b/__gcd(i,j));
	}
	for(int i=2;i<=10000;i++)
	{
		tw[i] = 1LL*(i)*(i-1LL)/2LL;
	}
	for(int i=2;i<=10000;i++)
	{
		th[i] = 1LL*(i)*(i-1LL)*(i-2LL)/6LL;
		th[i] %= mod;
	}
	ll t = 0,f = 0;
	
	for(int i=1;i<=n;i++)
	{
		int cnt[100][100][4] = {};
		for(int j=1;j<=n;j++)
		{
			if(i == j) continue;
			int a = x[j]-x[i];
			int b = y[j]-y[i];
			int c = 0;
			if(a < 0)
			{
				c += 2;
				a = -a;
			}
			if(b < 0)
			{
				c += 1;
				b = -b;
			}
			if(a == 0)
			{
				b = 1;
			}
			if(b == 0)
			{
				a = 1;
			}
			if(a && b)
			{
				int cc = a;
				a = gcd[a][b].fi;
				b = gcd[cc][b].sc;
			}
			cnt[a][b][c]++;
			t += cnt[a][b][c]-1;
			f += tw[cnt[a][b][c]-1];
		}
	}
	if(t % 2 == 1) t = ((t+mod)/2)%mod;
	else t = (t/2)%mod;
	if(f % 2 == 1) f = ((f+mod)/2)%mod;
	else f = (f/2)%mod;
	ll res = 1LL*n*(n-1)*(n-2)*(n-3)/24LL - t*(n-3LL) + 3*f;
	res %= mod;
	res = (res+mod)%mod;
	cout << res << endl;
}

C:

気づけばやるだけなんだけど実装が鬼

int dp[105][105][31][155];
int n;
int a[35],b[35],c[35];

int main()
{
	cin >> n;
	for(int i=0;i<n;i++)
	{
		cin >> a[i] >> b[i] >> c[i];
	}
	for(int i=0;i<105;i++)
	{
		for(int j=0;j<105;j++)
		{
			for(int k=0;k<31;k++)
			{
				for(int l=0;l<155;l++)
				{
					dp[i][j][k][l] = INF;
				}
			}
		}
	}
	dp[100][a[0]][0][0] = 0;
	queue<P2>que;
	que.push(mp(mp(100,a[0]),mp(0,0)));
	while(!que.empty())
	{
		P2 p = que.front(); que.pop();
		if(p.fi.sc == 0)
		{
			if(p.sc.fi == n-1) continue;
			if(dp[p.fi.fi][a[p.sc.fi+1]][p.sc.fi+1][p.sc.sc] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc])
			{
				dp[p.fi.fi][a[p.sc.fi+1]][p.sc.fi+1][p.sc.sc] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc];
				que.push(mp(mp(p.fi.fi,a[p.sc.fi+1]),mp(p.sc.fi+1,p.sc.sc)));
			}
			continue;
		}
		if(p.fi.fi-b[p.sc.fi] > 0)
		{
			if(p.fi.sc-(p.sc.sc+1) <= 0)
			{
				if(dp[p.fi.fi-b[p.sc.fi]][0][p.sc.fi][p.sc.sc+1] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1)
				{
					dp[p.fi.fi-b[p.sc.fi]][0][p.sc.fi][p.sc.sc+1] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1;
					que.push(mp(mp(p.fi.fi-b[p.sc.fi],0),mp(p.sc.fi,p.sc.sc+1)));
				}
			}
			else
			{
				if(dp[p.fi.fi-b[p.sc.fi]][min(a[p.sc.fi],p.fi.sc-(p.sc.sc+1)+c[p.sc.fi])][p.sc.fi][p.sc.sc+1] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1)
				{
					dp[p.fi.fi-b[p.sc.fi]][min(a[p.sc.fi],p.fi.sc-(p.sc.sc+1)+c[p.sc.fi])][p.sc.fi][p.sc.sc+1] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1;
					que.push(mp(mp(p.fi.fi-b[p.sc.fi],min(a[p.sc.fi],p.fi.sc-(p.sc.sc+1)+c[p.sc.fi])),mp(p.sc.fi,p.sc.sc+1)));
				}
			}
			if(p.fi.sc-5 <= 0)
			{
				if(dp[p.fi.fi-b[p.sc.fi]][0][p.sc.fi][0] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1)
				{
					dp[p.fi.fi-b[p.sc.fi]][0][p.sc.fi][0] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1;
					que.push(mp(mp(p.fi.fi-b[p.sc.fi],0),mp(p.sc.fi,0)));
				}
			}
			else
			{
				if(dp[p.fi.fi-b[p.sc.fi]][min(a[p.sc.fi],p.fi.sc-5+c[p.sc.fi])][p.sc.fi][0] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1)
				{
					dp[p.fi.fi-b[p.sc.fi]][min(a[p.sc.fi],p.fi.sc-5+c[p.sc.fi])][p.sc.fi][0] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1;
					que.push(mp(mp(p.fi.fi-b[p.sc.fi],min(a[p.sc.fi],p.fi.sc-5+c[p.sc.fi])),mp(p.sc.fi,0)));
				}
			}
			if(dp[min(100,p.fi.fi-b[p.sc.fi]+50)][min(a[p.sc.fi],p.fi.sc+c[p.sc.fi])][p.sc.fi][0] > dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1)
			{
				dp[min(100,p.fi.fi-b[p.sc.fi]+50)][min(a[p.sc.fi],p.fi.sc+c[p.sc.fi])][p.sc.fi][0] = dp[p.fi.fi][p.fi.sc][p.sc.fi][p.sc.sc]+1;
				que.push(mp(mp(min(100,p.fi.fi-b[p.sc.fi]+50),min(a[p.sc.fi],p.fi.sc+c[p.sc.fi])),mp(p.sc.fi,0)));
			}
		}
	}
	int res = INF;
	for(int i=1;i<=100;i++) for(int j=0;j<=150;j++) res = min(res,dp[i][0][n-1][j]);
	if(res == INF) res = -1;
	cout << res << endl;
}

D:

すごく面白かった(KONAMI)

20点は9C3*6C3*3C3なので全探索。

その後は少し厄介だが、

x座標でソートして

小さいほうから2/3をy座標でソートしなおす。

そのあとx座標が小さいほうの2/3のy座標が小さいほうと大きいほう、x座標の大きいほう1/3から大きいほうを結ぶ三角形をとる

をするだけでなんとN=18を除く60点がとれる。

N=18は9/9に分けてそれぞれで全探索してやるのを1.8secしたら18点もらえた。

int n;
double x[3005],y[3005];
vector<int>res;
vector<int>hoge;
double area(int a,int b,int c)
{
	double ab = sqrt( (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]) );
	double ac = sqrt( (x[a]-x[c])*(x[a]-x[c]) + (y[a]-y[c])*(y[a]-y[c]) );
	double bc = sqrt( (x[b]-x[c])*(x[b]-x[c]) + (y[b]-y[c])*(y[b]-y[c]) );
	return sqrt( (ab+ac+bc)/2 * (-ab+ac+bc)/2 * (ab-ac+bc)/2 * (ab+ac-bc)/2 );
}
bool cmp(int a,int b)
{
	return (x[a] < x[b]);
}
bool cmp2(int a,int b)
{
	return (y[a] < y[b]);
}
bool cmp3(int a,int b)
{
	return (x[a] > x[b]);
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%lf %lf",&x[i],&y[i]);
	}
	if(n == 9)
	{
		vector<int>a;
		for(int i=0;i<9;i++) a.pb(i);
		vector<int>b;
		double best = 0;
		do
		{
			double s = area(a[0],a[1],a[2])+area(a[3],a[4],a[5])+area(a[6],a[7],a[8]);
			if(best < s)
			{
				best = s;
				b = a;
			}
		}while(next_permutation(a.begin(),a.end()));
		for(int i=0;i<n;i+=3) printf("%d %d %d\n",b[i],b[i+1],b[i+2]);
	}
	else if(n == 18)
	{
		vector<int>a,b;
		for(int i=0;i<18;i++) a.pb(i);
		double z = 0.0; double begin = clock();
		do
		{
			random_shuffle(a.begin(),a.end());
			vector<int>c,d,e,f;
			for(int i=0;i<9;i++)
			{
				c.pb(a[i]);
			}
			for(int j=0;j<9;j++)
			{
				d.pb(a[9+j]);
			}
			for(int i=0;i<9;i++)
			{
				e.pb(-1); f.pb(-1);
			}
			int a[21][3];
			double best = 0.0;
			double best2 = 0.0;
			for(int i=0;i<9;i++)
			{
				for(int j=i+1;j<9;j++)
				{
					for(int k=j+1;k<9;k++)
					{
						for(int x=0;x<9;x++)
						{
							if(x == i || x == j || x == k) continue;
							for(int y = x+1;y<9;y++)
							{
								if(y == i || y == j || y == k) continue;
								for(int z = y+1;z<9;z++)
								{
									if(z == i || z == j || z == k) continue;
									bool used[9]={};
									used[i] = used[j] = used[k] = used[x] = used[y] = used[z] = true;
									vector<int>s;
									for(int qq=0;qq<9;qq++)
									{
										if(!used[qq]) s.pb(qq);
									}
									if(area(c[i],c[j],c[k])+area(c[x],c[y],c[z])+area(c[s[0]],c[s[1]],c[s[2]]) > best)
									{
										best = area(c[i],c[j],c[k])+area(c[x],c[y],c[z])+area(c[s[0]],c[s[1]],c[s[2]]);
										e[0] = c[i];
										e[1] = c[j];
										e[2] = c[k];
										e[3] = c[x];
										e[4] = c[y];
										e[5] = c[z];
										e[6] = c[s[0]];
										e[7] = c[s[1]];
										e[8] = c[s[2]];
									}
									if(area(d[i],d[j],d[k])+area(d[x],d[y],d[z])+area(d[s[0]],d[s[1]],d[s[2]]) > best2)
									{
										best2 = area(d[i],d[j],d[k])+area(d[x],d[y],d[z])+area(d[s[0]],d[s[1]],d[s[2]]);
										f[0] = d[i];
										f[1] = d[j];
										f[2] = d[k];
										f[3] = d[x];
										f[4] = d[y];
										f[5] = d[z];
										f[6] = d[s[0]];
										f[7] = d[s[1]];
										f[8] = d[s[2]];
									}
								}
								
							}
						}
					}
				}
			}
			if(z < best+best2)
			{
				z = best+best2;
				b.clear();
				for(int i=0;i<9;i++) b.pb(e[i]);
				for(int i=0;i<9;i++) b.pb(f[i]);
			}
		}while(begin+1.8*CLOCKS_PER_SEC >= clock());
		for(int i=0;i<n;i+=3) printf("%d %d %d\n",b[i],b[i+1],b[i+2]);
	}else
	{
		int a[3005];
		for(int i=0;i<n;i++) a[i] = i;
		sort(a,a+n,cmp);
		vector<int>pre;
		vector<int>bac;
		for(int i=0;i<n*2/3;i++) pre.pb(a[i]);
		for(int i=n*2/3;i<n;i++) bac.pb(a[i]);
		sort(pre.begin(),pre.end(),cmp2);
		sort(bac.begin(),bac.end(),cmp3);
		for(int i=0;i<n/3;i++)
		{
			printf("%d %d %d\n",pre[i],pre[n*2/3-1-i],bac[i]);
		}
	}
}

E:

読んでない


100+100+100+98+0 = 398でした。

2014-06-28

ARC #026 && 101 Hack June'14 00:11

成し遂げたぜ。

ARC #026

A: 一種のGreedy

B: やるだけ (10^10 = (5*10^9)^2とかいうひどい勘違いをしていた)

C: segtreeした

D: 時給きめうち-> MST (ただしコストが負の辺は無条件で追加)

こういう問題は昔から好きなのでラッキーでした。

#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 fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
 
int par[10005];
int ran[10005];
void init()
{
	for(int i=0;i<10005;i++) par[i]=i,ran[i]=0;
}
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(ran[x]<ran[y]) par[x]=par[y];
	else 
	{
		par[y]=par[x];
		if(ran[x] == ran[y]) ran[x]++;
	}
}
bool same(int x,int y)
{
	return find(x)==find(y);
}
vector<pair<pair<double,double>,P> > gen;
 
int main()
{
	int n,m;
	cin >> n >> m;
	for(int i=0;i<m;i++)
	{
		int a,b;
		double c,t;
		scanf("%d %d %lf %lf",&a,&b,&c,&t);
		gen.pb(mp(mp(c,t),mp(a,b)));
	}
	double lb = 0.0;
	double ub = 1145140.0;
	double mid;
	for(int i=0;i<114;i++)
	{
		mid = (lb+ub)/2;
		vector<pair<double,P> > vec;
		for(int j=0;j<m;j++)
		{
			double ne = gen[j].fi.fi - gen[j].fi.sc*mid;
			vec.pb(mp(ne,gen[j].sc));
		}
		sort(vec.begin(),vec.end());
		init();
		double sum = 0.0;
		for(int i=0;i<vec.size();i++)
		{
			if(vec[i].fi <= 0.0)
			{
				sum += vec[i].fi;
				unite(vec[i].sc.fi,vec[i].sc.sc);
			}
			else if(!same(vec[i].sc.fi,vec[i].sc.sc))
			{
				sum += vec[i].fi;
				unite(vec[i].sc.fi,vec[i].sc.sc);
			}
		}
		if(sum <= 0.0) ub = mid;
		else lb = mid;
	}
	printf("%.15f\n",mid);
}

2位(過去最高順位)でした。やったね


101 Hack June'14

A: GCDをとる

B: まとめると調和級数で処理できる

C: bitごとにsegtreeをつくるテク

D: sa+lcpして適当ににぶたんする

#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++)
#define SIZE (1<<17)

int ran[100005];
int n,k;
int tmp[100005];
int sa[100005];
int lcp[100005];

void construct_lcp(string S)
{
	for(int i=0;i<=n;i++) ran[sa[i]] = i;
	
	int h = 0;
	lcp[0] = 0;
	
	for(int i=0;i<n;i++)
	{
		int j = sa[ran[i]-1];
		
		if(h) h--;
		for(;j+h<n && i+h<n;h++)
		{
			if(S[j+h] != S[i+h]) break;
		}
		lcp[ran[i]-1] = h;
	}
}

bool compare_sa(int i,int j)
{
	if(ran[i] != ran[j]) return ran[i] < ran[j];
	else
	{
		int ri = i+k<=n ? ran[i+k]: -1;
		int rj = j+k<=n ? ran[j+k]: -1;
		
		return ri < rj;
	}
}

void construct_sa(string S)
{
	for(int i=0;i<=n;i++)
	{
		sa[i] = i;
		ran[i] = i<n?S[i]:-1;
	}
	
	for(k=1;k<=n;k*=2)
	{
		sort(sa,sa+n+1,compare_sa);
		
		tmp[sa[0]] = 0;
		for(int i=1;i<=n;i++)
		{
			tmp[sa[i]] = tmp[sa[i-1]] + compare_sa(sa[i-1],sa[i]);
		}
		for(int i=0;i<=n;i++)
		{
			ran[i] = tmp[i];
		}
	}
}

string s;
int t;

int main()
{
	cin >> t;
	for(int i=0;i<t;i++)
	{
		cin >> s; n = s.size();
		construct_sa(s);
		construct_lcp(s);
		
		ll ind;
		cin >> ind;
		ll prev = 0;

		for(int j=0;j<=n;j++)
		{
			ll len = (ll)(n-sa[j]);
			ll rem = (ll)(j?lcp[j-1]:0);
			ll cur = prev + (len*(len+1)/2-rem*(rem+1)/2);

			if(cur < ind)
			{
				prev = cur;
				continue;
			}

			ll lb = (rem+1);
			ll ub = len;
			ll target = ind-prev;
			//[lb,ub]
			
			while(ub-lb > 0)
			{
				ll mid = (lb+ub)/2;
				if((mid+(rem+1))*(mid-(rem+1)+1)/2 < target) lb = mid+1;
				else ub = mid;
			}
			//solution exists in lb
			target -= ((lb-1)+(rem+1))*((lb-1)-(rem+1)+1)/2;
			printf("%c\n",s[sa[j]+target-1]); break;
		}
	}
}

E: 適当に組んだら2点ちょっともらえた


9位。まさかT-shirtもらえるとは思ってなかった...

|