LoginSignup
2
0

More than 5 years have passed since last update.

Python3でAt CoderのTypical DP Contestに挑戦してみる(その2 Bゲーム)

Posted at

引き続き挑戦。またしても以下のサイトにお世話になりました。ありがとうございます。
クリエイティヴなヴログ

今回と前回で2度もお世話になった上記のブログですが,TDPCのC問題については記事がないようなので,次からは自力でやらないといけないかもしれません。頑張ります。

今のところ,クリエイティヴなヴログさんのC++(ですか?)のソースをpythonで書き直しただけなので,自力解決できるようにしたいです。

#入力を受け取る

#数列a,bの要素数
A, B = input().split()
A = int(A)
B = int(B)

#数列a,bの具体的な値
a = list(map(int, input().split()))
b = list(map(int, input().split()))

#各局面における先攻のスコアをリストdpに格納する(0で初期化))
dp = [[0 for i in range(B+1)] for j in range(A+1)]

for i in reversed(range(0,A+1)):
    for j in reversed(range(0,B+1)):

        if i + j == A + B:
            continue

        #先攻のときは,2通りあるうちのよりスコアが大きくなるほうへ行動
        if (i+j)%2 == 0:
            if i == A:#Bの山からしか取れないとき
                dp[i][j] = b[j]+dp[i][j+1]
            elif j == B:#Aの山からしか取れないとき
                dp[i][j] = a[i]+dp[i+1][j]
            else:
                dp[i][j] = max(a[i]+dp[i+1][j], b[j]+dp[i][j+1])

        #後攻のときは,先攻のスコアが小さくなるように行動する
        else:
            if i == A:#Bの山からしか取れないとき
                dp[i][j] = dp[i][j+1]
            elif j == B:#Aの山からしか取れないとき
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = min(dp[i+1][j], dp[i][j+1])

print(dp[0][0])
2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0