の続きです。

JOI 2011 予選 4 - 1 年生

practice.py

N = int(input())
Alist = list(map(int, input().split()))
dp = [[0]*(21) for _ in range(N-1)]
dp[0][Alist[0]] = 1
Alist = Alist[1:]
for n in range(1,N-1):
    for m in range(21):
        if m-Alist[n-1] >= 0:
            dp[n][m] += dp[n-1][m-Alist[n-1]]
        if m+Alist[n-1] <= 20:
            dp[n][m] += dp[n-1][m+Alist[n-1]]
print(dp[N-2][Alist[-1]])

この問題はパターン数をぶち込んでいくタイプのdpです。最初は0を何個dp内に作ればいいのかわかりづらいのですが、坊やが数えられる数の上限は20なので、index番号で混乱しないための0を含めて21個作ってあげれば良いです。そして何回分のリストを作れば良いかについては、ここで重要なのは数字同士に入れる+と-の分岐のパターン数なので、N-2です。for文ではN-1の数は含まれないので、N-1を上限にしてfor文を回してdpリストを作ってあげれば良いです。そして、dpの初期値としてAlistに与えられた最初の値に1を加えてあげれば良いです(最初の数は+or-の影響を受けないので簡単に埋められる。)もう最初の数字を使う機会はないのでAlistから取り除いといてあげましょう。for分の上限は普通のDPと同じように、上のdpリストの上限に従っていけばオッケーです。内部の処理では+のパターンと-のパターンでdpの値を動かしてあげましょう。ここで坊やは負の数を知らない、21以上の計算ができないことを忘れないようにif文で制限をかけといてあげしょう。最後に、リストの最後の列のAlistの最後の数字の行に入っている値を出力してあげればACできます。

JOI 2012 予選 4 - パスタ

practice.py

MOD = 10**4
N,K = map(int, input().split())
decided = [0]*(N+1)
for i in range(K):
    a,b = map(int, input().split())
    decided[a] = b
dp = [[0]*(N+1) for _ in range(4)]
dp[1][0] = 1
ans = 0
for i in range(1,N+1):
    if decided[i] != 0:
        for j in range(1,4):
            dp[decided[i]][i] += dp[j][i-1]
        if i-2>0 and dp[decided[i]][i-1] > 0 and dp[decided[i]][i-2] > 0:
            dp[decided[i]][i-1] -= dp[decided[i]][i-2]
            dp[decided[i]][i] -= dp[decided[i]][i-2]
    else:
        for j in range(1,4):
            for k in range(1,4):
                dp[j][i] += dp[k][i-1]
        for j in range(1,4):
            if i-2>0 and dp[j][i-1] > 0 and dp[j][i-2] > 0:
                dp[j][i-1] -= dp[j][i-2]
                dp[j][i] -= dp[j][i-2]
for i in range(1,4):
    ans += dp[i][-1]
print(ans%MOD)

この問題は最初に、決められた日程のパスタの種類を格納しておくためのリストを作っておくことで大分解きやすくなります。Dpはメインを日数にして、種類数を外に置いて二重配列を作っていきます。初期値が必要なので、0日目の種類1にパターンを1つ追加してあげましょう。そして、dpを始めていきましょう。for文の数が多いので混乱しがちですがやってることはそんなに難しくありません。まずiの日程のパスタの種類が最初に決められていなかったときは、前回の3種類のパスタのパターン数を足し合わせた数が日程のiのパスタのパターン数になります。その後に、日程iのうまくいかないパターンの数を削っていきます。まず1日前と現在の値から、2日前の数を削っていくだけです。もしdecidedで決められていたのなら、decided[i]の種類のパスタの数だけを動かす形で、上と同じような動作をしていけばオッケーです。そして最後に最終日の3種類のパスタのパターン数を足し合わせて、MODで割って出力すればACです。

JOI 2013 予選 4 - 暑い日々

practice.py

