作成日 : 2021-12-26
更新日 : 2021-12-26
9 min readAtCoder

【備忘録】AtCoder Beginner Contest 233 A~D問題

AtCoder Beginner Contest 233のA~D問題に関して、問題文からContest中に考えたこと、解答等を備忘録としてまとめました。是非最後までご一読ください。

そもそもAtCoderとは?

AtCoderを一言で表すと、オンラインで参加できるプログラミングコンテスト(競技プログラミング)サイトになります。リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問に、いつでも挑戦出来ることが魅力です。

今回は 「AtCoder Beginner Contest 233」のプログラミングコンテストへ参加しました。

「AtCoder Beginner Contest 233」

コンテスト情報

• コンテスト時間 : 100分
• レーティング更新対象 : 0 - 1999

配点

ルール

1. コンテスト中に問題に正解すると点数を獲得できます。
2. 順位は総合得点で決定します。
3. 同点の場合は提出時間の早い人が上の順位になります。
4. 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。(ルールに関して詳しくみる)

このコンテストは「コンテスト中に提出された結果」だけで順位が決定します。

A -> 10yen Stamp

問題文

サンタさんに手紙を出したい高橋くんは、 X円切手が1枚だけ貼られた封筒を用意しました。サンタさんに手紙を届けるためには、貼られている切手の総額がY円以上である必要があります。高橋くんは、この封筒に10円切手を何枚か貼り足すことで、貼られている切手の総額をY円以上にしたいです。

高橋くんはこの封筒に、最小で何枚の10円切手を貼り足す必要がありますか?

制約

• X, Yは整数
• 1 ≤ X, Y ≤ 1000

入力

入力は以下の形式で標準入力から与えられる。

1X Y

出力

答えを整数として出力せよ。

本問題は、AtCoder株式会社で作成された、A - 10yen Stamp問題を参照しております。

Contest中に考えたこと

• 10円切手をY円を超えるまで足していく。
• 10円切手を使った個数を出力する。

解答

1# 標準入力を受け付ける。
2X, Y = map(int, input().split())
3
4cnt = 0
5while X < Y:
6    cnt += 1
7    # 10円切手をY円を超えるまで足していく。
8    X += 10
9
10# 10円切手を使った個数を出力する。
11print(cnt)

B -> A Reverse

問題文

整数L, Rと、英小文字のみからなる文字列Sが与えられます。SのL文字目からR文字目までの部分を反転した(すなわち、 L文字目からR文字目までの文字の並びを逆にした)文字列を出力してください。

制約

• Sは英小文字のみからなる。
• 1 ≤ ∣S∣ ≤ 10の5乗(∣S∣はSの長さ)
• L, Rは整数
• 1 ≤ L ≤ R ≤ ∣S∣

入力

入力は以下の形式で標準入力から与えられる。

1L R
2S

出力

問題文の指示通り出力せよ。

本問題は、AtCoder株式会社で作成された、B - A Reverse問題を参照しております。

Contest中に考えたこと

• L ~ Rの文字列を切り出して、反転する。
• L ~ Rの文字列を切り出して、反転した文字列をL ~ R以外の文字列と連結する。

解答

1# 標準入力を受け付ける。
2L, R = map(int, input().split())
3s = input()
4
5# L ~ Rの間の文字列を反転する。
6# L - 1としているのは、配列のインデックスの始まりが0からだから。
7# 参考 : https://note.nkmk.me/python-str-extract/
8center = s[L - 1:R]
9# 参考 : https://note.nkmk.me/python-reverse-reversed/
10center = ''.join(list(reversed(center)))
11
12value = ''
13flag = False
14for i in range(len(s)):
15    # L ~ Rの間だけ、反転処理を行う。
16    # L - 1, R - 1としているのは、配列のインデックスの始まりが0からだから。
17    if L - 1 <= i and i <= R - 1:
18        if flag:
19            continue
20
21        flag = True
22
23        # 一度だけ反転した文字列の値を格納する。
24        value = value + center
25
26        continue
27    # それ以外の場合は反転処理を行わない。
28    value = value + s[i]
29
30print(value)

