ABC233のA,B,C,D,E問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

シンプル：余計なことを考えずに済む
実装が楽：ミスやバグが減ってうれしい
時間がかからない：パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントかツイッター、マシュマロ、Discordサーバーまでお気軽にどうぞ！

Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー（質問や記事の感想・リクエストなどどうぞ！） : https://discord.gg/jZ8pkPRRMT
よかったらLGTMや拡散していただけると喜びます！

ABC233 まとめ

全提出人数: 7817人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	AB------	300	29分	5172(4932)位
400	AB------	300	12分	4287(4048)位
600	ABC-----	600	79分	3537(3303)位
800	AB-D----	700	62分	2791(2562)位
1000	ABCD----	1000	35分	2081(1854)位
1200	ABCDE---	1500	93分	1494(1279)位
1400	ABCDE---	1500	61分	1056(848)位
1600	ABCDE---	1500	42分	739(535)位
1800	ABCDE---	1500	29分	501(313)位
2000	ABCDEF--	2000	109分	314(166)位
2200	ABCDEF--	2000	74分	210(82)位
2400	ABCDE-G-	2100	87分	129(39)位

色別の正解率

色	人数	A	B	C	D	E	F	G	Ex
灰	2528	96.8 %	90.2 %	17.2 %	16.5 %	5.5 %	0.1 %	0.0 %	0.0 %
茶	1123	97.9 %	97.6 %	57.7 %	40.2 %	22.7 %	0.2 %	0.3 %	0.0 %
緑	936	97.7 %	97.4 %	83.1 %	70.1 %	55.0 %	1.7 %	0.4 %	0.1 %
水	594	97.5 %	97.1 %	95.0 %	92.3 %	88.9 %	7.2 %	1.2 %	0.7 %
青	394	96.5 %	96.5 %	95.2 %	97.0 %	95.4 %	29.9 %	7.9 %	3.3 %
黄	184	91.3 %	90.2 %	89.7 %	90.2 %	91.8 %	53.3 %	23.4 %	19.6 %
橙	42	92.9 %	92.9 %	92.9 %	92.9 %	90.5 %	88.1 %	40.5 %	52.4 %
赤	19	89.5 %	89.5 %	89.5 %	89.5 %	89.5 %	89.5 %	79.0 %	89.5 %

※表示レート、灰に初参加者は含めず

A問題『10yen Stamp』

問題ページ：A - 10yen Stamp
灰コーダー正解率：96.8 %
茶コーダー正解率：97.9 %
緑コーダー正解率：97.7 %

入力

$X$ : 貼られている切手の金額
$Y$ : 必要な切手の総額（ $Y$ 円以上ならOK）

考察

$X\ge{Y}$ ならば、 $10$ 円切手を $1$ 枚も貼らなくても金額が十分なので、答えは $0$ 枚です。

そうでない場合、$Y-X$ 円不足しているのを、$10$ 円切手で補う必要があります。必要な $10$ 円切手の枚数は、 $\frac{Y-X}{10}$ を小数点以下切り上げした枚数です。例えば、$40$ 円不足しているなら $4$ 枚、$55$ 円不足しているなら $ 6 $ 枚必要です。

実装

$X-Y$ を $10$ で割って切り上げた値は、以下のコードで計算できます。

ans = (Y - X + 10 - 1) // 9

素直にmathモジュールのceil関数を使って、以下のコードを使ってもこの問題はACできます。

from math import ceil
ans = ceil((Y - X) / 10)

しかし、コンピュータが小数点のある数を扱うと、誤差が生じることがあります。ですので、整数演算だけで誤差なく切り上げの計算ができる方法を使うようにするといいです。

一般に、$X$ を $Y$ で割って小数点以下を切り上げた値は

(X + Y - 1) // Y

で計算できます。

コード

X, Y = map(int, input().split())
if X > Y:
    ans = 0
else:
    d = Y - X  # 不足している金額
    ans = (d + 10 - 1) // 10  # 整数演算だけで切り上げをする方法です
print(ans)

別解

forループを使って、$10$ 円切手を使う枚数を小さい方から全探索してもいいです。

X, Y = map(int, input().split())
for i in range(100000):
    n = X + 10 * i
    if n >= Y:
        print(i)
        break

B問題『A Reverse』

問題ページ：B - A Reverse
灰コーダー正解率：90.2 %
茶コーダー正解率：97.6 %
緑コーダー正解率：97.4 %

入力

$L,R$ : 文字列 $S$ の $L$ 文字目から $R$ 文字目を反転する
$S$ : 長さ $1$ から $10^5$ の文字列

考察

書いてあるとおりにやるだけです。どう実装するかが問題です。

実装

Pythonでは、スライスを使って実装するのが簡単です。

問題文では $1$ 文字目から数えはじめていますが、Pythonのインデックスは $0$ から始まることに注意してください。

コード

L, R = map(int, input().split())
L = L - 1  # Lを0はじまりにします（Rはスライスの終端になりますが、R自体は含まないのでそのままでいいです）
S = input()
S_list = list(S)  # 文字列はイミュータブル（変更不可）なので、一度文字列のリストにします
S_list[L:R] = S_list[L:R][::-1]  # [::-1] で反転したものを代入します
print(*S_list, sep='')

C問題『Product』

