K^2PC Hard

4100/7500 で18thでした。
悪くはないと思いますが、Dの満点解法の実装が間に合わなくて悔しいです。HardのD,Eは良い問題だと思うので、Hardで丁度良かったです。

A.
1個,2個,3個,...
に分かれているから、
第n群の末項は、全体で第n*(n+1)/2項で、(1,n)になります。
どの群の何項にあたるかを調べて、数値を求めます。
それらを足し合わせたものが、第何項目かを計算すれば解けます。

typedef long long ll;

void f(ll &a, ll &b, ll c){
	for(ll i = 0; i < 100000; i++){
		if(i*(i+1)/2<c&&c<=(i+1)*(i+2)/2){
			ll d = c - i*(i+1)/2;
			b+=d;
			a+=i-d+2;
		}
	}
}

int main(){
	ll s,t;
	cin>>s>>t;
	ll a,b;
	a = b = 0;
	f(a,b,s);
	f(a,b,t);
	cout<<(a+b-2)*(a+b-1)/2+b<<endl;
	
	
	return 0;
}

B.
治療済みの神経を入力順に見ていって、
その神経aより上に治療済みの神経があったら、aを無視します。
治療済みの神経が無かったら、そこより下は虫歯神経ではないから、それの個数を数えます。
神経の総数から、虫歯神経でないものの数を引くと虫歯神経の個数を求められます。

typedef unsigned long long ll;
typedef pair<ll,ll> P;
map<P,int> de;
ll dei[100000],dej[100000];

ll p(int a){
	ll t=0;
	for(int i = 0; i <= a; i++){
		t+=((ll)1<<i);
	}
	return t;
}

int main(){
	int k,n;
	scanf("%d%d",&k,&n);
	ll ans = p(k);
	
	for(int i = 0; i < n; i++){
		scanf("%lld%lld",dei+i,dej+i);
		de[make_pair(dei[i],dej[i])]=1;
	}
	for(int i = 0; i < n; i++){
		ll a = dei[i],b = dej[i];
		bool f = true;
		ll dep = a;
		while(dep){
			dep--;
			b=(b+1)/2;
			if(de[make_pair(dep,b)]){
				f=false;
				break;
			}
		}
		if(f){
			ans-=p(k-a);
		}
	}
	cout<<ans<<endl;
	return 0;
}

C.
まず、nが平方数じゃなかったら、nから戻ってこれないので、-1を出力します。(ただし、n=2を除く)
n=sq^2であると分かったら、xをnまで増やして、xをsqにします。
同様にして、xを(sq-1)^2まで増やして、xをsq-1にし、
xが2になるまで続けます。
あとは、増やす回数と1/2乗する回数の和を出力すればよいです。

typedef long long ll;

int main(){
	ll n,sq;
	cin>>n;
	ll ans=0;
	if(n==2){
		cout<<0<<endl;
		return 0;
	}
	{
		ll lo=1,hi=10000000;
		while(hi-lo>1){
			ll md=(lo+hi)/2;
			if(md*md<=n){
				lo=md;
			}else{
				hi=md;
			}
		}
		if(lo*lo!=n){
			cout<<-1<<endl;
			return 0;
		}
		sq=lo;
	}
	ll pos=2;
	do{
		ans+=sq*sq-pos+1;
		pos=sq;
		--sq;
	}while(pos>2);
	cout<<ans<<endl;
	return 0;
}

D.
ある地点に対して、

• 飛ばさない
• 行くときだけ飛ばす
• 帰るときだけ飛ばす

という選択肢があり、水たまりの有無や、直前の行動によっては選択できないものがあるから、その分を足さないようにして動的計画法で解きます。

int dp[3][3000001];
bool de[2][3000001];


int main(){
	int d,n;
	cin>>d>>n;
	bool f=true;
	for(int i = 0; i < n; i++){
		int a,b;
		cin>>a>>b;
		a--;
		de[a][b]=1;
		if(de[1-a][b])f=false;
	}
	if(!f){
		cout<<0<<endl;
		return 0;
	}
	dp[0][0]=1;
	for(int i = 0; i < d; i++){
		if(!de[0][i+1]&&!de[1][i+1])dp[0][i+1]=(dp[0][i]+dp[1][i]+dp[2][i])%mod;
		if(!de[0][i+1])dp[1][i+1]=(dp[0][i]+dp[2][i])%mod;
		if(!de[1][i+1])dp[2][i+1]=(dp[0][i]+dp[1][i])%mod;
	}
	cout<<(dp[0][d-1]+dp[1][d-1]+dp[2][d-1])%mod<<endl;
	return 0;
}

E.
部分点解法です。
指数は必ず1であるから、区間の和をO(1)で求められて、それをmod Pするだけです。
これだけで、500点(Aの点数と同じ)貰えるので解きましょう。

満点解法は、バケットに分けて尺取法らしいです。

int a[100000],s[100001];

int main(){
	int n,q,p;
	cin>>n>>q>>p;
	for(int i = 0; i < n; i++)scanf("%d",a+i);
	for(int i = 0; i < n; i++)s[i+1]=(s[i]+a[i])%p;
	for(int i = 0; i < q; i++){
		int u,v;
		scanf("%d%d",&u,&v);
		cout<<(s[v]-s[u-1]+p)%p<<endl;
	}
	return 0;
}