ABC323をPythonで（E, F）

ユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)のうち本番で解けなかったもの

E問題

X.5秒時点で曲1が流れている確率は

X秒で前の曲が終わって曲1が流れる確率
+X-1秒で前の曲が終わって曲1が流れる確率
+...
+max(0, X-t[0]+1)秒で曲が終わって曲1が流れる確率

曲1が流れる確率は1/n
時刻iで曲が流れ終わる確率は送るdpで求められる

E

n, x = map(int, input().split())
t = list(map(int, input().split()))
mod = 998244353

# dp[i]=時刻iで曲が流れ終わる確率
pow_n = pow(n, -1, mod)
dp = [1] + [0] * x
for i in range(x):
    for t_i in t:
        if i + t_i <= x:
            dp[i + t_i] += dp[i] * pow_n % mod

print(sum(dp[max(0, x - t[0] + 1):]) * pow_n % mod)

F問題

まず考えるパターンを減らすために、点Cを原点に、点Bを第一象限にあるように、平行移動と回転移動をさせる。

移動距離として考えることは
1、荷物を押すための移動で最短距離だと交錯するときは2歩ぶん遠回りする
2、荷物を押しているときに曲がる必要があるときは2歩余分に歩く必要がある

F

xa, ya, xb, yb, xc, yc = map(int, input().split())

# 平行移動　Cを原点に
xa, xb, xc = xa - xc, xb - xc, xc - xc
ya, yb, yc = ya - yc, yb - yc, yc - yc

# 回転移動　Bを第一象限に
if xb < 0:xa *= -1; xb *= -1
if yb < 0:ya *= -1; yb *= -1

def dist(sx, sy, gx, gy):
    # (sx, sy):start
    # (gx, gy):goal
    return abs(sx - gx) + abs(sy - gy)

ans = 0
if xa == xb and ya < yb:
    ans1 = 1 + dist(xa + 1, ya, xb, yb + 1) + dist(xb, yb, xc, yc) + 2 * (xb != xc)
else:
    ans1 = dist(xa, ya, xb, yb + 1) + dist(xb, yb, xc, yc) + 2 * (xb != xc)

if ya == yb and xa < xb:
    ans2 = 1 + dist(xa, ya + 1, xb + 1, yb) + dist(xb, yb, xc, yc) + 2 * (yb != yc)
else:
    ans2 = dist(xa, ya, xb + 1, yb) + dist(xb, yb, xc, yc) + 2 * (yb != yc)

ans = min(ans1, ans2)

print(ans)