問題ページ：C - Product
灰コーダー正解率：17.2 %
茶コーダー正解率：57.7 %
緑コーダー正解率：83.1 %

入力

$N$ : 袋の数（$N\ge2$）
$X$ : 取り出したボールの総積が $X$ になる取り出し方が何通りか数える
$L_i$ : $i$ 番目の袋に入っているボールの数（$L_i\ge2$）
$a_{i,j}$ : $i$ 番目の袋の $j$ 番目のボールに書いてある正の整数

袋に入っているボールの個数の総積は $10^5$ を超えない。すなわち $\displaystyle\prod_{i=1}^{N}L_i \leq 10^5$

考察

一見どこから手をつけていいかわからない問題です。

実は、すべての取り出し方についてそれぞれ、積がいくつになるか全探索をすることが可能です。

取り出し方は10万通り以下である

制約に『袋に入っているボールの個数の総積は $10^5$ を超えない』とあるからです。取り出し方の数は、ボールの個数の総積と等しいので、取り出し方も $10^5$ 通り以下になります。

例えば、袋が $3$ 袋あって、入っているボールの数が $2$ 個・$3$ 個・$4$ 個だとします。このとき、ボールの取り出し方は全部で $2\times{3}\times{4}=24$ 通りです。

袋の数は最大で16袋しかない

袋の数 $N$ は最大で $16$ 袋です。

袋に入っているボールの数の制約 $L_i\ge{2}$ より、ボールが $1$ 個しか入っていない袋は存在しません。$2^{16}\lt{10^5}\lt{2^{17}}$ より、すべての袋にボールを $2$ 個だけ入れることにしても、$17$ 袋目で総積が $10^5$ を超えてしまいます。したがって、袋の数は最大で $16$ 袋です。

コード

def main():
    N, X = map(int, input().split())
    nums = [1]  # 初期値に1を入れます
    for i in range(N):
        L, *A = map(int, input().split())  # Lは使いません、Aはリストになります
        nums = [x * y for x in nums for y in A if x * y <= X]  # 元のnumsとAの全要素の組み合わせを二重ループで掛け算します
    print(nums.count(X))  # 多くても10万要素しかないので、count(X)で数えていいです


if __name__ == '__main__':
    main()

D問題『Count Interval』

問題ページ：D - Count Interval
灰コーダー正解率：16.5 %
茶コーダー正解率：40.2 %
緑コーダー正解率：70.1 %

入力

$N$ : 数列の長さ
$K$ : 要素の和が $K$ になる連続部分列の数を求める
$A_i$ : 数列の $i$ 番目の要素

考察

まず、数列 $A$ の累積和を取ります。（$B$ と呼ぶことにします）

$B$ の $i$ 番目の要素は、$A$ の $0$ 番目から $i$ 番目の連続部分列の和と等しいです。

$B_i-B_j$（$i>j$）は、（$A$ の $0$ 番目から $i$ 番目の連続部分列の和）－（$A$ の $0$ 番目から $j$ 番目の連続部分列の和）= （$A$ の $j+1$ 番目から $i$ 番目の連続部分列の和）となります。

結局この問題は、各 $B_i$ について、$B_i\ -\ B_j = K$ （$i>j$）となる $B_j$ がいくつあるか数えて、足し合わせた値が答えになります。

累積和 $B$ を前から見ていって、見終わった値をCounterでカウントしていけば、$O(N)$でこの問題を解くことができます。

コード

from collections import Counter
from itertools import accumulate


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(accumulate(A))
    C = Counter()
    C[0] += 1  # 連続部分列の0番目からi番目を数えるために、0を1個入れる必要があります
    ans = 0

    for x in B:
        y = x - K  # x - y = K より、y = x - K である連続部分列が今まで何回出てきたかが知りたいものです
        ans += C[y]
        C[x] += 1

    print(ans)


if __name__ == '__main__':
    main()

E問題『Σ[k=0..10^100]floor(X／10^k)』

問題ページ：E - Σ[k=0..10^100]floor(X／10^k)
灰コーダー正解率：5.5 %
茶コーダー正解率：22.7 %
緑コーダー正解率：55.0 %

入力

$X$ : 最大 $500000$ 桁の正の整数

考察

例えば $X=54321$ なら、以下の計算を行えという問題です。

桁ごとに見ると、累積和の形になっています。

入力を桁ごとにバラした数列の累積和をとって、繰り上がりを考慮しつつ、筆算の要領で一桁ずつ下の位から求めていけばいいです。

コード

from itertools import accumulate


def main():
    X = input()
    A = [int(char) for char in X]  # list(map(int, X))と書いてもいいです
    B = list(accumulate(A))[::-1]  # 累積和をとって反転させます（1の位で必要なのはAの全要素の和ですから、逆順になります）
    res = []
    rem = 0
    for x in B:
        rem += x
        res.append(rem % 10)
        rem //= 10
    while rem > 0:  # 繰り上がり分が残っている場合があります
        res.append(rem % 10)
        rem //= 10
    ans = res[::-1]  # 一番下の位が先頭に来ているので、反転させます
    print(*ans, sep='')


if __name__ == '__main__':
    main()

【AtCoder解説】PythonでABC233のA,B,C,D,E問題を制する！

目次

アプリ AtCoderFacts を開発しています