🐶

ABC233解説:本番でACできた問題+1問(Python)

2022/02/03に公開

A - 10yen Stamp

https://atcoder.jp/contests/ABC233/tasks/abc233_a

まず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

https://atcoder.jp/contests/ABC233/tasks/abc233_b

文字列のスライスを使って実装します。
反転は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

https://atcoder.jp/contests/ABC233/tasks/abc233_c

L_i \geq 2L_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)

類題

https://atcoder.jp/contests/abc165/tasks/abc165_c

https://atcoder.jp/contests/abc161/tasks/abc161_d

D - Count Interval

https://atcoder.jp/contests/ABC233/tasks/abc233_d

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)

Discussion