AtCoder ABC #192 (SOMPO HD プログラミングコンテスト2021) : F - Potion

しょうもないミスが多すぎた…。
https://atcoder.jp/contests/abc192/tasks/abc192_f

問題

N個のポーションがあり、それぞれ魔力A[i]が設定されている。
N個のうちk個のポーションを混ぜると、魔力は個々のポーションの総和となる。(kは1でもよい)
また、そのポーションは以後時刻1毎にkだけ魔力が離散的に増加する。

魔力Xのポーションを作るのに必要な最短時間を求めよ。

解法

ポーションを混ぜたとき、その魔力の総和をXから引くと、kで割り切れるようにしたい。
そこで、kを総当たりし、魔力の総和をmod kで分類して、各分類における最大値を求めよう。
もし総和をSとして(X-S)がkで割り切れるなら、(X-S)/kが解の候補となる。

sum(A)≦Xなので、混ぜた時点で魔力がXを超えることはないため、貪欲に最大値を目指して問題ない。

int N;
ll X,A[101];

ll dp[102][102];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	FOR(i,N) cin>>A[i];
	
	ll ret=1LL<<60;
	
	for(i=1;i<=N;i++) {
		FOR(x,N+1) FOR(y,N+1) dp[x][y]=-1LL<<60;
		dp[0][0]=0;
		FOR(x,N) {
			for(j=i;j>=1;j--) {
				FOR(y,i) dp[j][(y+A[x])%i]=max(dp[j][(y+A[x])%i],dp[j-1][y]+A[x]);
			}
		}
		FOR(y,i) if(dp[i][y]>=0&&(X-y)%i==0) ret=min(ret,(X-dp[i][y])/i);
	}
	cout<<ret<<endl;
}

まとめ

配列を使いまわすコードを書いていたが、配列の処理順を間違えて3WA…。