アルゴ式のテスターに選ばれました（9日目）

進捗

数日詰まっていたQ3-6に何とかACし，勢いそのままにQ3-7もACしました！やった！！

Q3-6について

最初の実装

dp[i][j]はi番目までを使用しjを作れた場合は，j%Aの値．jを作れなかったときは-1．

N, A, B = map(int,input().split())
X = list(map(lambda x: int(x)%A  ,input().split()))
sumX = sum(X)
dp = [ [-1]*(sumX+1) for _ in range(N) ]
dp[0][0] = 0
dp[0][X[0]] = X[0]%A
for i in range(N-1):
    for j in range(sumX+1):
        if dp[i][j] != -1:
            dp[i+1][j] = dp[i][j]
            if j + X[i+1] <= sumX:
                dp[i+1][j+X[i+1]] = (j + X[i+1])%A
if B in set(dp[N-1]):
    print('Yes')
else:
    print('No')

結果

1TLEで，そのほかのケースはAC．

解決

自力解決とはいきませんでしたが，アルゴ式の公式アカウントさんに，進捗報告（TLEしたこと）をTwitterのDMでお伝えしたところ，提出コードを見てくださり，

「sumXがとても大きくなる場合にTLEしている様子ですね。」

と言う絶妙なヒントを頂いた．しかも，その後に続けて

「もしヒントなど必要であれば、その旨伝えていただけるとお教えいたします。」

とのことでした（ありがたい）．

この絶妙なヒントを受けて落ち着いて考えてみました．

そもそも先の実装では，dp[i][j]においてiをNまで，jをsumXまでループさせていたので，もっとループ回数を減らすことを考えました．そこで自分のメモを見て次のことに気がつきました

なんだこれは，と言う感じかもしれませんが，これは入力サンプルのdpテーブルを書いたものです．これを書いているときに，横（jに相当）方向の値とjの値が一致していること，Aによる剰余をとっているので，表の中の値も0~A-1までしか取らないことに気づきました（最初に気づきましょうと言うのは置いておきましょう．あと，挿入した図はちょっとずれてますね）

と言うことは，jのループはsumXまでではなくて，Aまででもいいのでは？となり次の実装にしてみました．

N, A, B = map(int,input().split())
X = list(map(lambda x: int(x)%A  ,input().split()))
dp = [ [-1]*(A+1) for _ in range(N) ]
dp[0][0] = 0
dp[0][X[0]] = X[0]%A
for i in range(N-1):
    for j in range(A+1):
        if dp[i][j] != -1:
            dp[i+1][j] = dp[i][j]
            dp[i+1][(j+X[i+1])%A] = (j + X[i+1])%A

if B in set(dp[N-1]):
    print('Yes')
else:
    print('No')

このコードで無事ACです．

ちなみに，解説ではもっとスマートなdpテーブルの持ち方をしており，解説を読めばそりゃそうした方がいいよな，と納得感しかありませんでした．

Q3-7について

最初に手で計算しました．

注：一番下の四角で囲んである一番大事な部分「W-dp[i][j]のMax」の部分は「W-2*dp[i][j]のMax」の間違いです．

幸いにもこの考察が正しかったようで割とスムーズにACできました．

N = int(input())
W = list(map(int, input().split()))
sumW = sum(W)
dp = [ [False]*(sumW//2 + 1) for _ in range(N)]
dp[0][0] = True
if W[0] <= sumW//2:
    dp[0][W[0]] = True

mx = 0
for i in range(N):
    for j in range(sumW//2 + 1):
        if i+1 < N:
            if not dp[i][j]:
                continue

            dp[i+1][j] = dp[i][j]

            if j+W[i+1] <= sumW//2:
                dp[i+1][j+W[i+1]] = True
                mx = max(j+W[i+1],mx)
print(sumW-2*mx)

ただこれも解説の方法とは違っていました．解説の方法も勉強しておかなくちゃと言う感じですが，とりあえず解けたので嬉しいです．

感想

とりあえずアルゴ式の動的計画法の最初のコンテンツがなんとか終了しました．せっかくなのでこのまま続けて【特集】典型的な動的計画法のパターンを整理 ～ ナップサック DP 編 ～をやろうかなぁと思っていますが，違うところも興味あるので悩ましです．整数論のところとかやりたいなぁ．

あと，記事の途中にアルゴ式さんとのDMのくだりを書きましたが，ヒントを与えるということに対するスタンスがとても教育的でありがたかったです．

まだまだ頑張るぞ