D,N = map(int, input().split())
temps = [0]+[int(input()) for _ in range(D)]
clothes = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(D+1) for _ in range(N)]
for i in range(2,D+1):
    for j in range(N):
        if clothes[j][0] > temps[i] or clothes[j][1] < temps[i]:
            continue
        else:
            tmp = 0
            for k in range(N):
                if clothes[k][0] > temps[i-1] or clothes[k][1] < temps[i-1]:
                    continue
                else:
                    tmp = max(tmp, abs(clothes[j][2]-clothes[k][2])+dp[k][i-1])
            dp[j][i] = tmp
ans = 0
for i in range(N):
    ans = max(ans, dp[i][-1])
print(ans)

この問題は服の種類をベースに日数を組み合わせてdpを作っていきます。dpの中身では、実際に値が追加されるのは二日目からなので、for文を2からD+1の範囲で始めていきます。そして、i日目にきる服の種類に焦点を向けてfor文を回してます。ここで、処理を始める前に、特定の服を切るのに適していない気温の日のケースを除外していきましょう。そして、i-1日目に着る服の種類をfor文で全探索のような感じで探していきます。ここでも、気温の例外ケースを除外していきます。そして、i日目に着る服とi-1日目に着る服の絶対値の差とそれまでの最大値がdpの値を足して、一番大きい値をdpに記録します。そして、メインのfor文の外でも最終日の値の最大値を比べまくって、一番大きい値を答えとして出力していきます(ちょっと小泉構文みたいになってますね笑笑)

JOI 2015 予選 4 - シルクロード

practice.py

INF = 1<<60
n,m = map(int, input().split())
cities = [0]
weathers = [0]
for _ in range(n):
    city = int(input())
    cities.append(city)
for _ in range(m):
    weather = int(input())
    weathers.append(weather)
dp = [[INF]*(m+1) for _ in range(n+1)]
for i in range(m+1):
    dp[0][i] = 0
for i in range(1,n+1):
    for j in range(1,m+1):
        dp[i][j] = min(dp[i][j-1], dp[i-1][j-1]+(cities[i]*weathers[j]))
print(dp[-1][-1])

この問題ではまず最初に必要な情報を集めて行って、求められている値が最小値なのでdpをINFベースで作っていきます。そして、それぞれの街の0日目の値を0に変えていきましょう。(これをしないと全ての値がINFになってしまう)ここからdpを始めていきます。待機をして1日前と同じ値と、行動を起こして増えた値を比べて、低い方をdpに落とし込んでいって、最終日の最後の街の値を出力したらACです。

パ研杯2019 D - パ研軍旗

practice.py

n = int(input())
cols = [[0]*n for _ in range(3)]
for _ in range(5):
    tmp = input()
    for i in range(n):
        if tmp[i] == "W":
            cols[0][i] += 1
        elif tmp[i] == "R":
            cols[1][i] += 1
        elif tmp[i] == "B":
            cols[2][i] += 1
dp = [[0]*3 for _ in range(n)]
for i in range(3):
    dp[0][i] = 5-cols[i][0]
for i in range(1,n):
    for j in range(3):
        if j==0:
            dp[i][j] = (5-cols[j][i])+min(dp[i-1][1], dp[i-1][2])
        elif j==1:
            dp[i][j] = (5-cols[j][i])+min(dp[i-1][0], dp[i-1][2])
        else:
            dp[i][j] = (5-cols[j][i])+min(dp[i-1][0], dp[i-1][1])
print(min(dp[-1]))

この問題ではまず、文字列で与えられる色の情報を数字に変換をしていきます。その色の情報をcolsリストに格納していきます。各リストの段落ごとにどの列に特定の色の花がどれだけあるかを記録します。そして、dp用のリストを作っていきます。そして、dpの初期値をあらかじめ埋め込んでおきましょう。そして、for文の中ではjが花の種類を表しているので、jの値によって比べる値を変えていきましょう(隣の花と同じ色にはなれないから)。最後に最小値を出力してACです。