🐶

ABC233解説：本番でACできた問題＋1問（Python）

2022/02/03に公開

Python

A - 10yen Stamp

まずYからXを引き、残り何円あればよいかを考えます。
残りの金額を十分に満たす10円切手の枚数は、10で割った値を切り上げることで求まります。
また、YからXを引いた値が負の場合はもう十分な切手がはられているので、必要な枚数は0枚です。

a.py

X, Y = list(map(int, input().split()))

x = Y - X

print(max(0, (x + 10 - 1) // 10))

B - A Reverse

文字列のスライスを使って実装します。
反転はS[::-1]で行うことができます。
スライスはわかりにくいので、テストケースを用いて帳尻を合わせます。

b.py

L, R = list(map(int, input().split()))
S = input()

print(S[: L - 1] + S[L - 1 : R][::-1] + S[R:])

C - Product

$L_i \geq 2$ 、 $L_1 \times \dots \times L_N \leq 10^5$ の制約から、ボールの最小値が2のときの袋の数はおよそ20個となり、このとき取りうる組み合わせは1048576通りで、十分に全探索可能です。

しかし、いつものようにfor文で全探索をしようとすると実装が困難です。
こういうときにはDFSで全探索をすると簡潔に記載できます。

全探索のdfs関数には深さと値の2つを引数に取ると書きやすいです。
2回目以降のdfsでは深さを1段ずつ深くしていき、そのたびに値を更新していきます。

c.py

import sys
sys.setrecursionlimit(10 ** 6)

N, X = list(map(int, input().split()))
LA = [tuple(map(int, input().split())) for _ in range(N)]

A = [a for _, *a in LA]


def dfs(depth, value):
    ans = 0
    # 終了条件
    if depth == N:
        if value == X:
            return 1
        else:
            return 0
    for a in A[depth]:
        ans += dfs(depth + 1, value * a)
    return ans


print(dfs(0, 1))

なお、itertools.productとmath.prodを使うとかなりシンプルに実装できます。

c-library.py

from itertools import product
from math import prod

N, X = list(map(int, input().split()))
LA = [tuple(map(int, input().split())) for _ in range(N)]

A = [a for _, *a in LA]

ans = 0
for pro in product(*A):
    if prod(pro) == X:
        ans += 1

print(ans)

類題

D - Count Interval

Aの累積和を考えます。

$A = (8, -3, 5, 7, 0, -4)$ のとき、累積和は $S = (0, 8, 5, 10, 17, 17, 13)$ となります。

本問の題意は $l<r$ のとき、 $S_{r} - S_{l} = K$ となる $(l,r)$ を求めるというものです。
ここで、 $S_{r} - S_{l} = K$ から $S_{l} = S_{r} - K$ となります。
このとき、求めたい区間の数は $l<r$ のときに $S_{r} - K$ を満たす $l$ の個数になります。

また、 $S_{l}$ は $S_{r}$ を記録した配列に含まれることが重要な考察になります。
for文で $S_{r}$ の出現数をカウントすることで、いつか $S_{l}$ として使う値を記録することができます。
この性質によって $S_l$ を求めるためにfor文を追加する必要がなくなり、for文ひとつで答えが求まります。

d.py

from collections import defaultdict

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

# 累積和
S = [0]
for a in A:
    S.append(S[-1] + a)

d = defaultdict(int)

ans = 0

for Sr in S:
    Sl = Sr - K
    ans += d[Sl]
    d[Sr] += 1

print(ans)

A - 10yen Stamp

B - A Reverse

C - Product

類題

D - Count Interval

Discussion