yukicoder No.398 ハーフパイプ(2)

2通りの解がある
・DP解
dp[人数][最低点][最高点][合計点]でDPしてΣ{dp[6][m][M][s]|s=X*4+m+M}を求める

#define min(a,b)(a<b?a:b)
#define max(a,b)(a>b?a:b)
long d[7][101][101][601],a;
i,m,M,s,k;
int main(){
	for(m=0;m<101;m++)d[1][m][m][m]=1;
	for(i=1;i<6;i++)for(m=0;m<101;m++)for(M=m;M<101;M++)
		for(k=0;k<101;k++)for(s=m*i;s<=i*100;s++)
			d[i+1][min(m,k)][max(M,k)][s+k]+=d[i][m][M][s];
	scanf("%d.%d",&i,&k);
	s=i*4+k/25;
	for(m=0;m<101;m++)for(M=m;M<101;M++)a+=d[6][m][M][s+m+M];
	printf("%ld",a);
	return 0;
}

実行時間は1秒くらい
(iの分6)×(mの分100)×(kの分100)×(sの分i*(100-m))×(Mの分100-m)≒6*100*100*3*10000/3=6*10^8 回くらいループするような気がするので、かなりギリギリになると思ったら意外と余裕があった。何故？

・数学解
よく考えるとこれって数学で解決出来そう。
Xを算出するにあたって使われた4人分の点を100^4ループして調べて、残り2人の点が最高と最低になるようにしてその順列を考える。
（実際には100^3ループで4人目はX*4から引けばいいのだけど、それだと最高最低の判定が難しくなるので…）

coe[8][4]={
{720,360,360,180},//-bcde-
{360,180,120,60},//-bcdd-
{360,180,180,90},//-bccd-
{120,60,30,15},//-bccc-
{360,120,180,60},//-bbcd-
{180,60,60,20},//-bbcc-
{120,30,60,15},//-bbbc-
{30,6,6,1}//-bbbb-
};
long a;i1,i2,i3,i4,f;
main(S){
	scanf("%d.%d",&i1,&i2);S=i1*4+i2/25;
	for(i1=0;i1<=100;i1++)for(i2=i1;i2<=100;i2++)for(i3=i2;i3<=100;i3++)for(i4=i3;i4<=100;i4++)if(i1+i2+i3+i4==S){
		f=(i1==i2)*4|(i2==i3)*2|i3==i4;
		a+=coe[f][0]*i1*(100-i4);	//(最低点)<i1 && i4<(最高点)
		a+=coe[f][1]*(100-i4);	//(最低点)==i1 && i4<(最高点)
		a+=coe[f][2]*i1;	//(最低点)<i1 && i4==(最高点)
		a+=coe[f][3];	//(最低点)==i1 && i4==(最高点)
	}
	printf("%ld",a);
	return 0;
}

100^4くらいループしてるはずなのに8ms
if文を見てi4のループが消されて実質100^3とかそんな感じに見える

で、どっちが短くなるのか
結論から言えばDP解の方だった。
数学解の暫定最短はFF256grhyさんによる287B #104678 No.398 ハーフパイプ(2) - yukicoder
（自分には290Bしか作れなかった ideone
　※ただしyukicoderでは謎のWA #104668 No.398 ハーフパイプ(2) - yukicoder
　　原因が分かる方がいましたら教えて下さい
　※これらのコードには使っていない変数fの消し忘れがあり292Bになっている）
方針は上で書いたものと全く同じ素直なものなのでまあ読める

DP解を縮めていく
とりあえずまずはなんども出てくるfor文をdefine

#define R(i,a)for(i=a;i<101;i++)
long d[7][101][101][601],a;
m,M,s,k;
main(i){
	R(m,0)d[1][m][m][m]=1;
	for(i=1;i<6;i++)R(m,0)R(M,m)R(k,0)for(s=m*i;s<=i*100;s++)d[i+1][m<k?m:k][M>k?M:k][s+k]+=d[i][m][M][s];
	scanf("%d.%d",&i,&k);
	R(m,0)R(M,m)a+=d[6][m][M][i*4+k/25+m+M];
	a=!printf("%ld",a);
}

実行時間に余裕があるのを見て、もしかしてfor文は全部0スタートでも大丈夫だったりする？
だったら初期化も縮められる

#define R(i)for(i=0;i<101;i++)
long d[7][101][101][601],a;
m,M,s,i;
main(k){
	for(d[0][100][0][0]=1;i<6;i++)R(m)R(M)R(k)for(s=m*i;s<=i*100;s++)d[i+1][m<k?m:k][M>k?M:k][s+k]+=d[i][m][M][s];
	scanf("%d.%d",&i,&k);
	R(m)R(M)a+=d[6][m][M][i*4+k/25+m+M];
	a=!printf("%ld",a);
}

1500msで通過。じゃあfor文をちょっと細工して

#define R(i)for(i=0;i<101;i++)
//↓
#define R(i)for(i=101;i--;)

と書き換えるくらいは大丈夫だよね。1700ms

さて、わざわざ答えの出力の為に新しい変数を用意するのはめんどくさい
DP計算部分のループが終わった時点ではiは6、m,M,kは-1、sは601になっているので
mを出力用の変数として使い回すことで1B短縮

#define R(i)for(i=101;i--;)
long d[7][101][101][601],m;
M,s,i;
main(k){
	for(d[0][100][0][0]=1;i<6;i++)R(m)R(M)R(k)for(s=m*i;s<=i*100;s++)d[i+1][m<k?m:k][M>k?M:k][s+k]+=d[i][m][M][s];
	scanf("%d.%d",&i,&s);
	R(k)R(M)m-=d[6][k][M][i*4+s/25+k+M];
	//↑マイナスを計算することで、mには最終的に-1-(答え) が入るので、~mで答えが取り出せる
	M=!printf("%ld",~m);
}

257B

16/07/24追記
float型の変数を新たに用意した方が1B短くなる

	float t;//+8B
	scanf("%f",&t);
//	scanf("%d.%d",&i,&s);から-6B
	d[6][k][M][s=t*4+k+M]
//	d[6][k][M][i*4+s/25+k+M]から-3B

さらにこれにより最初にscanfしておくことが可能になったのでdの初期化とまとめることで2B短縮

#define R(i)for(i=101;i--;)
long d[7][101][101][601],m;
M,s,i;
float t;
main(k){
	for(d[0][100][0][0]=scanf("%f",&t);i<6;i++)R(m)R(M)R(k)for(s=m*i;s<=i*100;s++)d[i+1][m<k?m:k][M>k?M:k][s+k]+=d[i][m][M][s];
	R(k)R(M)m-=d[6][k][M][s=t*4+k+M];
	M=!printf("%ld",~m);
}

254B

2017/11/07追記
d[0][100][0][0]を**100[*d]と書き換えることで6B短縮
コンパイラのバージョンアップによる3Bと合わせて9B短縮

#define R(i)for(i=101;i--;)
long d[7][101][101][601],m;
M,s,i;
float t;
main(k){
	for(**100[*d]=scanf("%f",&t);i<6;i++)R(m)R(M)R(k)for(s=m*i;s<=i*100;s++)d[i+1][m<k?m:k][M>k?M:k][s+k]+=d[i][m][M][s];
	R(k)R(M)m-=d[6][k][M][s=t*4+k+M];
	printf("%ld",~m);
}

245B

メモ

yukicoderでゆるふわgolf

yukicoder No.398 ハーフパイプ(2)