F - Potion

[Q] https://atcoder.jp/contests/abc192/tasks/abc192_f
1. N=100と小さめ。O(N^4)でDPする。
2. DP[maxmod][index][mod] = maxval で管理。
maxmod は 1~N
index は 0~N
mod は 0~(N-1)

Q. DP[3][1][2] = 5 は？

A. 
最終的に3個(maxmod)とる場合の探索だけど、
今は1個(index)とった時点。
その総和を3(maxmod)で割ったあまり val%3 == 2 を満たす最大の値が5だよ。という管理。

こんなシチュエーション。
A[] = {1,2,3,4,5}
3個とることを想定した探索で、
1個とった時点で3で割ったあまりが 2 になる最大の取り方は 5 // DP[3][1][2]

Q. DPの値をデバッグ？

Q. 例1
3 9999999999
3 6 8

・1個とる場合
DP[1][0][0]:0 // 初期条件
DP[1][1][0]:8 // ★1個とる場合の最大値

9999999999%1 = 0 なので、 DP[1][1][0] が解答候補。

・2個とる場合
DP[2][0][0]:0  // 初期条件
DP[2][0][1]:0  // 初期条件
DP[2][1][0]:8  // 1個とるうち、val%2=0 になる最大値
DP[2][1][1]:3  //             val%2=1 
DP[2][2][0]:14 // 2個とるうち、val%2=0 になる最大値
DP[2][2][1]:11 // ★2個とる場合の最大値

9999999999%2 = 1 なので、 DP[2][2][1] が解答候補。

DP[3][0][0]:0
DP[3][0][1]:0
DP[3][0][2]:0
DP[3][1][0]:6
DP[3][1][1]:0
DP[3][1][2]:8
DP[3][2][0]:9
DP[3][2][1]:0
DP[3][2][2]:14
DP[3][3][0]:0 // ★3個とる場合の最大値(0なので考慮外)
DP[3][3][1]:0
DP[3][3][2]:17

9999999999%3 = 0 なので、 DP[3][3][0] が解答候補。だけど、0なので見ない。

答えは
DP[2][2][1]:11 が最大値なので、
2個とって、11 のポーションを作る。
(9999999999-11)/2 = 4999999994

実装

int main(){
 cincout();
 
 cin >> N >> X;
 rep(i, N) cin >> A[i];
 ll ans = oo;
 rep(i, N){
   ll a = A[i];
   for(ll mod=1; mod<=N; ++mod){
     for (ll j=min(i, mod-1); j>=0; --j){ // 今とったらj個とることになる
       rep(k, mod){
         if (DP[mod][j][k] == 0 && (j>0 || k>0) ) continue;
         ll val = DP[mod][j][k] + a;
         chmax(DP[mod][j+1][(k+a)%mod], val);
       }
     }
   }
 }
 
 for(ll i=1; i<=N; ++i){
   ll val = DP[i][i][X%i];
   if (val == 0) continue;
   chmin(ans, (X-val)/i);
 }
 cout << ans << endl;

https://atcoder.jp/contests/abc192/submissions/27466115