C -> Product

問題文

N個の袋があります。袋iにはLi個のボールが入っていて、袋iのj(1 ≤ j ≤ Li)番目のボールには正の整数ai, jが書かれています。

それぞれの袋から1つずつボールを取り出します。取り出したボールに書かれた数の総積がXになるような取り出し方は何通りありますか？

ただし、書かれた数が同じであっても全てのボールは区別します。

制約

• N ≥ 2
• Li ≥ 2
• 袋に入っているボールの個数の総積は10の5乗を超えない。
• 1 ≤ ai, j ≤ 10の9乗
• 1≤ X ≤ 10の18乗
• 入力に含まれる値は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

1N X
2L1 a1,1 a1,2 … a1,L1
3​L2 a2,1 a2,2 … a2,L2
4⋮
5LN aN,1 aN,2 … aN,LN

出力

答えを出力せよ。

本問題は、AtCoder株式会社で作成された、C - Product問題を参照しております。

Contest中に考えたこと

• 問題文を誤読していた。。
• Xになる数 = 素因数分解して作られる値だと思う。素因数分解を行う。
• 素因数分解した値からXになる組み合わせの数字(Xが40の場合、(4, 10), (2, 20)など)を洗い出す。
• 組み合わせの数字に該当する袋内のボールがどれくらい存在するのか(Xが40の場合、(4, 10)の組み合わせの数字を持つ袋内のボールが(1, 2)存在する、(2, 20)の組み合わせの数字を持つ袋内のボールが(0, 1)存在するなど)確認する。
• 洗い出した、組み合わせの数字に該当する袋内のボールの数を掛け合わせて、合計する。
• ここで終了しました。。

解答

1import itertools
2# 袋に入っているボールの個数の総積は10の5乗を超えない。 ⏩ 袋の中からボールを1つずつ選ぶ組み合わせは10の5乗を超えないを意味する。 ⏩ 普通に全通り検証して問題ない。
3
4# 標準入力を受け付ける。
5N, X = map(int, input().split())
6
7# 袋の中に入っている、ボール情報を格納する。
8baggages = []
9
10for _ in range(N):
11    tmp = list(map(int, input().split()))
12    baggages.append(tmp[1:])
13
14# 参考 : https://note.nkmk.me/python-itertools-product/
15product_list = itertools.product(*baggages)
16ans = 0
17for product in product_list:
18    value = 1
19    for p in product:
20        if value > X:
21            break
22        value *= p
23
24    if X == value:
25        ans += 1
26
27print(ans)

D -> Count Interval

問題文

長さNの数列A=(A1, A2, …, AN)と、整数Kが与えられます。Aの連続部分列のうち、要素の和がKになるものはいくつありますか？

制約

• 1 ≤ N ≤ 2 × 10の5乗
• ∣Ai∣ ≤ 10の9乗
• ∣K∣ ≤ 10の15乗
• 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

1N K
2A1 A2 … AN

出力

答えを出力せよ。

本問題は、AtCoder株式会社で作成された、D - Count Interval問題を参照しております。

解答

1################################
2# <方針>
3# 連続部分列 ⏩ 連続部分列の一番左のインデックスをl, 連続部分列の一番右のインデックスをrとした場合に、0インデックス~rの数列の総和 - 0インデックス~lの数列の総和 = Kになるか確かめることになる。
4# r - l = kになればいいので、l = r - kになるlの位置がどれくらいあるのか探せば良い。
5################################
6
7from collections import Counter
8
9# 標準入力を受け付ける。
10N, K = map(int, input().split())
11
12A = list(map(int, input().split()))
13
14cnt = Counter([0])
15ans = 0
16r = 0
17for a in A:
18    r += a
19    ans += cnt[r - K]
20    cnt[r] += 1
21
22print(ans)

2021年12月25日時点のレート画像

プロフィールを確認する

参考文献

• レーティングとは?
• AtCoderのプログラミングコンテストのルール
• AtCoder株式会社について
• 素因数分解とは?
• Atcoder 233に関するコードまとめ