Tenka1 Programmer Beginner Contest

Python

tenka1-2019-beginner.contest.atcoder.jp
2完。40分遅れで始めたとはいえCが解けなかったのが悔しい。。左が白、右が黒の並びになればいいところまではわかったけど、ロジックに穴がありWA食らいました。もうちょいサンプル欲しかったなぁという負け惜しみ。

Cは左側が白、右側が黒というように分かれればよくて、[0, i)までを白領域、[i, N)までを黒領域(i == 0なら全部黒、i == Nなら全部白)とすると、「白領域の黒の数と黒領域の白の数の和」がひっくり返せばいい数になるので、あとはiを[0, N]まで動かして最小値を探索すればok。前回使った累積和が出てきたけど見事に活用できなかったな。

N = int(input())
S = input()

cum_sum_b = [0]
cum_sum_w = [0]

sum_b = 0
sum_w = 0
for i, s in enumerate(S):
    if s == '#':
        sum_b += 1
    else:
        sum_w += 1
    cum_sum_b.append(sum_b)
    cum_sum_w.append(sum_w)

ans = N
for i in range(0, N + 1):
    count = cum_sum_b[i] + cum_sum_w[N] - cum_sum_w[i]
    ans = min(ans, count)

print(ans)

Pythonで、多分こんな雰囲気。


Dは解説聞かないと正直解ける気しなかったです。
解き方は解説動画に任せて式の立て方としては、
i = 0...N, j = 0...{a0...aNの総和s}として、
R == j で残りはGorBで塗る組み合わせの数(dp0)と、R == jで残りはGで塗る組み合わせの数(dp1)をそれぞれDPで出し、
dp0からR>=sの時の組み合わせの数、dp1からR==G==s/2の時の組み合わせの数がわかるので、そこから答えを求める
という感じのよう。

import math

N = int(input())
a = [int(input()) for _ in range(N)]
s = sum(a)

# Calculate counts of (R >= s / 2)
dp = [[0 for _ in range(s + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    for j in range(s + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        else:
            dp[i][j] = dp[i - 1][j] * 2 + (dp[i - 1][j - a[i - 1]] if j >= a[i - 1] else 0)
c0 = sum(dp[N][math.ceil(s / 2):])

# Calculate counts of (R == s / 2 and G == s / 2)
dp = [[0 for _ in range(s // 2 + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    for j in range(s // 2 + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        else:
            dp[i][j] = dp[i - 1][j] + (dp[i - 1][j - a[i - 1]] if j >= a[i - 1] else 0)
c1 = dp[N][s // 2] if s % 2 == 0 else 0

ans = (3 ** N - 3 * c0 + 3 * c1) % 998244353
print(ans)

ただこれだとTLEするPythonには辛い仕様で、通すにはnumpy芸が必要なよう。

import math
import numpy as np

N = int(input())
a = np.array([int(input()) for _ in range(N)])
s = np.sum(a)

dp0 = np.zeros((N + 1, s + 1), dtype=np.int64)
dp0[0, 0] = 1
dp1 = np.zeros((N + 1, s // 2 + 1), dtype=np.int64)
dp1[0, 0] = 1

mod = 998244353
for i, x in enumerate(a):
    dp0[i + 1, :] += dp0[i, :] * 2 % mod
    dp0[i + 1, x:] += dp0[i, :-x] % mod
    dp1[i + 1, :] += dp1[i, :] % mod
    dp1[i + 1, x:] += dp1[i, :-x] % mod

# Counts of (R >= s / 2)
c0 = int(np.sum(dp0[N][math.ceil(s / 2):]))
# Counts of (R == s / 2 and G == s / 2)
c1 = int(dp1[N][s // 2]) if s % 2 == 0 else 0

ans = (3 ** N - 3 * c0 + 3 * c1) % mod
print(ans)

こんな感じにすればいけそう。マイナスのインデックスが慣れないですが、リストの長さ-xと同じですね。
numpyも慣れないといけないけど、なかなかむずい。。