Google Code Jam 2021 Round 1B : B. Subtransmutation

これはなんなんだろう…？
https://codingcompetitions.withgoogle.com/codejam/round/0000000000435baf/00000000007ae4aa

問題

パラメータA,Bが与えられる。
大きさNの材料を分割すると、N-AとN-Bの2個が得られる(0以下の大きさの材料は、ないものとみなす)。

今、大きさ1～20の材料が最小何個欲しいか、という情報が与えられる。
1つの材料から始めて、分割を行い条件を満たすには、最小どの大きさの材料があればよいか。

解法

大きさ402まで、愚直に試すと通る。

int N,A,B;
const int X=2000;
int U[X+2];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>A>>B;
	ZERO(U);
	FOR(i,N) cin>>U[i+1];
	
	for(i=N+1;i<=X;i++) {
		int num[X+2]={};
		num[i]=1;
		for(j=i;j>=1;j--) {
			if(num[j]<U[j]) break;
			x=num[j]-U[j];
			if(j>A) num[j-A]=min(num[j-A]+x,800);
			if(j>B) num[j-B]=min(num[j-B]+x,800);
		}
		
		if(j==0) break;
	}
	
	if(i==X+1) _P("Case #%d: IMPOSSIBLE\n",_loop);
	else _P("Case #%d: %d\n",_loop,i);
}

まとめ

厳密に証明せずに通した人も多いんじゃないだろうか…？