IJPC practice

IJPCのpracticeをする。

practiceといっても普通に難しい。ある程度以上の人じゃないとあれはプラクティスにならないのではないか。

最初にBをとく。問題文を読まず「taroで素因数分解してjiroに送っちゃっていいのか?」とかおもう。それなら簡単だと思う。

で、問題文を読み直したところ、s<=12ってかいてある。s<=15ならさっきの手法が使える・・・って、送るのは素数だけだから何番目の素数かを送ればいい！
実装してバグとってAC。

#include "grader.h"
#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
void taro(int N) 
{
	int ret=0;
	vector<int>vec;
	int pri=0;
	if(N==2)
	{
		goto l01;
	}
	for(int i=2;i<sqrt(double(N))+1;i++)
	{
		int han=0;
		for(int j=0;j<ret;j++)
		{
			if(vec[j]>sqrt(double(i))+1)
			{
				break;
			}
			if(i%vec[j]==0)
			{
				han=1;
				break;
			}
		}
		if(han==0)
		{
			vec.push_back(i);
			ret++;
			if(N%i==0)
			{
				pri=1;
				break;
			}
		}
	}
	l01:;
	if(pri==0)
	{
		for(int k=0;k<12;k++)
		{
			send(0);
		}
	}
	else
	{
		for(int k=0;k<12;k++)
		{
			send(ret%2);
			ret/=2;
		}
	}
}
 
int jiro(int S, int X[]) 
{
	int N=0;
	reverse(X,X+12);
	for(int p=0;p<12;p++)
	{
		N*=2;
		N+=X[p];
	}
	if(N==0)
	{
		return -1;
	}
	vector<int>vec;
	int ret=0;
	for(int i=2;;i++)
	{
		int han=0;
		for(int j=0;j<ret;j++)
		{
			if(vec[j]>sqrt(double(i))+1)
			{
				break;
			}
			if(i%vec[j]==0)
			{
				han=1;
				break;
			}
		}
		if(han==0)
		{
			vec.push_back(i);
			ret++;
			if(ret==N)
			{
				return i;
			}
		}
	}
}

次にDをとく。明らかにsegtree系の問題。分散の式を変形すると、数列の累積和BITと、累積2乗和BITがあればいいことがわかる。
実装。BITがうまく実装できずバグる。直す。サンプルとおる。テスト通らない。
long long トラップであった。ありがち。

#include "variance.h"
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int N;
int *A;
int now;
vector<ll>bit;
vector<ll>bit2;
void bitinit(int n)
{
	now=1;
	for(int i=0;;i++)
	{
		now*=2;
		if(now>n)
		{
			break;
		}
	}
	now++;
	for(int j=0;j<now;j++)
	{
		bit.push_back(0);
		bit2.push_back(0);
	}
}
ll sum(int a)
{
	if(a<0)
	{
		return 0;
	}
	a++;
	ll gou=0;
	for(;;)
	{
		gou+=bit[a];
		a-=a&-a;
		if(a==0)
		{
			break;
		}
	}
	return gou;
}
 
ll sum2(int a)
{
	if(a<0)
	{
		return 0;
	}
	a++;
	ll gou=0;
	for(;;)
	{
		gou+=bit2[a];
		a-=a&-a;
		if(a==0)
		{
			break;
		}
	}
	return gou;
}
void init(int n, int *a)
{
	bitinit(n);
	for(int i=0;i<n;i++)
	{
		update(i,*(a+i));
	}
}
int variance(int i, int j) 
{
	ll kos=j-i+1;
	ll gou=kos;
	ll per=sum(j)-sum(i-1);
	gou*=(sum2(j)-sum2(i-1));
	gou-=per*per;
	gou/=kos*kos;
	return gou;
}
void update(int i, int x)
{
	int dif=x-(sum(i)-sum(i-1));
	int dif2=x*x-(sum2(i)-sum2(i-1));
	i++;
	for(;;)
	{
		bit[i]+=dif;
		bit2[i]+=dif2;
		i+=i&-i;
		if(i==now-1)
		{
			bit[i]+=dif;
			bit2[i]+=dif2;
			break;
		}
	}
}

A:ただのDP。適当にかく。きれいにかける。1発AC。

#include<stdio.h>
#include"ijpc.h"
#include<algorithm>
using namespace std;
int map[100000][4];
int replace(int N, char S[]) 
{
	map[0][0]=map[0][1]=map[0][2]=map[0][3]=4;
	for(int k=0;k<N;k++)
	{
		if(k!=0)
		{
			map[k][0]=min(map[k-1][0],1);
			map[k][1]=min(map[k-1][1],map[k-1][0]+1);
			map[k][2]=min(map[k-1][2],map[k-1][1]+1);
			map[k][3]=min(map[k-1][3],map[k-1][2]+1);
		}
		if(S[k]=='I')
		{
			map[k][0]=0;
		}
		if(S[k]=='J')
		{
			if(k>0)
			{
				map[k][1]=min(1,map[k-1][0]);
			}
		}
		if(S[k]=='P')
		{
			if(k>1)
			{
				map[k][2]=min(2,map[k-1][1]);
			}
		}
		if(S[k]=='C')
		{
			if(k>2)
			{
				map[k][3]=min(3,map[k-1][2]);
			}
		}
	}
	return map[N-1][3];
}

C:二分探索みたいなことをするんだろうが、1の個数の上限があるのでそれではうまくいかない。
各段階ごとにmのn乗根個のバケットにわけてやることにした。
submit。small2個は全部通るが、largeが全然とおってない。またもやlong long トラップだった。
submit。96.15点。1段階でmのn乗根個すべてを見ているわけではないので、多少バケットの大きさを調整。
これで100点を得る。

#include"grader.h"
#include"submission.h"
#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
long long getT(int N, long long M)
{
	ll beg=0,end=M;
	for(int i=0;i<N-1;i++)
	{
		ll dif=end-beg+1;
		ll syo=beg;
		ll now=beg;
		for(int j=0;;j++)
		{
			now=syo+ll((j+1)*pow(double(dif),double(N-i-1)/double(N-i))/1.25);
			if(now>end)
			{
				break;
			}
			int com=compare(now);
			if(com==1)
			{
				end=now;
				break;
			}
			beg=now+1;
		}
	}
	ll ret=beg;
	for(ll k=beg;k<=end;k++)
	{
		int zan=compare(k);
		if(zan==1)
		{
			ret=k;
			break;
		}
	}
	return ret;
}

書いてる途中でEscキーを押してしまい一瞬ひやっとしたがもとにもどってよかった。