[ABC265] AtCoder Beginner Contest 265（A-E 問題 Python）

AtCoder Beginner Contest 265 の復習記録です。難易度が青色レベル以下の、A問題からE問題までをやります。使用言語はPythonです。

A問題

https://atcoder.jp/contests/abc265/tasks/abc265_a

考え方

$N$ 個のりんごを買うとき、 $3$ で割った余りの端数分は $1$ 個ずつ購入するしか方法がありませんが、$3$ で割った商の分だけ、$3$ 個セットで購入することができます。ただし $3$ 個セットで買うときは、セットを使わないで $1$ 個ずつ $X×3$ 円で購入するのと、$3$ 個セットの $Y$ 円で購入するので、どちらが得か比較する必要があります。

提出コード

X,Y,N = map(int,input().split())
ans = N//3*min(Y,3*X) + N%3*X
print(ans)

B問題

https://atcoder.jp/contests/abc265/tasks/abc265_b

考え方

ボーナス時間の取り扱いを工夫します。ボーナス部屋に入るとボーナス時間がもらえますが、これを必要時間から差し引きすると考えても同じです。

あとは、残り時間 $T$ が $0$ 以下になるかどうかを判定しながら、$A[i]$ を引いていけば良いです。

提出コード

N,M,T = map(int,input().split())
A = list(map(int,input().split()))

for _ in range(M):
    X,Y = map(int,input().split())
    A[X-1] -= Y

flag = True
for i in range(N-1):
    T -= A[i]
    if T <= 0:
        flag = False
        break

if flag == True:
    print("Yes")
else:
    print("No")

C問題

https://atcoder.jp/contests/abc265/tasks/abc265_c

考え方

通ったことのあるマスを、$rec$ に記録しておき、通ったことのあるマスに到達したら、$-1$ を出力して終了するようにします。あとは、移動先のマスがグリッドの外に出た場合には、移動前のマスを出力するようにします。

提出コード

import sys
H,W = map(int,input().split())
G = [input() for _ in range(H)]
rec = [0]*H*W
i1,i2,j1,j2 = 0,0,0,0
rec[i1*W+j1] = 1

while 0<=i2<H and 0<=j2<W:
    if G[i1][j1] == "U":
        i2,j2 = i1-1,j1
    elif G[i1][j1] == "D":
        i2,j2 = i1+1,j1
    elif G[i1][j1] == "L":
        i2,j2 = i1,j1-1
    elif G[i1][j1] == "R":
        i2,j2 = i1,j1+1

    if 0<=i2<H and 0<=j2<W:
        if rec[i2*W+j2] == 1:
            print(-1)
            sys.exit()
        
        i1,j1 = i2,j2
        rec[i1*W+j1] = 1

print(i1+1,j1+1)

D問題

https://atcoder.jp/contests/abc265/tasks/abc265_d

考え方

あらかじめ累積和を計算しておけば、累積和の引き算は区間和になります。あとは、bisectを用いて二分探索で目的の区間和が得られるかどうかを判定します。

提出コード

from bisect import bisect_left
N,P,Q,R = map(int,input().split())
A = list(map(int,input().split()))
S = [0]
for i in range(N):
    S.append(S[-1]+A[i])

flag = False
for x in range(N):
    y = bisect_left(S,S[x]+P)
    if y>N or S[y] != S[x]+P:
        continue

    z = bisect_left(S,S[y]+Q)
    if z>N or S[z] != S[y]+Q:
        continue

    w = bisect_left(S,S[z]+R)
    if w>N or S[w] != S[z]+R:
        continue
    
    flag = True

print("Yes") if flag == True else print("No")

E問題

https://atcoder.jp/contests/abc265/tasks/abc265_e

考え方

DPで解きます。ただし、DPテーブルを座標で設定しようとしても、本問は座標の制限がないので不可能です。また、今回求めるのは経路の数なので、同じ座標であっても、そこに至る経路が異なれば別経路として考える必要があります。
ワープの仕方はたかだか $3$ 通りだけで、ワープ移動の座標変化は固定値なので、座標自体を考えるよりも、ワープの仕方の内訳でDPテーブルを設定する方が良いです。

$N$ 回ワープし、ワープ $1$ を $a$ 回、ワープ $2$ を $b$ 回、ワープ $3$ を $N-a-b$ 回行ったときの経路数を $DP[a][b][N]$ と定義します。

ワープ	移動量	回数
$1$	$(A,B)$	$a$ 回
$2$	$(C,D)$	$b$ 回
$3$	$(E,F)$	$N-a-b$ 回

$$x = A×a+C×b+E×(N-a-b)$$

$$y = B×a+D×b+F×(N-a-b)$$

が座標になりますので、この位置が、障害物と一致しないかをチェックしながら、DP遷移を考えていきます。

提出コード

N,M = map(int,input().split())
A,B,C,D,E,F = map(int,input().split())
dx,dy = [A,C,E],[B,D,F]
mod = 998244353

obs = set()
for _ in range(M):
    X,Y=map(int,input().split())
    obs.add((X,Y))

DP = [[[0]*(N+1) for _ in range(N+1)] for __ in range(N+1)]
DP[0][0][0] = 1

for i in range(N):
    for a in range(i+1):
        for b in range(i-a+1):
            c = i-a-b
            x = A*a+C*b+E*c
            y = B*a+D*b+F*c

            for j in range(3):
                if (x+dx[j], y+dy[j]) in obs:
                    continue

                if j == 0:
                    DP[a+1][b][i+1] += DP[a][b][i]
                    DP[a+1][b][i+1] %= mod
                elif j == 1:
                    DP[a][b+1][i+1] += DP[a][b][i]
                    DP[a][b+1][i+1] %= mod
                else:
                    DP[a][b][i+1] += DP[a][b][i]
                    DP[a][b][i+1] %= mod

ans = 0
for a in range(N+1):
    for b in range(N+1):
        ans += DP[a][b][N]
        ans %= mod
print(ans)