Open10

AtCoder DP 練習場

チェロチェロ

https://atcoder.jp/contests/tdpc/tasks/tdpc_dice
40分悩んで全く解法が違ったので供養

dが小さいサンプルだけ解けたDP
# template
from math import gcd
from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
# mod = 10 ** 9 + 7
# mod = 998244353
n,d=mi()
max_num=d
dp=[[0]*(max_num) for i in range(n)]

dp[0][0]=0
for i in range(n):
    for num in range(max_num):
        if i == 0:
            dp[i][num]=1
        else:
            for k in range(1,7):
                dp[i][num*k%d]+=dp[i-1][num]

print(dp[-1][0]/sum(dp[-1]))

サイコロの目を素因分解するという発想が出ないとそもそも解けない
Dの235の素因数分解値を目指してDPする
例題のLv2でこれってきついぜ…

回答AC
# template
from math import gcd
from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
# mod = 10 ** 9 + 7
# mod = 998244353
n, d = mi()

def anal235(d):
    if d == 1:
        return 1
    d2 = d3 = d5 = 0
    while d % 2 == 0:
        d2 += 1
        d //= 2
    while d % 3 == 0:
        d3 += 1
        d //= 3
    while d % 5 == 0:
        d5 += 1
        d //= 5
    # 235の倍数以外サイコロの積は存在しない
    if d != 1:
        return 0
    dp = [[[[0 for i in range(d5 + 1)] for i in range(d3 + 1)] for i in range(d2 + 1)] for i in range(n + 1)]
    dp[0][0][0][0] = 1

    for i in range(1, n + 1):
        for j in range(d2 + 1):
            for k in range(d3 + 1):
                for l in range(d5 + 1):
                    p = dp[i - 1][j][k][l]
                    # 1-6の目が出た際の確率を足す
                    # d2、d3、d5の数は超えても条件であるD倍は満たす
                    # 従って、各値を超えた場合はd2，d3，d5の確率を増やしている
                    dp[i][min(d2, j + 0)][min(d3, k + 0)][min(d5, l + 0)] += p / 6
                    dp[i][min(d2, j + 1)][min(d3, k + 0)][min(d5, l + 0)] += p / 6
                    dp[i][min(d2, j + 0)][min(d3, k + 1)][min(d5, l + 0)] += p / 6
                    dp[i][min(d2, j + 2)][min(d3, k + 0)][min(d5, l + 0)] += p / 6
                    dp[i][min(d2, j + 0)][min(d3, k + 0)][min(d5, l + 1)] += p / 6
                    dp[i][min(d2, j + 1)][min(d3, k + 1)][min(d5, l + 0)] += p / 6

    return (dp[-1][d2][d3][d5])

print(anal235(d))
チェロチェロ

https://atcoder.jp/contests/abc015/tasks/abc015_4
敗北したし学びが多かったので記事にしました

記事にした際のメモ

幅と個数制限ということで、dpは[i][cnt][sum_w]で見ればよかったのだ…
単純に制限が増えるたびに次元が増えるということなかな?

あれ?かっこよく決めたと思ったのに通らん…
# template
# 解説みた
from math import gcd
from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
# mod = 10 ** 9 + 7
# mod = 998244353
w=ii()
n,k=mi()
a,b=[],[]
for i in range(n):
    A,B=mi()
    a.append(A)
    b.append(B)

dp = [[[0] * (w+1) for i in range(k+1)] for i in range(n+1)]
dp[0][0][0] = 0
# dp[i][cnt][sum_w]
# i番目まで見た中で、cnt以下で選択し、sum_w以下の幅で選択したうちの最大値
# この問題だと重量と個数制限がついているのでそれぞれ見る必要があるのだ
for i in range(n):
    for cnt in range(k+1):
        for sum_w in range(w+1):
            # sum_w以下、cnt以下であれば最大値を比較する
            if sum_w - a[i]>=0 and cnt - 1 >=0:
                dp[i+1][cnt][sum_w] = max(dp[i][cnt][sum_w],dp[i][cnt-1][sum_w-a[i]]+b[i])
            else:
                dp[i+1][cnt][sum_w] =dp[i][cnt][sum_w]
print(dp[n][k][w])

と思ったけれどこれ通らない。。。
pypyだとMLE、PythonだとTLEになる

どうも3次元DPとすると、メモリー超過でMLEが出るっぽい。
よく見るとメモリー制限が256Mbと現行の25%と少ないのでNGとなるみたい。
というわけで、2次元DPで処理する必要がある。
といってもどうやれば良いのかわからんのでみんなの答案をチェック。
dp[i][cnt][sum_w]のうちの[i]は工夫で消せる!

