Zenn
🐡

AtCoder ABC233 個人的メモ

2021/12/26に公開
Python
競技プログラミング
AtCoder
tech

A - 10yen Stamp

Y-Xを10で切り上げの割り算すればおｋ

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

print(max(0, -(-(Y - X) // 10)))

B - A Reverse 

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

L -= 1
ans = S[:L] + S[L:R][::-1] + S[R:]

print("".join(ans))

C - Product

制約の3つ目の「袋に入っているボールの個数の総積は10^5を超えない」というのは、ボールの取り出し方の場合の数は10^5を超えないということ。
つまり、あるボールの取り出し方でのボールに書かれた数の総積をO(1)で求めることができるならば、ボールの取り出し方を全探索すれば十分高速に答えを求めることができる。
なので、DFSで全探索しつつボールの数の積を計算していけばおｋ。

from sys import setrecursionlimit

setrecursionlimit(10 ** 7)


def rec(bag_i: int, all_product: int):
    """bag_i番目の袋からボールを選ぶ"""
    # すべての袋から1つづつボールを選び終わった場合
    if bag_i >= N:
        if all_product == X:
            return 1
        else:
            return 0
    # まだボールを選んでいない袋がある場合
    res = 0
    for a in A[bag_i]:
        res += rec(bag_i + 1, all_product * a)
    return res


N, X = map(int, input().split())
# 入力は数列Aだけ欲しいので、Lは捨てている
A = [list(map(int, input().split()[1:])) for _ in range(N)]

print(rec(0, 1))

D - Count Interval

数列Aに区間[l,r]の区間和がKとなる区間がいくつかあるかが知りたい。
区間和は事前に累積和を取っておけばO(1)で求めれる。
区間の数え上げなので尺取法かと思うが、Aに負の数を含むので素直には解けなさそう。

とりあえずlを小さい方から順に見ていくとする。
lを固定した時に[l,r]の区間和がKとなるrの個数は、Aのl番目以降の全ての要素からなる数列B_l=(A_l,A_{l+1},\ldots ,A_N)の累積和C_lを取って、その中のKとなる要素の個数と等しい。
しかし、各lで毎回累積和を取るのは計算量が厳しい。
ここで、l-1からlに変化した時のC_{l-1}からC_lへの変化を考えてみると、C_lはC_{l-1}の2番目以降の全ての要素からA_{l-1}を引いたものと分かる。

例1の場合のC
l = 1  (8,  5, 10, 17, 17, 13)
l = 2  (   -3,  2,  9,  9,  5)  # 全ての要素がl=1の場合からA[1]=8だけ引き算されている
l = 3  (        5, 12, 12,  8)  # A[2]=-3だけ引き算されている
l = 4  (            7,  7,  3)
l = 5  (                0, -4)
l = 6  (                   -4)

上記の様にC_{l-1}の要素全てからA_lを引いてC_lを作った後にKと比較するよりも、C_{l-1}の2番目以降の要素とk_l=k_{l-1}+A_{l-1}(k_0=K)を比較するほうが高速に同じ結果を得られそう。
なので、そうする。

例1の場合
l = 1  ( 8,  5, 10, 17, 17, 13)  k=K=5となる要素の個数だけ区間和[l,r]がKになる
l = 2  (     5, 10, 17, 17, 13)  k =  5 +   8  = 13
l = 3  (        10, 17, 17, 13)  k = 13 + (-3) = 10
l = 4  (            17, 17, 13)  k = 10 +   5  = 15
l = 5  (                17, 13)  k = 15 +   7  = 22
l = 6  (                    13)  k = 22 +   0  = 22

from collections import Counter
from itertools import accumulate

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

cumsum = list(accumulate(A, initial=0))
cnt = Counter(cumsum)
ans = 0
for i in range(N):
    cnt[cumsum[i]] -= 1
    ans += cnt[K + cumsum[i]]

print(ans)

E - Σ[k=0..10^100]floor(X／10^k)

以下のコードで正しい解は得られるがTLEする。

# TLEするコード
X = int(input())
ans = 0
while X:
    ans += X
    X //= 10
print(ans)

制約より|X|\leq 10^{5\times 10^5}なので、Xは5\times 10^5桁以下。
なので、各桁をO(1)で計算できれば良さそう。
そのために筆算のように計算する。
i桁目の数の和を求めるのにO(|X|)かかるので、累積和も必要。

from itertools import accumulate


def cal_hissann(i, res):
    ans[M - i - 1] = res % 10
    kuriagari = res // 10
    return kuriagari


X = list(map(int, input()))

X.append(0)     # 累積和を0始まりにするためにXに0を追加しておく
cumsum = list(accumulate(X[::-1]))
M = len(X) + 1  # 例2のような繰り上がりのためにansの長さは|X|+1必要
ans = [0] * M
res = 0
for i in range(len(X)):
    res += cumsum[-1] - cumsum[i]
    res = cal_hissann(i, res)

if res:
    cal_hissann(len(X), res)

print(int("".join(map(str, ans))))

Discussion