dp[i]の更新には一つ前のdp[i-1]の物があれば良い。
つまり、dp_prev[cnt][sum_w]、dp_next[cnt][sum_w]の2つでイケる。

と分かっても結構ハマったので書き出し。

  • dp[i]→dp[i+1]の更新
    • dp_prev=dp_next とすると、参照渡しとなって狙いの挙動にならなくなる
    • dp_prev=copy.deepcopy(dp_next) とすると、TLEとなる
    • dp_prev, dp_next = dp_next, dp_prev とすると、うまい具合に参照渡しとなり通る
      • 更新後のdp_nextは使用しないが、ちょうどいいゴミ箱として使ってる

ということで、MLE対策、次元の落とし方、と学びが多い問題でありました!

ACコード
# template
# 解説みた
from math import gcd
from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
# mod = 10 ** 9 + 7
# mod = 998244353
w = ii()
n, k = mi()
a, b = [], []
for i in range(n):
    A, B = mi()
    a.append(A)
    b.append(B)

dp_prev = [[0] * (w + 1) for i in range(k + 1)]
dp_next = [[0] * (w + 1) for i in range(k + 1)]
# dp[i][cnt][sum_w]
# この問題だと重量と個数制限がついているのでそれぞれ見る必要があるのだ
# i番目まで見た中で、cnt以下で選択し、sum_w以下の幅で選択したうちの最大値
# とすると、3次元配列だとメモリ容量食うのでMLEで敗北する

# dp_prev[cnt][sum_w] dp_next[cnt][sum_w]として
# iが更新されるたびにdp配列を更新することでメモリを節約する
for i in range(n):
    for cnt in range(k + 1):
        for sum_w in range(w + 1):
            # sum_w以下、cnt以下であれば最大値を比較する
            if sum_w - a[i] >= 0 and cnt - 1 >= 0:
                dp_next[cnt][sum_w] = \
                    max(dp_prev[cnt][sum_w], dp_prev[cnt - 1][sum_w - a[i]] + b[i])
            else:
                dp_next[cnt][sum_w] = dp_prev[cnt][sum_w]
    # iを更新するのでdp_prevにdp_nextを入れる
    # dp_prev=dp_next とするとアドレス渡しとなり、以降同じ値を取るためNG
    dp_prev, dp_next = dp_next, dp_prev
    dp_prev = copy.deepcopy(d)
print(dp_prev[k][w])
チェロチェロ

https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_d
本当にパスタ大好きなら毎日同じ味でも飽きない。
従ってn**3%modが解。nが大きいとTLEとなるので、逐一modかけよう!

と云うのはさておき、やっぱりわからん……。
初期条件、該当パスタ以外の弾き方がわからんで敗北

よく分かった解説

https://betrue12.hateblo.jp/entry/2020/03/29/232441

DPの遷移はイメージできても、初期条件何入れればいいのだ?となる
とりあえずわかったのは、DPはざっくり以下の項目が思いつけばイケるっぽい?

  • 値の遷移
  • 初期条件(dp[0]値とdp配列内の値)
  • 遷移を通す通さないの条件
    まぁ数こなせば理解していくでしょ…多分。
コード
# template
# めっちゃ解説見た
from math import gcd
from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
# mod = 10 ** 9 + 7
# mod = 998244353

n, k = mi()
pasta = [-1] * n
# 日付は1日、パスタは1から3なので、1引いとく
for i in range(k):
    a, b = mi()
    pasta[a - 1] = b - 1

dp = [[[0] * 3 for i in range(3)] for i in range(n + 1)]
dp[0][0][0] = 1

for i in range(n):
    for prepre in range(3):
        for pre in range(3):
            for today in range(3):
                # パスタの指定がない場合は2日目まで何食べても大丈夫
                # 初期条件埋めたいし、｢2以下は通して良い｣(これがこの問題の肝かな)
                if prepre == pre == today and 2 <= i:
                    continue
                # パスタの指定がある場合は遷移させない
                # -1のときは指定がないので通す
                if pasta[i] != today and pasta[i] != -1:
                    continue
                dp[i + 1][pre][today] += dp[i][prepre][pre]
res = 0
mod = 10000
for i in range(3):
    for j in range(3):
        res += dp[n][i][j] % mod
res %= mod
print(res)
チェロチェロ

https://atcoder.jp/contests/joi2013yo/tasks/joi2013yo_d
問題文読み間違った
同じ服を続けて着ることができないものだと誤読して、なんか良くわからんプログラムになってた
改めて問題文を読み直したらすんなり理解。
組み合わせは頭こんがらがるので、最大値探す系は理解しやすい印象。